ハノイの塔の再帰呼出しの引数を穴埋めする

解説

ハノイの塔の再帰アルゴリズムは次の3段階で構成される。 (1) 上の n-1 枚を src から work へ移動する(dst を作業用として使う) (2) src に残った最大の円盤を dst へ移動する(1回の移動) (3) work にある n-1 枚を dst へ移動する(src を作業用として使う) したがって、 ・〔 a 〕= n - 1, src, work, dst(段階1に対応) ・〔 b 〕= n - 1, work, dst, src(段階3に対応) が正解である。 【トレース: hanoi(3, "A", "C", "B")】 hanoi(3,A,C,B) hanoi(2,A,B,C) … 上2枚をAからBへ hanoi(1,A,C,B) … 上1枚をAからCへ hanoi(0,...) → return log追加: "A→C" … log[1] hanoi(0,...) → return log追加: "A→B" … log[2] hanoi(1,C,B,A) … 上1枚をCからBへ hanoi(0,...) → return log追加: "C→B" … log[3] hanoi(0,...) → return log追加: "A→C" … log[4](最大円盤の移動) hanoi(2,B,C,A) … 上2枚をBからCへ hanoi(1,B,A,C) … 上1枚をBからAへ hanoi(0,...) → return log追加: "B→A" … log[5] hanoi(0,...) → return log追加: "B→C" … log[6] hanoi(1,A,C,B) … 上1枚をAからCへ hanoi(0,...) → return log追加: "A→C" … log[7] hanoi(0,...) → return 結果: log = {"A→C", "A→B", "C→B", "A→C", "B→A", "B→C", "A→C"} これは問題文に示された期待結果と一致する。

選択肢ごとの解説

ア

正解。1回目の再帰で上の n-1 枚を src から work へ(dst を作業用として)移動し、src の最大円盤を dst へ移した後、2回目の再帰で work にある n-1 枚を dst へ(src を作業用として)移動する。ハノイの塔の正しいアルゴリズムである。

イ

不正解。1回目の再帰で移動先を dst、作業用を work としているため、n-1 枚を dst へ直接移動しようとしてしまう。その後 src の円盤も dst へ移動するので、大きい円盤の上に小さい円盤が既にある状態になり、ハノイの塔の規則に反する手順が記録される。

ウ

不正解。2回目の再帰で移動先を src、作業用を dst としているため、n-1 枚を work から src へ戻してしまう。結果として円盤が dst にすべて移動しない。

エ

不正解。1回目と2回目の再帰呼出しの役割を逆にしている。1回目で work から dst へ移動しようとするが、最初は work に円盤がないため正しい手順にならない。

オ

不正解。両方の再帰呼出しで移動先杭と作業用杭を取り違えている。1回目で n-1 枚を dst に直接移動し、2回目で dst から src に戻す形になるため、円盤が正しく移動しない。

カ

不正解。再帰呼出しの第1引数が n のままで減少しないため、n ≧ 1 のとき無限再帰に陥り処理が終了しない。再帰では n - 1 として問題のサイズを小さくする必要がある。

キ

不正解。2回目の再帰で移動元を src としているが、最大の円盤を dst へ移した後は、n-1 枚の円盤は work にある。移動元を src と誤解すると、既に空になった杭から移動しようとする手順が生成される。

登録なしで解ける問題は、これで最後です。続きは無料登録で、演習用の300問を期限も上限もなく解けます。登録すると解いた結果が残り、間違えた問題は日をおいて復習に出ます。