ハノイの塔の解き方(正道)
よく再帰処理の題材として取り上げられるハノイの塔。
「『目的のディスク』を動かすために『目的のディスクの上のディスク』を動かす」
という流れになるため、再帰処理で解かれることが多いです。
詳細は省きますが、だいたいは
・「ディスクを動かす関数」を書く。
・関数の引数で「動かすディスク」を受け取る。
・動かすディスクの上に他のディスクが乗っている場合、「（動かしたい）ディスクを動かす関数」から「（動かしたいディスクの上の）ディスクを動かす関数」を呼ぶ。
という処理になります。
問題点
ハノイの塔は段数が増えると、文字通り指数関数的に動かす回数が増えてしまいます。
具体的には「(2^ディスクの数)-1」回の移動が必要になり、
これは大雑把なイメージとして10段増えるごとにだいたい1000倍です。
1000段のハノイの塔を解くにはだいたい10^300回の移動が必要となりますし、
100兆回動かした後の状態を作るには100兆回のループが必要です。
1億ループ/秒としても計算に11.5日ほど掛かってしまって現実的ではありませんし、
まなぶくんも再来週までは待てません。
ディスクの状態を直に計算する
これでは悔しいので、たくみくんはディスクの状態を直に計算することにしました。
では何がわかればディスクの状態を直に計算できるでしょうか？
- それぞれのディスクは何回ずつ動くのか
- それぞれのディスクはどんな順番で棒の間を動くのか
がわかれば位置を特定できそうです。
ここから考え方、解き方を書いていきますが
答えを全て書いてしまうのもアレなので、少しずつぼやかして書いていきます。
それぞれのディスクがいつ動くのか考える
N段のハノイの塔で、N段目（最下段）のディスクを動かすのはどのタイミングでしょうか？
2〜4段くらいの低いハノイの塔で動かすディスクの順番を見てみましょう。
2段：1→[2]→1
3段：1→2→1→[3]→1→2→1
4段：1→2→1→3→1→2→1→[4]→1→2→1→3→1→2→1
N段目（最下段）を動かすのはちょうど真ん中でした。
ハノイの塔を動かす流れを大雑把に以下の3段階で考えると
- N-1段目までのディスク群を隣に避ける
- N段目のディスクを動かす
- N-1段目までのディスク群をN段目のディスクに乗せる
1と3に掛かる手数が同じであるため、N段目のディスクを動かすのが真ん中になります。
具体的にはceil(((2^N)-1)/2)手目、もしくは(2^(N-1))手目です。
ではN-1段目のディスクを動かすタイミングはどこでしょうか？
2段：[1]→2→[1]
3段：1→[2]→1→3→1→[2]→1
4段：1→2→1→[3]→1→2→1→4→1→2→1→[3]→1→2→1
NがいくつでもN-1段目を動かす回数は同じ2回でした。
これは「一旦横に避ける」「N段目のディスクに乗せる」の2回しか動かないからです。
タイミングですが、N段目を「だいたい1/2の場所」と表現するなら、
N-1段目は「だいたい1/4の場所」と「だいたい3/4の場所」で動きました。
これはN段目が真ん中に来たのと同じ理屈で
「N-2段目までを隣に避ける→N-1段目を動かす→N-2段目までを上に乗せる」をしているためですが、
N-1段目はN段目を動かす前後で1回ずつ動かしているので「だいたい(1/2の1/2)=1/4」と「だいたい(1/2+(1/2の1/2))=3/4」の2箇所になります。
ここまでくればあとは同じ要領でN-2段目、N-3段目も考えることが出来るのではないでしょうか。
翻って、それぞれのディスクは何回ずつ動くのかを考える
前段で「いつどのディスクを動かすのか」がわかりました。
ここから「どのディスクが何回ずつ動くのか」を考える必要があります。
N段目のディスクを動かす回数は簡単です。
合計の動かす回数をxとした場合、
-
x<ceil(((2^N)-1)/2)であれば0回 -
x>=ceil(((2^N)-1)/2)であれば1回
です。
ではN-1段目はどうでしょう。
-
x<だいたいN/4であれば0回 -
x>=だいたいN/4 かつ x<だいたいN*3/4であれば1回 -
x>=だいたいN*3/4であれば2回
N段目と比べ少し条件が増えましたが計算で求められそうです。
同じ要領でN-2段目、N-3段目、N-4段目・・・と求めていくことも出来そうですが、
これをループなりで表現するのはなかなか面倒です。
そこで少し違うアプローチでディスクの動く回数を求めてみます。
y段目は何回動くのかを観察する
この手の法則を見つけるには観察が大切です。
まずは1段目から見てみましょう。
2段：[1]→2→[1]
3段：[1]→2→[1]→3→[1]→2→[1]
4段：[1]→2→[1]→3→[1]→2→[1]→4→[1]→2→[1]→3→[1]→2→[1]
なんだか2回に1回くらいは1段目が動いていそうです。
次は2段目。
2段：1→[2]→1
3段：1→[2]→1→3→1→[2]→1
4段：1→[2]→1→3→1→[2]→1→4→1→[2]→1→3→1→[2]→1
続いて3段目。
2段：1→2→1
3段：1→2→1→[3]→1→2→1
4段：1→2→1→[3]→1→2→1→4→1→2→1→[3]→1→2→1
最後に4段目。
2段：1→2→1
3段：1→2→1→3→1→2→1
4段：1→2→1→3→1→2→1→[4]→1→2→1→3→1→2→1
どうですか？見えてきましたか？
なんだかだんだん半分くらいになっているような気がしてきましたね。
それぞれのディスクはどんな順番で棒の間を動くのかを考える
動く回数はここまでとして、次はどんな順番で棒の間を動くのかを考えていきます。
ディスクを上から[1]〜[2]（2段のハノイの塔）、棒を左から[1]〜[3]として棒[1]から棒[3]に移動した場合
それぞれのディスクの動きは以下の通りです。
ディスク[1] 棒[1]->[2]->[3]
ディスク[2] 棒[1]->[3]
3段以上についてはほぼネタバレなので割愛します。
考えて書き出してみてください。
再帰的に求めるハノイの塔を組んでログに吐かせるのが楽です。
ヒントとしては、こちらもN段目から見た位置を基準に法則が決まります。
実装
といっても重要な部分はぼかしているので、実装は骨組みだけです。
お勉強中のPythonで。
def get_hanoi(N, X):
hanoi = [['棒[1]'],['棒[2]'],['棒[3]']] # ハノイの塔を入れる
remaining = X # 残りの動かす回数
# それぞれのディスクの動く回数を求める
while(remaining):
# いずれかの段の動く回数を求める
# 残りの動かす回数から引く
# それぞれのディスクの位置を求める
for i in range(N):
# ディスクの番号から動かす回数を求める
# 動かす回数と動かす順番から棒の位置を求める
return '\n'.join([ ' '.join([str(i) for i in l]) if len(l) else '-' for l in hanoi ])
if __name__=='__main__':
print(get_hanoi(1000, 100*10**12)) # 10^12で兆
今回はループを2つに分けましたが、1つにしてしまっても良いと思います。
書き方次第ですが、10行から20行程度の処理になります。
結果
棒[1] 1000 999 … 50 49 48 45 44 41 36 35 32 31 30 23 22 21 20 17 16
棒[2] 47 42 29 18 15
棒[3] 46 43 40 39 38 37 34 33 28 27 26 25 24 19 14 13 12 11 10 9 8 7 6 5 4 3 2 1
実に953枚のディスクは動くことなく棒[1]に留まり続けました。
最高でディスク[47]まで動いています。
結果の検証（長文、4行目以降は読み飛ばし推奨）
ディスク[47]が動くのは2^46 = 70兆3687億4417万7664手目、
ディスク[48]が動くのは2^47 = 140兆7374億8835万5328手目なので、
ディスク[47]まで動いているのは正しそうです。
ディスク[47]が棒[1]から棒[3]に動いた時、ディスク[46]から[1]は全て棒[3]に収まっていたはずです。
ディスク[47]の後の動きを考えると、ディスク[46]は棒[3]から動かず、ディスク[45]は棒[3]から棒[1]に動いています。
ディスク[46]が動くのは2^45 = 35兆1843億7208万8832手目なので、ディスク[47]の70兆手と合わせると100兆手を超えてしまうため、動きませんでした。
ディスク[45]が動くのは2^44 = 17兆5921億8604万4416手目なので、70兆手と合わせても100兆手に収まりますね。
もう1つくらい見ると、
ディスク[45]が棒[3]から棒[1]に動いた時、ディスク[44]から[1]は全て棒[2]に収まっていたはずです。
ディスク[45]の後の動きを考えると、ディスク[44]は棒[2]から棒[1]に動いています。
同じくディスク[44]が動いた時、ディスク[43]から[1]は全て棒[3]に収まっていたはずです。
ディスク[44]の後の動きを考えると、ディスク[43]は棒[3]から動かず、ディスク[42]は棒[3]から棒[2]に動いています。
ディスク[44]が動くのは2^43 = 8兆7960億9302万2208手目。
ディスク[43]が動くのは2^42 = 4兆3980億4651万1104手目。
ディスク[42]が動くのは2^41 = 2兆1990億2325万5552手目。
[44][43]が動くには「70兆+17.5兆+8.8兆+4.4兆=100.7兆」なのでオーバーします。
[44][42]が動くには「70兆+17.5兆+8.8兆+2.2兆=98.5兆」なので収まります。
といった具合。
さて、上記のような考え方で「動いた」ディスクを全て挙げると
[47][45][44][42][40][39][38][37][34][33][29][23][22][21][20][18][15]
になります。
動いた判定の仕方は面倒で、
N段目が動かず棒[a]に居る場合、N-1段目も動く前は棒[a]に居る。
N-1が棒[a]なら動いていない。
N-1が棒[b]なら[a]->[b]に動いた。
N-1が棒[c]なら[a]->[c]に動いた。
N段目が棒[a]->[b]と動いて棒[b]に居る場合、N-1段目は動く前は棒[c]に居る。
N-1が棒[a]なら[c]->[a]に動いた。
N-1が棒[b]なら[c]->[b]に動いた。
N-1が棒[c]なら動いていない。
というのをN段目から1段目まで順に追っていっています。
(もっと良い方法あったら教えてください・・・。)
動いたディスクそれぞれの手数は
ディスク[47] 70368744177664
ディスク[45] 17592186044416
ディスク[44] 8796093022208
ディスク[42] 2199023255552
ディスク[40] 549755813888
ディスク[39] 274877906944
ディスク[38] 137438953472
ディスク[37] 68719476736
ディスク[34] 8589934592
ディスク[33] 4294967296
ディスク[29] 268435456
ディスク[23] 4194304
ディスク[22] 2097152
ディスク[21] 1048576
ディスク[20] 524288
ディスク[18] 131072
ディスク[15] 16384
この合計がぴったり100兆（1e+14）になりますので、結果の検証としては問題ないのではないでしょうか。
「直に計算する」が使える場面
再帰的に処理を回して状態を再現するような処理は、割と直に計算出来る場合が多いです。
一定の法則で文字や数字を再帰的に組んで指定された桁数を取ってくるような問題などで使えますが、
問題ごとに法則を見つけてそれに合わせた計算を行う必要があります。
その準備のために、まずは再帰で組んで結果を観察したり、
直に計算した結果の検証をしたりするため、結局は再帰で組めるようになる必要があります。
なので、ループ回数がそれほど多くない条件で求めるのであれば、再帰処理に軍配が上がると思います。
結論
「100兆回程度じゃ47枚くらいしかうごかせねーな！」と言ってあげましょう。