0

この再帰がどのように機能するかを理解する必要があります。単純な再帰の例は理解できますが、より高度な例は難しいです。問題が発生したコードは2行だけだと思っていましたが、returnステートメント自体です。これがどのように機能するか、特に and/or 演算子については空白にします。どんな洞察も大歓迎です。

      bool subsetSumExists(Set<int> & set, int target) {
      if (set.isEmpty()) {
         return target == 0;
      } else {
         int element = set.first();
         Set<int> rest = set - element;
         return subsetSumExists(rest, target)
             || subsetSumExists(rest, target - element);
         } 
      }
4

6 に答える 6

5

再帰コードは通常、リダクションの概念と結びついています。一般に、リダクションとは、何らかの変換を介して未知の問題を既知の問題に還元する手段です。

コードを見てみましょう。入力データセットの要素から特定の目標合計を構築できるかどうかを調べる必要があります。データセットが空の場合、ターゲットの合計を 0 と比較する以外に何もすることはありません。

それ以外の場合は、削減を適用しましょう。セットから数値を選択すると、実際には 2 つの可能性があります。選択した数値が求める合計に含まれるか、含まれないかです。ここには他の可能性はありません (すべての可能性をカバーすることが非常に重要です!)。実際、残りのデータのすべての可能性をカバーできる限り、どのデータ要素を選択しても問題ありません。

最初のケース: 数は合計に参加しません。検査対象の要素を含まないデータセットと同じターゲット合計を使用して、問題をより小さなものに減らすことができます。

2 番目のケース: 数が合計に参加します。検査対象の要素を含まないデータ セットと、要求された合計を数値の値だけ減らすことで、問題をより小さなものに減らすことができます。

これらのケースのいずれかが真であるかどうか、この時点ではわからないことに注意してください。答えを確実に知ることができる些細な空のケースに到達するまで、それらを減らし続けます。

これらの 2 つのケースのいずれかに当てはまる場合、元の質問に対する答えは true になります。それはまさに operator||が行うことです - そのオペランド (2 つのケースの結果) のいずれかが true の場合、true が返されます。

于 2012-11-30T09:52:08.887 に答える
3

||は論理 OR です。左から右に評価され、ショートサーキットされます。

これは、式A || BでAは , が最初に評価されることを意味します。の場合true、式全体がtrueであり、それ以上の評価は行われません。の場合、Aが評価され、式は の値を取得します。falseBB

あなたの例でAは、「セットの最初の要素を使用せずに同じ合計を取得してみてください」です。B「セットの最初の要素を使用すると、残りの合計が減少し、残りの要素でそれを取得しようとします。」

于 2012-11-30T09:40:05.487 に答える
2

最初にアルゴリズムを見てみましょう..

  • 基本ケース (つまり、再帰が終了するケース) は、セットが空の場合です。

  • それ以外の場合、プログラムは最初の要素を取り、それをセットから減算します。

  • これで、true かどうかを呼び出しsubsetSumExists(rest, target)てチェックし、true の場合は true を返します。そうでない場合は、呼び出し subsetSumExists(rest, target - element)て、返されたものを返します。

簡単に言えば、最初の呼び出しが false を返したsubsetSumExists(rest, target - element)場合にのみ、この呼び出しが行われます。subsetSumExists(rest, target)

{3,5} の小さなサンプル セットと合計 8 を使用して、このコードのドライ ランを試してみましょう。関数 sSE を呼び出します。

sSE({3,5}, 8) => "sSE({5}, 8) || sSE({5},(8-3))"

sSE({5}, 8)   => sSE({}, 8) || sSE({}, (8-5)) 

sSE({}, 8)    => false.. now will call sSE({}, (8-5))

sSE({}, 3)    => false.. now will call sSE({5}, (8-3))

sSE({5}, 5)   => sSE({}, 5} || sSE({}, (5-5))

sSE({}, 5)    => false.. now will call sSE({}, (5-5))

sSE({}, 0)    => true.. ends here and return true
于 2012-11-30T09:41:57.410 に答える
1

再帰を理解するには、再帰を理解する必要があります。そのためには、慎重に考える必要があります。

この特定のケースでは。

任意の場合:subsetSum(set, target)

  1. setが空かつtarget0 の場合、存在subsetSumします

  2. それ以外の場合は、 の最初の要素を削除しsetます。subdetSum(set, target)存在するか、または存在するかを確認subdetSum(set, target - removed_element)します (ステップ 0 を使用)

于 2012-11-30T09:41:11.767 に答える
1

セット減算は奇妙な構文に見えますが、要素の pop() を意味すると仮定します。

指数関数的ですが、可能なすべての組み合わせを見つけることで「機能」します。

この||ステートメントでは、LHS は現在の要素を含む合計であり、RHS はそれを除いた合計です。したがって、指数ツリーをたどると、各要素のすべての組み合わせがオンまたはオフになります。

ちなみに、指数関数的とは、30 個の要素がある場合、2 の 30 乗、つまり0x4000000010 億近くの組み合わせが生成されることを意味します。

もちろん、メモリが不足する可能性もあります。

解決策が見つかった場合、2^N のすべてのケースを実行できない可能性があります。解決策がない場合は、常にそれらすべてにアクセスします。

于 2012-11-30T09:41:13.600 に答える