h 1 = 1
h n = h (n-1) + 1 + h (n-1)
円盤の枚数が(n-1)のときの手順数がわかれば、円盤の枚数がｎのときの手順数はいつでも計算できる、ということから再帰的に書くことができます。
計算してみます。
$ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help
Prelude> :l h.hs
[1 of 1] Compiling Main ( h.hs, interpreted )
Ok, modules loaded: Main.
*Main> h 1
1
*Main> h 2
3
*Main> h 3
7
*Main>
枚数が多くなると非常に時間がかかるようになります。
*Main> map h [1..64]
[1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,^CInterrupted.
*Main>
これはこのコードの構造がHanoiの塔を解くプログラムと同じだからです。
（円盤を動かすたびにカウントしているのと同じ）
このようなときはfold系の関数を利用します。
*Main> scanl (\x _ -> x + 1 + x) 0 [1..64]
[0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823,2147483647,4294967295,8589934591,17179869183,34359738367,68719476735,137438953471,274877906943,549755813887,1099511627775,2199023255551,4398046511103,8796093022207,17592186044415,35184372088831,70368744177663,140737488355327,281474976710655,562949953421311,1125899906842623,2251799813685247,4503599627370495,9007199254740991,18014398509481983,36028797018963967,72057594037927935,144115188075855871,288230376151711743,576460752303423487,1152921504606846975,2305843009213693951,4611686018427387903,9223372036854775807,18446744073709551615]
(0.02 secs, 709,992 bytes)
*Main>
最初のコードが非効率だったのは二股再帰しているからです。
次のように書き換えればよい。
h2 1 = 1
h2 n = h2 (n-1) * 2 + 1
*Main> h2 64
18446744073709551615
(0.02 secs, 112,688 bytes)
*Main>
円盤の数がN枚のときのハノイの塔は、２のN乗マイナス１回の動きで解けることが知られています。
Prelude> 2^64-1円盤の数がN枚のときのハノイの塔は、２のN乗マイナス１回の動きで解けることが知られています。
18446744073709551615
「最初に一番下にあった円盤はただ１回、元の位置から目的地に移動しているだけ」
ということが関係しています。
つまり円盤が何枚積まれていても一番下の円盤が持ちうる状態は２つ。
です。
すべての円盤についてそうですので、N枚の円盤が持ちうる状態をすべて数え上げれば
２のN乗になります。
一番最初の状態を加えていないので
２のN乗マイナス１
です。64枚の円盤に上から順番に番号をつけます。一番上が1番一番下が６４番です。 ６４番はただ一回A塔からB塔に移動しているだけです。 つまり６４番の持ちうる状態は２つ。 つぎに６３番から１番までの動きををみてみますと、６４番を移動させるために、一旦全部C塔に移動しています。 このとき６３番だけをみますと、ただ一回A塔からC塔に移動しているだけです。 つまり６３番の持ちうる状態は２つ。 で６４番がB塔に移動したあと、すべてB塔に移動するのですが、やはり６３番はただ一回C塔からB塔に移動しているだけです。 このとき、６３番の持ちうる状態は２つです。 つまり６４番の持ちうる状態それぞれについて６３番が持ちうる状態は２つづつ。 つまり２ｘ２、２の２乗です。 ６２番については面倒なので省略しますが、同じことが言えます。 ハノイの塔のルールにしたがって(最小手順で）動かした場合、自分より下の円盤が持ちうる全ての状態それぞれについて２つづつの状態を持ちうるということです。 ６４番と６３番が持ちうる状態が２ｘ２でしたので、２ｘ２ｘ２、２の３乗。 一般に
ハノイの塔のルールにしたがって（最小手順で）円盤を動かした場合、 N番目までの円盤が持ちうる状態は ２の（Nマイナス１）乗 かける ２ つまり ２のN乗です。 １番の円盤は下から数えて６４枚目ですので、 ２の６４乗 最初の状態を勘定にいれないので、 ２の６４乗マイナス１
（これは６４bitのメモリーが０〜18446744073709551615までの整数を表わせることと等価です。）
さてソロリ新左衛門がなぜ大金持ちになったかですが、
決して「戦場でサンタフェを売った。」からではありません。
有名なのは将棋盤と米粒の話しです。
最初のマスに１粒、次に２倍の２粒、さらに２倍の４粒・・・米粒をのせていきます。
将棋盤は９ｘ９の８１マスなので、
*Main> scanl (\x _ -> x * 2) 1 [2..(9*9)]
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904,9223372036854775808,18446744073709551616,36893488147419103232,73786976294838206464,147573952589676412928,295147905179352825856,590295810358705651712,1180591620717411303424,2361183241434822606848,4722366482869645213696,9444732965739290427392,18889465931478580854784,37778931862957161709568,75557863725914323419136,151115727451828646838272,302231454903657293676544,604462909807314587353088,1208925819614629174706176]
(0.03 secs, 1,033,184 bytes)
ソロリ新左衛門が求めたのはその合計ですので
*Main> sum it
2417851639229258349412351
(0.01 secs, 109,800 bytes)
*Main>
2杼4178垓5163京9229兆2583億4941万2351粒です。
ある方の計算によると１俵は2666666粒なのだそうです。
ある方の計算によると１俵は2666666粒なのだそうです。
とすると2杼4178垓5163京9229兆2583億4941万2351粒は約９０京俵。
日本の現在の年間生産量は１億数千万俵。
同様の話しがインドの王様とチェスの発明者の話しとして伝わっています。
こちらはチェス盤と麦です。
*Main> scanl (\x _ -> x * 2) 1 [2..(8*8)]
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904,9223372036854775808]
(0.02 secs, 685,632 bytes)
*Main> sum it
18446744073709551615
1844京6744兆737億955万1615粒
なぜかハノイの塔の解き手順と一致しました。
将棋盤やチェス盤ですのでこの程度の数でおさまっていますが、これが囲碁の盤だったらどうなるでしょうか。
*Main> sum $ scanl (\x _ -> x * 2) 1 [2..(18*18)]
34175792574734561318320347298712833833643272357706444319152665725155515612490248800367393390985215
(0.02 secs, 276,408 bytes)
*Main>
34,175,792,574,734,561,318,320,347,298,712,833,833,643,272,357,706,444,319,152,665,725,155,515,612,490,248,800,367,393,390,985,215
サイエンティフィック・ノーテーションでは
34,175,792,574,734,561,318,320,347,298,712,833,833,643,272,357,706,444,319,152,665,725,155,515,612,490,248,800,367,393,390,985,215
3.417579257473456e97
３のあとに０が９７個並びます。
３のあとに０が９７個並びます。
実際にハノイの塔を解くHaskellのプログラムは
参考
Emacsにはテキストベースながらグラフィカルにハノイの塔の動きをシミュレートするマクロが搭載されています。（有名です。）
多分そのソースコードとおもわれるLispプログラムが
に公開されています。（かなり複雑）
またVimのマクロもあり（これは初耳）、
Kona ３．０では
/usr/share/vim/vim74/macros/hanoi
にありました。（使用法は同ディレクトリーのClick.meというファイルを開いてください。）
ユニクスの塔
プリンストンという所にある「ユニクス寺院（和名『宦官寺』）には３本の塔が立っており、
３２枚のシリコンでできた円盤がささっている。
この寺院の僧には円盤をすべて別の塔に移し替えることが修行として課せられている。
その修行は,1970年1月1日午前0時0分0秒に始まっており、
計算では2038年1月19日3時14分7秒に３１枚の円盤を移し終え、最後の１枚にとりかかったところでタイムオーバーとなり、
その瞬間システムはリブートするといわれている。（hanoi.elの注釈より）
＊＊＊＊＊という所にある「＊＊＊の塔」には３本の塔が立っており、世界中から集められたコインでできた32枚の円盤がささっている。
この円盤はなにやら怪しげな動きを繰り返しているが
(なんと「ユニクスの塔」の１０００倍のスピードで)
「黒い箱」で覆われているため、その動きは小さな「窓」を通してしか、うかがい知ることができない。
どうやら円盤は隣の塔に移動しようとしているようだ。
そしてすべて移動し終わったとき、システムはフリーズする。
＊＊＊＊＊という所にある「＊＊＊の塔」には３本の塔が立っており、世界中から集められたコインでできた32枚の円盤がささっている。
この円盤はなにやら怪しげな動きを繰り返しているが
(なんと「ユニクスの塔」の１０００倍のスピードで)
「黒い箱」で覆われているため、その動きは小さな「窓」を通してしか、うかがい知ることができない。
どうやら円盤は隣の塔に移動しようとしているようだ。
そしてすべて移動し終わったとき、システムはフリーズする。
0 件のコメント:
コメントを投稿