0

この課題のアルゴリズムを作成するのに問題があります。誰が最初のアルゴリズムを開始するかについてのヒントを得ることができれば幸いです.

この割り当ての目標は、特定のセットの可能なすべてのサイズのサブセットの数を計算するためのさまざまなアルゴリズムを実装して比較することです。n 個の要素を持つセットには 2^n 個のサブセットがあることに注意してください。実際にサブセットを生成するために、2 つのアルゴリズムが使用されます。あなたのプログラムは、ユーザーが終了するまで選択を求める機能を備えています。プログラムの GUI は許可されていますが、必須ではありません。選択により、次のことが可能になります。

  1. 0 から始まる 2^n 個の整数をすべてカウントし (C/C++/Java の int データ型を使用できない場合があります)、各数値に対応するサブセットのサイズを決定することに基づいて機能するアルゴリズムを実行します。このアルゴリズムでは、何らかの方法で整数除算とモジュラスを使用する必要があります。可能な各サイズのサブセットの数を保持する配列を返す必要があります。可能なサイズごとのサブセットの数を表示します。n の値は、ユーザー入力によって決定されます。n に対してエラー チェックを実行する必要があります。

  2. 0 から始まる 2^n 個の整数をすべてカウントし (C/C++/Java の int データ型を使用できない場合があります)、各数値に対応するサブセットのサイズを決定することに基づいて機能するアルゴリズムを実行します。このアルゴリズムでは、何らかの方法でビットレベル演算 (論理 AND およびシフト) を使用する必要があります。可能な各サイズのサブセットの数を保持する配列を返す必要があります。可能なサイズごとのサブセットの数を表示します。n の値は、ユーザー入力によって決定されます。n に対してエラー チェックを実行する必要があります。

  3. 0 から n (両端を含む) までの k のすべての値に対して C(n,k) を生成するアルゴリズムを実行します。ここで、n はユーザー入力によって決定されます。このアルゴリズムは、再帰階乗関数を利用する必要があります。可能な各サイズのサブセットの数を保持する配列を返す必要があります。可能なサイズごとのサブセットの数を表示します。n に対してエラー チェックを実行する必要があります。

  4. 0 から n (両端を含む) までの k のすべての値に対して C(n,k) を生成するアルゴリズムを実行します。ここで、n はユーザー入力によって決定されます。このアルゴリズムは、反復階乗アルゴリズムを利用する必要があります。可能な各サイズのサブセットの数を保持する配列を返す必要があります。可能なサイズごとのサブセットの数を表示します。n に対してエラー チェックを実行する必要があります。

4

1 に答える 1

0

あなたの質問はすべて、Recursive Backtrackingという 1 つのテーマに関するものだと思います。

集合 S の累乗集合を生成するには、次のようにします。

function rec( i )
      if i == S.length
         print choocen elements of S
         return
      else
         do not chooce element i of S
         rec(i + 1)
         choose element i of S
         rec(i + 1)

再帰の概念を理解すれば、問題C(n, k)も同様です。私はあなたの課題の解決策をあなたに与えるつもりはありません:)

于 2012-10-19T17:29:07.283 に答える