0

'x' をマッピング/ビニングできる整数 'x' と 'n' の可能な値があると仮定します。xに最も近い「n番目」の値を返す関数を持つCのエレガントな方法は何ですか?

疑似コードの例。

int x = 40;
int res;
int bins[] = { 0, 20, 80, 200 }; /* Sorting is guaranteed */

res = int_bin(x, bins);
assert(res == 20); /* 40 is closer to 20 than 80 */

x = 150;

res = int_bin(x, bins);
assert(res == 200); /* 150 is closer to 200 than 80 */

エレガントとは、if/else if/else ステートメントの束だけではないことを意味します。

4

3 に答える 3

5

リストがソートされている場合は、単純に値のバイナリ検索を実行できます。

検索でリストに値が見つからない場合、その値がリストにあったとしたら、その値がどのインデックスにあったかがわかります。次に、値をそのインデックスの要素と前のインデックスの要素 (明らかにインデックスがゼロでない場合) と比較して、どちらが近いかを確認できます。

于 2010-06-22T18:52:24.660 に答える
1

各ビンの中心値を格納する代わりに、各ビンの境界値を格納します。配列の先頭と末尾にセンチネル値を使用して、検索で常に答えが見つかるようにします。あなたの例では、に置き換え{ 0, 20, 80, 200 }てください{ INT_MIN, 10, 50, 140, INT_MAX }。

実際の問題が例のように単純な場合は、線形検索を使用できます。それ以外の場合は、二分探索が有効です。

于 2010-06-22T21:43:14.813 に答える
0

ここで自分の質問に答えます。

できるだけ多くの標準 C 関数を再利用したいので。bsearch() を使用できるとは思いません。要素が見つからない場合に移動する場所のインデックスに関する情報が得られないためです。私は自分自身を転がす必要があります。

ただし、qsort()bins[] 配列で使用して、ビンが「x」にどれだけ近いかに基づいてソートする比較関数を指定し、0 番目の要素を答えとして選択するのはどうですか?

于 2010-06-22T19:04:54.053 に答える