組み合わせの列挙の再帰プログラム

再帰 全探索 | アルゴリズムとデータ構造 | Aizu Online Judge」で組み合わせの列挙をする再帰プログラムがあったのでC++で、記事の通り書いてみたけれど、ちょっと動きが分からなかったので修正して、詳細な動きを書いてみました。

AOJのコードの場合は、以下のように、配列がゼロ初期化されていて、rec関数から戻るときにS[i]=1でオン状態になったものは、必ずS[i]=0でオフに戻すという記述のため、※の部分のS[i]の値がぱっと見分からない。

rec関数の最後で、S[i]=0でゼロに戻しているので、基本的には以下と同等です。

関数の最初でリセットするか呼び出し後の最後でリセットするかの違いです。上記のコードで一度ステップ実行してしまえば理解が深まります。

ステップ実行してみる

要素数が3の組み合わせ一覧をメモ帳で書きながらステップ実行すると、以下のようになります。rec呼び出しでprintしない場合は、必ずS[i]=0となるため上手く動作します。

出力

 

JavaScriptで実装

Node.jsで実行

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA