Python(13)ハノイの塔

前の関連記事：Python(12)二重再帰の再帰を除去する

二重再帰の例といえばハノイの塔 - Wikipediaです。教養のコンピュータアルゴリズムにも載っています。これは数値を得るものでなく手順を表示していくものなので非再帰にする意味を感じないのですよね。(でもPython(16)ハノイの塔の再帰を除去するでやりました。）

Aの棒からCの棒へn枚の円盤を移す

円盤は大小の順には詰めないので棒Aから棒Cへ移動させるのに作業用棒Bを介します。

# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
    if n == 1:
        print("{}→{}".format(x, y))
    else:
        hanoi(n-1, x, z, y)
        print("{}→{}".format(x, y))
        hanoi(n-1, z, y, x)
hanoi(3, "A", "C", "B")

(2014.6.22追記。4行目と7行目に全角文字「→」を使っているので先頭行に文字コードの定義を追加しました。理由はPyCharm(1)デバッグ時にUnicodeDecodeErrorがでるへ。）

とりあえず教養のコンピュータアルゴリズムに載っているJavaScriptのコードをPythonで書いてみました。

zが作業用棒なのでこれをBにします。

xからyへ棒が移動しますのでxをA、yをCにします。

これを実行すると円盤を移す手順が出力されます。
A→C
A→B
C→B
A→C
B→A
B→C
A→C
n = 3 で7手順も必要です。

n = 19 で実行するとPyCharmに、結果が多すぎて表示できない、といわれます。

円盤がn枚のときの手順の数 $$$T_{n}$$$は$$$T_{n}=2^{n}-1$$$になります。

n = 19 だと手順数は524287になります。

これは計算回数ではなくて円盤を移動させるのに必要な手順の数なので再帰のプログラムを非再帰に変換しても手順数は減りません。

もう少し手順を直感的にみやすいように出力を工夫してみました。

# -*- coding: utf-8 -*-  
def output(x, y):
    lst = [x, y]
    if lst == ["A", "B"]:
        print("{}→{}".format(*lst))
    elif lst == ["A", "C"]:
        print("{}→ 　{}".format(*lst))
    elif lst == ["B", "A"]:
        print("{}←{}".format(*reversed(lst)))
    elif lst == ["B", "C"]:
        print(" 　{}→{}".format(*lst))
    elif lst == ["C", "A"]:
        print("{}　 ←{}".format(*reversed(lst)))
    elif lst == ["C", "B"]:
        print(" 　{}←{}".format(*reversed(lst)))
def hanoi(n, x, y, z):
    if n == 1:
        output(x, y)
    else:
        hanoi(n-1, x, z, y)
        output(x, y)
        hanoi(n-1, z, y, x)
hanoi(5, "A", "C", "B")

n = 5 のときで以下の結果が出力されます。

31手順になります。

A→ 　C
A→B
 　B←C
A→ 　C
A←B
 　B→C
A→ 　C
A→B
 　B←C
A　 ←C
A←B
 　B←C
A→ 　C
A→B
 　B←C
A→ 　C
A←B
 　B→C
A→ 　C
A←B
 　B←C
A　 ←C
A←B
 　B→C
A→ 　C
A→B
 　B←C
A→ 　C
A←B
 　B→C
A→ 　C

PyCharmの出力画面ではA、B、Cの列が揃っているのですが、ウェブブラウザでみるとちょっとずれてしまいますね。

本当にこの手順で移せるかどうかは以下のページで実際に手を動かして確認することができます。

ハノイの塔 ( パズル ):無料Flashゲーム

ハノイの塔が100段の時、ゴールできるまでの最短時間を計算してみた

n = 5 は最後までちゃんとできました。

n = 8 のときはもう途中で嫌になってやめてしまいました。

255手順にもなりますので、、、

こんなのがオモチャとして売っています。

10枚の円盤を移すには1023手順が必要なのですけど、答えをみずにできる人はいるのでしょうかね。

次の関連記事:Python(14)アッカーマン関数のお勉強