Python を使用してハノイの塔問題を実装する方法

序文

ハノイ塔問題は古典的な問題です。ハノイタワーとしても知られるハノイタワーは、インドの古代伝説に由来しています。ブラフマー神が世界を創造したとき、3本のダイヤモンドの柱を作り、1本の柱には64枚の金の円盤を下から上に大きさの順に積み上げました。ブラフマーはバラモンに、別の柱の上にある円盤を下から大きい順に並べ替えるよう命じました。また、小さな円盤では常に円盤を拡大することはできず、3 つの柱の間で一度に 1 枚の円盤しか移動できないことも規定されています。操作方法を尋ねますか？

1. まず再帰とは何なのかについて話しましょう。

私自身の理解は、自分自身の問題のサイズを、縮小できない点まで縮小し続けることです。 (再帰の終了条件に到達) 次に、小さな問題を解決し始めます。小さな問題を 1 つずつ解決すると、大きな問題が解決されます (再帰が戻ります)

2. つまり、

元の問題は、より小さな元の問題に縮小され、その後、より小さな元の問題が解決され、それによって元の大きな問題が解決されます。

3. プロセスは次のとおりです:

規模を縮小し、小さいサイズから解決し、再帰して元の問題を解決します。 ！ ！

4. 再帰の鍵は次のとおりです:

(1) 再帰的な終了条件があります。

(2) 問題のサイズを小さくし、再帰の終了条件に近づけるためにそれ自体を継続的に呼び出します。

ハノイ塔問題

1. 問題の説明

A、B、Cという名前の3つの柱があります。最初、柱 A には n 個のディスクがあり、それらは下から上にあり、ディスクのサイズは大きいものから小さいものまであります。移動および配置の際は、小さなプレートを大きなプレートの上に置く必要があります。ルールを守りながら、柱 A にあるすべてのプレートを柱 C に移動します。移動中に柱 B を使用できますが、移動中は小さなプレートが大きなプレートの上にあることを確認する必要があります。 ！ ！引っ越しの手続きを印刷してみてはいかがでしょうか？

2. 問題分析の再帰的プロセス:

(1) C ## を使用して、上位 n-1 個のプレートを A から B## に移動します。 ##(2) 下のプレートを A から C

に移動します。 (3) 上の n-1 個のプレートを B から C

に再帰的に移動します。 終了条件:

問題プレートの数が 0 の場合、スケールはプレートの数が 0 になると移動する必要がないためです。 ！ ！

3. コード (Python)

# coding:utf-8

"""
    n为初始时A柱上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""


def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("盘子从%s移动到%s" % (a, c))
        hanoi(n-1, b, a, c)



hanoi(3, "A", "B", "C")

4. 結果表示

以上がPython を使用してハノイの塔問題を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。