前の関連記事：Python(15)アッカーマン関数の再帰を除去する
アッカーマン関数の再帰の除去で再帰の引数をすべて同じスタックに貯めていくという手法を学んだのでハノイの塔もその手法で非再帰にしてみます。
円盤を棒Aから棒Cに移す
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
if n == 1:
print("{}→{}".format(x, z))
else:
hanoi(n-1, x, z, y)
print("{}→{}".format(x, z))
hanoi(n-1, y, x, z)
hanoi(3, "A", "B", "C")
Python(13)ハノイの塔のときと違って棒ABCを引数xyzに対応させました。円盤の枚数が1枚のときは4行目で棒xから棒zに移動させています。
円盤が2枚以上あるときはn枚目の一番大きな円盤を移すことから考えます。
N枚目の円盤を移動させるためにはまずはその上にあるn-1枚の円盤を棒yに移さないといけません。
そのため6行目でn-1枚を棒xから棒ｙに移動させます。
関数hanoi()の引数のうちどの棒からどの棒に移すことになるのかは4行目と7行目に書いてある棒の関係で決まります。
このコードでは棒xから棒zに移すことになります。
つまり関数hanoi()の2番目の引数から4番目の引数に円盤を移動させるということです。
ということで6行目でn-1枚を棒xから棒ｙに移動させるためには1番目の引数を移動させる枚数n-1として、次の引数に移動元の棒、最後の引数に移動先の棒を入れればいいわけです。
7行目でn枚目をxからzに移動させます。
そして最後の8行目でyに移動させてあったn-1枚の円盤をyからzに移動させれば移動完了となるわけです。
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
if n == 1:
print("{}→{}".format(x, z))
else:
hanoi(n-1, x, z, y)
hanoi(1, x, y, z)
hanoi(n-1, y, x, z)
hanoi(3, "A", "B", "C")
n枚目の移動にもちゃんと関数hanoi()を使うとこう書けます。こうみるとハノイの塔は三重再帰になりますね。
非再帰に書き直すときもこのように書いたほうが理解しやすいです。
とりあえず再帰関数の引数をすべて同じスタックに詰め込んでいく手法で再帰を除去する
アッカーマン関数でも簡単に非再帰にできたこの手法に味を占めたのでハノイの塔でも同じ手法を使って再帰を除去します。
まずは引数の変化がどうなっているのか書き出してみます。
関数名はhanoi(n, "A", "B", "C")を略してh(n, A, B, C)にしています。
h(1, A, B, C)のときh(1, A, B, C)。
h(2, A, B, C)のとき
h(1, A, C, B)
h(1, A, B, C)
h(1, B, A, C)
これでとりあえずn=2までくればもうスタックに詰め込むものはないとわかりますね。
h(3, A, B, C)のときいよいよ再帰呼び出しが姿を現します。
灰色の引数はその上にあるピンク色の引数から計算できます。
青い色はn = 1のときに出力される結果です。
矢印の通りたどれば棒Aにある3枚の円盤を棒Cに移す手順が表示されていることがわかりますね。
とりあえずこれからだけで規則性をみつけるのは心許ないのでh(4, A, B, C)もやっておきます。
青色のところで動かす円盤を決定しておりすべての引数の組み合わせをスタックに収納するか円盤を動かすのに使った後はその引数はもう不要となります。
ということでh(4, A, B, C)から始まるととりあえずh(2, A, B, C)までスタックに収納します。
stack = [4, A, B, C, 3, A, C, B, 2, A, B, C]
ここでスタックの最後にいれた引数を使ってh(1, A, C, B), h(1, A, B, C), h(1, B, A, C)で円盤を動かします。
もうこれ以上h(2, A, B, C)の引数は使用しないのでスタックから削除します。
stack = [4, A, B, C, 3, A, C, B]
今度はh(3, A, C, B)に戻ってきますがnは1に変更してh(1, A, C, B)にします。
stack = [4, A, B, C, 1, A, C, B]
そしてh(1, A, C, B)を円盤に動かすのに使ったらその引数で次のh(2, C, A, B)を作っておきます。
h(1, A, C, B)の引数はもう使わないので削除します。
そして作っておいた次の操作に必要な引数h(2, C, A, B)をスタックに追加します。
stack = [4, A, B, C, 2, C, A, B]
今度はこのスタックの最後に入れた引数を使ってh(1, C, B, A), h(1, C, A, B), h(1, A, C, B)で円盤を動かします。
もうあとは同じ操作の繰り返しです。
もう使い終わった引数h(2, C, A, B)をスタックから削除して残っている引数のnを1に変更します。
stack = [1, A, B, C]
この引数を使って2回目の再帰の引数h(3, B, A, C)を作成しておきます。
h(1, A, B, C)を実行したらこれらをスタックから削除して、作っておいた次の操作に引数h(3, B, A, C)をスタックに追加します。
stack = [3, B, A, C]
もうあとの操作は繰り返しなのでスタックの変化のみ記載します。
stack = [3, B, A, C, 2, B, C, A]
stack = [3, B, A, C, 1, B, A, C]
stack = [3, B, A, C, 2, A, B, C]
stack = []
このようにスタックが空になったら終了です。
このスタックに引数を詰めていく方法はかなり汎用的に再帰の除去に応用できそうですね。
ここまでわかったらあとはwhile文で場合分けをするだけで非再帰のコードが完成します。
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z): # n枚の円盤を棒xから棒yへ移動させる。
stack = [n, x, y, z] # 引数を収納するスタックを生成。
while stack: # 引数があるときは継続。
n, x, y, z = stack[-4:] # 使用する引数を変数に戻す。
if n > 2: # 移動させないといけない円盤が3枚以上あるときは、n-1枚をxからyによけるための引数をスタックに加える。
stack.extend([n-1, x, z, y])
elif n == 2: # 移動させないといけない円盤が2枚のとき、2枚ともxからzに移動させる。
print("{}→{}".format(x, y)) # 小さいほうの上の円盤をまずyによけておく。
print("{}→{}".format(x, z)) # 2枚目の大きい円盤をzに移動させる。
print("{}→{}".format(y, z)) # よけておいた1枚目をzに重ねる。
del stack[-4:] # もうこれらの引数は使用しないので削除する。
if stack: # まだ引数が残っているということは3枚のときの処理が残っているということ。
x, y, z = stack[-3:] # 3枚のときの引数を取得。
stack.extend([1, x, y, z ]) # 2枚を移動させたあとの3枚目をxからzに移動させるための引数をスタックに加える。
elif n == 1: # 移動させないといけない円盤が1枚のとき。
print("{}→{}".format(x, z)) # xからzに移動させる。
if len(stack) > 4: # スタックに引数が5以上あるときはまだyによけたままになっている円盤があるということ。
n = stack[-8] # 今回1枚移動させる前に残っていた円盤の枚数を取得。
del stack[-8:] # そのときの引数を削除。
stack.extend([n-1, y, x, z]) # n-1枚をyからxに戻すための引数をスタックに加える。
else:
del stack[-4:] # yによけたままの円盤がないときは引数をすべて削除する。
hanoi(4, "A", "B", "C")
18行目はhanoi(1, "A", "B", "C")のときはスタックが5個以上の要素になるときがないのでそのときは後ろから4個の要素だけ削除するようにしています。
0 件のコメント:
コメントを投稿