1

整数の順序付けられた配列に対してこの検索アルゴリズムを実装しました。フィードした最初のデータセット（500整数）では正常に機能しますが、それより長い検索では失敗します。ただし、すべてのセットは、割り当て用に実装した他の4つの検索アルゴリズムと完全に連携します。

これは、178行目でセグメンテーション違反を返す関数です（予期しない負のm値が原因）。どんな助けでも大歓迎です。

コード：

155 /* perform Algortihm 'InterPolationSearch' on the set
156  * and if 'key' is found in the set return it's index
157  * otherwise return -1 */
158 int
159 interpolation_search(int *set, int len, int key)
160 {
161   int l = 0;
162   int r = len - 1;
163   int m;
164
165   while (set[l] < key &&  set[r] >= key)
166   {
167
168     printf ("m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l])\n");
169
170     printf ("m = %d + ((%d - %d) * (%d - %d)) / (%d - %d);\n", l, key, set[l], r, l, set[r], set[l]);
171     m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l]);
172     printf ("m = %d\n", m);
173
174 #ifdef COUNT_COMPARES
175     g_compares++;
176 #endif
177
178     if (set[m] < key)
179       l = m + 1;
180     else if (set[m] > key)
181       r = m - 1;
182     else
183       return m;
184   }
185
186   if (set[l] == key)
187     return l;
188   else
189     return -1;
190 }

出力：

m = l + ((key - set[l]) * (r - l)) / (set[r] - set[l])
m = 0 + ((68816 - 0) * (100000 - 0)) / (114836 - 0);
m = -14876

ありがとうございました！

リス

4

6 に答える 6

5

68816*100000は2^31を超えています。これは、おそらくマシンのintデータ型の制限です。整数のオーバーフローが発生しています。

コンパイラがサポートしている場合は、に変更してみてくださいlong long。実行して確認できます

#include <stdlib.h>
printf("the long long type is %u bits", (unsigned int) (CHAR_BIT * sizeof (long long)));

Naveenが指摘したように、実際の計算がこの精度で行われることも確認する必要があります。これはキャストによって行うことができます。

于 2010-03-31T07:20:10.937 に答える
1

あなたの算術はおそらくintあなたのプラットフォームのサイズをオーバーフローしています。

あなたは2つのことのうちの1つをする必要があります。より広い整数型（使用可能な場合）を使用するか、計算を再キャストして、このような大きな中間値を作成する必要がないようにします。

于 2010-03-31T07:19:40.877 に答える
1 
m = 0 + ((68816 - 0) * (100000 - 0)) / (114836 - 0);

68816 * 100000 = 6881600000 = (binary)110011010001011001110001000000000

それは33ビットです。事実上すべてのプラットフォームintで32ビットまたは（まれに）16ビットです。

long long少なくとも64ビットであることが保証されているものを使用してみることができます（C99で追加されましたが、ほとんどのコンパイラはC90でもサポートしています）。

于 2010-03-31T07:21:33.160 に答える
0

整数のオーバーフローに注意する必要があります。mより大きいタイプとして計算を実行し、終了したらintキャストバックするintことをお勧めします。

さらに、同じ行でゼロ除算エラーが発生する可能性があるため、セットに重複が含まれている場合は注意が必要な場合があります（つまり、の場合set[r] == set[l]）。

于 2010-03-31T07:21:19.517 に答える
0

これは、計算の中間値が、(68816 - 0) * (100000 - 0)内に保持できる値を超えているためintです。long long問題を解決するために、より大きな数（たとえば、）を保持できるデータ型に中間値をキャストできます。

于 2010-03-31T07:21:51.077 に答える
0

データ オーバーフローなどの問題を回避するために、さらに大きな数のライブラリを使用できます。良い例はhttp://gmplib.org/です。もちろん、オーバーヘッドが少し増えますが、全体的なパフォーマンスは非常に優れています。

于 2010-03-31T07:28:14.050 に答える