"BOKU"のITな日常

BOKUが勉強したり、考えたことを頭の整理を兼ねてまとめてます。

Pythonで何もしない(pass)と再帰処理/ハノイの塔の解法アルゴリズム

f:id:arakan_no_boku:20190223210405j:plain

目次

はじめに

今回はハノイの塔の解を求めるプログラムをPythonで書いてみます。

この中で。

という2つのケースがでてきて、自分の勉強用にちょうどいいかな・・と思ったので。

ハノイの塔

有名なパズルです。

下の図のように、3本の柱があって、一番左端(A)に何枚か(例では3枚)の円盤がささっているところからスタートします。

f:id:arakan_no_boku:20170303232100j:plain

 

そこから、円盤を1枚ずつ動かして、真ん中の柱(B)に移すパズルです。上記の3枚のパターンなら、こうなればOKです。

f:id:arakan_no_boku:20170304131001j:plain

 見てのとおり、円盤は図のように全部大きさが違い、下の段ほど大きい円盤になってます。そして、動かす途中であっても、小さい円盤の上に、大きい円盤をのせてはいけないという縛りがあります。 

これがルールです。

円盤の数が3枚なら「3ハノイ」、4枚なら「4ハノイ」のように、円盤の数+ハノイで呼ぶのが一般的です。

ハノイの塔(3ハノイ)を自力でやってみる

このサイトによると、「2のN乗 -1(Nは円盤の数)」回で解けるのが最短手順とのことです。

mathtrain.jp

つまり。 

円盤3枚なら手順は7回(2の3乗-1)で解けるということです。

自力でやってみると。

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

となりました。

確かに7回です。 

ハノイの塔を解くアルゴリズム

ハノイの塔には、問題を解くアルゴリズムが存在するようです。

上記のサイトの記事よれば。

f:id:arakan_no_boku:20170304002645j:plain

おー。

再帰的なアルゴリズムがあるということは、プログラムで解けるということですね。

pythonハノイの塔を解く

早速、pythonでやってみました。

def hanoi(n, a, b, c):
    hanoi_imp(n, a, b, c)


def hanoi_imp(n, a, b, c):
    if n <= 0:
        pass
    else:
        hanoi_imp(n - 1, a, c, b)
        print(a + u" → " + b)
        hanoi_imp(n - 1, c, b, a)


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

 

引数のnに円盤の枚数をわたし、a,b,c には、表示用にA,B,Cの文字を渡します。 

再帰呼び出しをするところで、引数で渡されてa,b,cの位置を入れ替えないといけない所が、ちょっと工夫が必要でしたが、ほぼ、まんまです。

この中で「pass」と書いているところが「何もしない」処理です。

あと、hanoi_imp()の中で、自分自身(hanoi_imp)を呼び出してます。

これが再帰処理です。

このテクニックを使うと「複雑に行われる処理を簡単に書くことができる」メリットがあるのですけど、慣れないと、結果がまったくイメージできない・・という悩ましいところがあります。

ここを深堀すると、大変面倒くさいのでここでは「Pythonでも再帰処理はふつうに使える」ということが確認できた・・ということでよしとしときます。

さて。

これを、math_hanoi.py という名前で保存して実行してみます。

python math_hanoi.py

結果は。

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

おーー。

自力でやった正解と同じです。

とりあえず、5ハノイまではプログラムの出力を見ながら、実際にやってみましたが、OKでした。 

ただ、6ハノイ以上は試してません。すいません。たぶん、大丈夫と思うのですが、もし、バグとかあったら、ごめんなさい。

ではでは。