ハノイの塔
この演習では、再帰アルゴリズムを使ってハノイの塔パズルを作成します。このゲームの目的は、3本の棒のうち1本にあるすべての輪を別の棒に移動させることです。ルールは以下のとおりです。
- 一度に動かせる輪は1つだけです。
- スタックの一番上にある輪のみを取り出し、別のスタックの上に置けます。
- 小さい輪の上に大きい輪を置くことはできません。
この4つの輪と「A」「B」「C」と名付けられた3本の棒を使ったゲームを実行するアルゴリズムがあります。このコードには2つのバグがあります。実行すると、最大再帰深度を超えてコンソールがクラッシュしてしまいます。バグを見つけて修正してみましょう。
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
演習の手順
- ベースケースを修正してください。
hanoi()関数の呼び出しを修正してください。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def hanoi(num_disks, from_rod, to_rod, aux_rod):
# Correct the base case
if num_disks >= 0:
# Correct the calls to the hanoi function
hanoi(num_disks, from_rod, aux_rod, to_rod)
print("Moving disk", num_disks, "from rod", from_rod,"to rod",to_rod)
hanoi(num_disks, aux_rod, to_rod, from_rod)
num_disks = 4
source_rod = 'A'
auxiliar_rod = 'B'
target_rod = 'C'
hanoi(num_disks, source_rod, target_rod, auxiliar_rod)