0

同様の再帰呼び出しを持つ別の問題を一般化しています。私の場合、使用されている変数は文字列であるため、ループ内の再帰呼び出しの前後のコードを回避するために単純に値を渡すことはできません。これを反復ループに変える方法はありますか? ループ内の再帰呼び出しの前後のコードを変更して、この特定のインスタンスを機能させることはできないと想定してください。

このコードは、nums からの int の任意の組み合わせの合計がゼロになるかどうかをテストします。index の元の値は 0 で、max は特定のソリューションで合計したい数値の最大数です。

さらに明確にするために、数字は繰り返すことができるので、可能な組み合わせをすべて試すことはできません。無限にたくさんあるからです。

void findSolution(const vector<int>& nums, vector<int>& my_list, int& mySum,
int index, const int max)
{
    if(mySum == 0) {
        /* print my_list and exit(0) */
    }
    if(index < max) {
        for(int i = 0; i < nums.size(); ++i) {
            my_list.push_back(nums[i]);
            mySum += nums[i];
            findSolution(nums, my_list, mySum, index+1, max);
            mySum -= nums[i];
            my_list.pop_back();
        }
    }
}
4

1 に答える 1

0

手動スタックを維持します。

あなたの場合、再帰呼び出しの唯一の独立した状態は、 I の値と index の値です。インデックスは、再帰呼び出しの深さです。

スタックと呼ばれる int の標準ベクトルを作成し、最大に予約します。ループを while stack true に置き換えます。

ループに入る前に、スタックにゼロをプッシュします。

ループ内のタラを 3 つの部分に分けます。AB と C。A は再帰呼び出しの前、B は再帰呼び出し、C は後です。C には、元のコードでは C の後に発生するループの先頭のインクリメントが含まれています。

ループで最初に行うことは、スタックのトップが nums サイズ以上かどうかを確認することです。その場合、スタックをポップし、C を実行して、スタックが空でない限り続行します。空の場合は中断します。

次に、A を実行します。次に、スタックに 0 をプッシュし、スタック サイズが最大より小さい場合は続行します。次に、C を実行します。C コードの重複は、フラグ変数を使用して削除できます。

スタックの一番上が I への参照を置き換えることに注意してください。基本的には、同じスタックを手動で維持することで自動的にスタックを作成する再帰呼び出しを置き換えますが、保存できる絶対最小量のみを保存します。ループの開始は、再帰呼び出しの終了とループの開始の両方の役割を果たします。そのため、goto をなくすことができます。

試してみて、説明を見た後に心配してください。フラグ変数に関することは、コードが配置された後により意味があります。

于 2012-12-16T12:25:42.200 に答える