2

指定されたサブセットに存在しない 1 から n までの数値を出力する必要があります。すべてのサブセットは 1 から n の間に収まります。サブセットは常に昇順です。たとえば、n=300 で、ユーザーが指定したサブセットが (30 から 70) (50 から 100) (150 から 200) および (250 から 300) の場合、出力を 1 から 29、101 から 149 の数字として出力する必要があります。 、201 ～ 249。

これに対する私のアプローチは次のとおりです。

  1. 1 から n までの各数値を取得し、指定されたサブセットのいずれかに存在するかどうかを確認します
  2. 指定されたサブセットのいずれにも存在しない場合は、その番号を出力します。
  3. それ以外の場合は続行します。

私が持っている質問は次のとおりです。

  1. これよりもエレガントなアプローチはありますか?
  2. そして、これをC言語でどのように実装できますか。(行ごとのコードを求めているわけではありません。C 言語でサブセットを表現する方法と、サブセット内の欠落数を検索する方法を知りたいだけです。)
4

4 に答える 4

2

n が固定されている場合、つまりユーザーが入力する必要はないが、ハードコーディングできる場合、次のような配列を定義できます。

#define N 300
int my_set[N + 1];

次に、配列全体を で初期化します。これは1、「この数値を出力する必要がある」ことを意味します。次に、ユーザーがサブセットを入力したら、対応する配列要素を に設定し0ます。最後に、配列をスキャンし、値が still である要素のインデックスを出力します1。

于 2013-09-07T17:55:37.877 に答える
1

アプローチは次のようになります（疑似コードを与えるだけです）：

  1. ペアの最初の要素の昇順でセットを並べ替えます。(あなたのケースでは既に並べ替えられています)

  2. 配列を取り、要素を次のように挿入します: 0, p(1,1),p(1,2),p(2,1),p(2,2).... (これは 0, 30,70,50,100,150,200,250,300...OP の場合)

  3. カウンターを 2 ずつインクリメントしながら (i を取る) 配列をループします。

  4. if(arr[i]<arr[i+1]) からループしarr[i]、arr[i+1]要素を印刷します。arr[i+1]それ以外の場合は、カウンターを 2 ずつインクリメントしながら、 th 要素よりも大きい要素に移動します。

例: 配列が次の場合: 0, 2, 5000, 3, 50, 60, 100, 6000, 6050; 5000 から 2 ずつ増加すると、6050 にジャンプします。

このアプローチの利点は、範囲内の各値を比較して出力するかどうかを比較しないことです。これは、範囲内の各数値を出力するかどうかをチェックすることよりもパフォーマンスが大幅に向上します。C で初期配列を作成するのは少し難しいでしょう (C++ では非常に簡単です)。

注: : 短い説明のため、最初はわかりにくく難しく見えるかもしれませんが、そうではありません。

于 2013-09-07T18:17:58.167 に答える
0

これがあなたが従うことができるアプローチです。あなたが与えられたとしましょう

[1 から N] の範囲。ここで、N は可変 (ユーザーからの入力)/定数 (固定済み) にすることができます。

サブセットは Ai[ai, bi] で、1<=i<=k です。つまり、ai が下限で bi が上限である k 個のサブセットがあります。

ここで、最初のノードを [1,N] としてツリーの作成を開始します。アルゴリズムの実行中の特定の時点で、ツリー内の各リーフ ノードは、特定のサブセットのいずれにも含まれない数値の範囲を表します。つまり、すべてのリーフ ノードの数値の範囲を出力する必要があります。

初期条件
まず、ツリーには葉ノード [1,N] が 1 つしかありません。つまり、サブセットをまだ処理していないため、1 から N までのすべての数値を出力する必要があります。

終了条件
アルゴリズム ツリーの最後には多くのリーフが含まれます。各リーフは、サブセットによってカバーされていない数値の範囲を表します。したがって、これらの数値を出力として出力する必要があります。

アルゴリズム：

STEP 1: Creating the Tree   
For i = 1 to k  //process for all given subsets
{
    For every leaf node in current tree
    {
        //Let [x,y] is the current leaf node being processed
        1. if(ai>=x && bi<=y) //subset being processed lie inside the leaf being
           processed.
           create nodes [x,ai-x] and [bi+1,y] and attach as child of the leaf node       
           being processed.

        2. if((x<=ai<y) && (bi>y)) //subset overflows towards right
           create a node [x, ai-1] and attach as child to the current leaf node being
           processed.

        3. if((ai<x) && (x<bi<=y)) //subset overflows towards left
           create a node [bi+1, y] and attach as child to the current leaf node being
           processed.
    }
}

STEP 2: Printing the output
//Now the leaf nodes indicate the numbers to be printed.
For each leaf node [x,y] of the resulting tree
{ 
    //you will get some leaf node with x>y
    if(x<=y)
         print the numbers in range [x,y].
}
于 2013-09-07T19:17:36.667 に答える