1

0..5 ..... 20 .... 25..40 ... 50 ...... 100のような範囲が与えられた場合、数値がどの範囲にあるかを判別する必要があります。したがって、問題は何であるかです。 aNum=56が範囲50....100にあるように、数値がどの範囲にあるかを判断する最も簡単な方法。範囲を決定した後、範囲の開始番号をaNum（この場合は50）に割り当てます。したがって、ついにaNum=50になります。

それに一定時間O（1）かかるのではないかと思います。

任意の提案をいただければ幸いです。それを行うために使用できる任意のデータ構造。

4

3 に答える 3

4

示されている範囲のタイプ（5で割り切れる）には、次のアルゴリズムが適しています。

  1. すべての範囲を5でセグメント化します（たとえば、25-40は実際には25-29、30-34、および35-39の3つの範囲です。

  2. セグメントを範囲にキー設定するルックアップ配列を作成します。したがって、たとえば、範囲25-39が＃4で、セグメント25-29が＃15の場合、30-34は＃16、35-39は＃17です。次に、lookup [15] = 4、lookup [16] = 4、lookup [17]=4などです。

  3. 今、それは分裂の問題です。数値を5で割ってDを取得し、範囲＃=lookup[D]にします。

範囲が不規則であり、共通の数値で割り切れない場合は、メモリを犠牲にして、すべての可能な値を含むルックアップテーブルを作成できます。

これは線形時間アルゴリズムです。

于 2012-10-25T15:05:52.647 に答える
2

順序付けられた範囲があると仮定するとN、ターゲット範囲はO(Log N)、バイナリ検索アルゴリズムを使用して見つけることができます。それ以下は不可能です。たとえば、次のようにすべての範囲が等しい場合を考えることができます。

1..2..3..4.. .. 99..100

この場合、ターゲット範囲を見つけることは、で実行できないソートされた配列で番号を見つけることと同じO(1)です。

于 2012-10-25T15:09:44.493 に答える
0

サンプルアルゴリズムは次のとおりです。

  1. 範囲の数と、各範囲の最小値と最大値を決定します。
  2. すべての範囲を反復処理し、数値を各範囲の最小値および最大値と比較します。
  3. いずれかの範囲にある場合は、その範囲の最小値に等しく設定してください。
  4. 範囲内にない場合は、必要なことをすべて実行してください。

次のコードは、このアルゴリズムをCで実装する例を示しています。

#include <stdio.h>
#include <stdlib.h>

/*We assume there is a fixed number of ranges*/
#define RANGE_COUNT 4

int main(int argc, char** argv){
   /*Set the minimum and maximum values for each range*/
   int ranges[RANGE_COUNT][2] = {{0, 5}, {20, 20}, {25, 40}, {50, 100}};
   int x = 0, num = 0;

   /*In this example, we are using the command-line for input*/
   if(argc != 2){
      fprintf(stderr, "Usage: %s <number>", argv[0]);
      exit(1);
   }

   /*We need to ensure that the input is a number*/
   if(!(num = atoi(argv[1])) && argv[1][0] != '0'){
      fprintf(stderr, "Error: \"%s\" is not a number", argv[1]);
      exit(1);
   }

   /*See if the number is in any of the ranges*/
   for(x = 0; x < RANGE_COUNT; x++){
      if(num >= ranges[x][0] && num <= ranges[x][1]){
         /*If the number is in a range, say which one it is*/
         printf("The number %d is in the range %d..%d\n",
            num, ranges[x][0], ranges[x][1]);

         /*Set the number equal to the minimum value of the range it is in*/
         num = ranges[x][0];
         printf("num = %d\n", num);
         exit(0);
      }
   }

   /*If the number is not in any of these ranges, indicate that it is not*/
   printf("The number %d is not in any of these ranges\n", num);

   return 0;
}
于 2012-10-26T03:14:40.893 に答える