ハノイの塔のプログラムを Python で書く方法

次のように再帰を使用するハノイの塔の Python コードです。

def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将 n-1 个盘子从源柱子移动到辅助柱子
        hanoi(n-1, source, auxiliary, target)
        
        # 将第 n 个盘子从源柱子移动到目标柱子
        print(f"Move disk {n} from {source} to {target}")
        
        # 将 n-1 个盘子从辅助柱子移动到目标柱子
        hanoi(n-1, auxiliary, target, source)


# 测试
n = 3  # 盘子的数量
hanoi(n, 'A', 'C', 'B')

なお、このコードは移動を１手ずつ印字していますが、今後移動の記録として利用する場合は、print文をリストへの追加命令に差し替えることで可能です。

ハノイの塔問題を解くhanoi関数では、4つの引数を使用します。nは移動する円の枚数、sourceは最初の柱、targetは移動先の柱、auxiliaryは補助的な柱です。この関数は、最初n-1枚の円をソースの柱から補助的な柱へ移動させ、次にn番目の円をソースの柱から移動先の柱へと移動させ、最後にn-1枚の円を補助的な柱から移動先の柱へと移動させます。この処理は関数自体を再帰的に呼び出すことで実現されます。

3 つの円盤のあるハノイの塔の問題をテスト部分で hanoi 関数に渡し、起点のポールを「A」、終点のポールを「C」、補助のポールを「B」と名づけます。