schedule2018-08-02

再帰関数を使ってハノイの塔を解く | Python

問題

hanoi

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

  • 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
  • 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
  • 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

引用:Wikipedia - ハノイの塔

解答

tower_of_hanoi.py

def tower_of_hanoi(n, from_stack, to_stack, tmp):
    """
    from_stackからto_stackへディスクを動かす。
    """
    if n == 1:
        # 1枚の円盤なら移して返す
        print(f"Move {n} disck from {from_stack} to {to_stack}.")
        return
    # 上からn-1番目の円盤をAからCへ、Bを中間に使う
    tower_of_hanoi(n-1, from_stack, tmp, to_stack)
    # 残りの円盤をAからCへ
    print(f"Move {n} disck from {from_stack} to {to_stack}.")
    # 上からn-1番目の円盤をBからCへ、Aを中間に使う
    tower_of_hanoi(n-1, tmp, to_stack, from_stack)

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

出力

$ python tower_of_hanoi.py
Move 1 disck from A to C.
Move 2 disck from A to B.
Move 1 disck from C to B.
Move 3 disck from A to C.
Move 1 disck from B to A.
Move 2 disck from B to C.
Move 1 disck from A to C.

実行回数は2^n-1回です。

小話

『ハノイの塔』は1883年にエドゥアール・リュカによって考案されたパズルです。

アシェット・コレクションズ・ジャパンが2005年9月に発行した雑誌「パズルコレクション」の創刊号の付録がこのパズルでした。


Pythonを初めて学ぶ方へオススメの本です!
Mac、Windows環境の整え方から手を動かして実行できるようになっていきます。

合わせてオンライン学習も進めるとより理解が深まると思います。

Pythonコース

Python3の入門オンライン講座