brainfuckでハノイの塔を解くプログラムを作ってみた.段数は26段.
ハノイの塔のルールは
ここを参照
各行に
(アルファベット) (数字) (数字)
という出力がされる.たとえば,
A 1 3
ならば1番の棒にあるAの円盤を3番の棒に移すことを表す.
Aが一番小さい円盤で,アルファベット順に大きい円盤になる.
注意：激重(約700億ステップ) !!!処理系によっては一生終わらない!!!
>>>>+>+++++[<+++++>-]+>+>+++<<<
[
>[
<-[
[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
<++++++>>+>->>>>>>>
[<<<<<<<<<<<<+>>>>>>>>>>>>-]
>[<<<<<<<<<<<<+>>>>>>>>>>>>-]
>[<<<<<<<<<<<<->>>>>>>>>>>>-]
>[<<<<<<<<<<<<+<->>>>>>>>>>>>>-]
<<<<<[>>+>+<<<-]
>[>+<-]++++++>[<->-]>[<<<+>>>-]
<<<<<-
]+>-
]++++++++[>++++++>++++++<<<++++++++>-]>>>>++++[<++++++++>-]<<<<<.[-]>>>>.<<.[-]>>.[-]<.[-]++++++++++.[-]<<<<<<<
]
段数を10段にしたもの:
これでも処理系によっては時間が掛かる
>>>>+++++++++>+>+>+++<<<
[
>[
<-[
[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
>[>>>>+>>>>+>>>>+<<<<<<<<<<<<-]
<++++++>>+>->>>>>>>
[<<<<<<<<<<<<+>>>>>>>>>>>>-]
>[<<<<<<<<<<<<+>>>>>>>>>>>>-]
>[<<<<<<<<<<<<->>>>>>>>>>>>-]
>[<<<<<<<<<<<<+<->>>>>>>>>>>>>-]
<<<<<[>>+>+<<<-]
>[>+<-]++++++>[<->-]>[<<<+>>>-]
<<<<<-
]+>-
]++++++++[>++++++>++++++<<<++++++++>-]>>>>++++[<++++++++>-]<<<<<.[-]>>>>.<<.[-]>>.[-]<.[-]++++++++++.[-]<<<<<<<
]
最初の+の個数を変えることで1～26段に変更できる.
解説
ハノイの塔は再帰的なアルゴリズムによって解けることが知られている.
円盤がn枚あるとする.ここでは最初は全ての円盤が番号1のぼうにあり,これを番号3の棒に移すことにする.
- 何らかの方法で(n-1)枚の円盤を番号1の棒から番号2の棒に移す.
- 一番大きな円盤を番号1の棒から番号3の棒に移す.
- 何らかの方法で(n-1)枚の円盤を番号2の棒から番号3の棒に移す.
- 「何らかの方法」の最適解は(n-1)枚の円盤のハノイの塔の解法と同一視できるから,この「何らかの方法」を行う際にもこの解法を再帰的に利用する.
簡単な例として円盤が3枚(A,B,B)のときの動かし方を求める.
①何らかの方法で円盤A,Bを番号1の棒から番号2の棒に移す.
②円盤Cを番号1の棒から番号3の棒に移す.
③何らかの方法で円盤A,Bを番号2の棒から番号3の棒に移す.
ここで,①の操作は,
[1]円盤Aを番号1の棒から番号3の棒に移す.
[2]円盤Bを番号1の棒から番号2の棒に移す.
[3]円盤Aを番号3の棒から番号2の棒に移す.
となる.これは円盤が2枚のハノイの塔の解法と全く同一である.③の操作も同様にして求められる.
これをまとめると,
①円盤Aを番号1の棒から番号3の棒に移す.
②円盤Bを番号1の棒から番号2の棒に移す.
③円盤Aを番号3の棒から番号2の棒に移す.
④円盤Cを番号1の棒から番号3の棒に移す.
⑤円盤Aを番号2の棒から番号1の棒に移す.
⑥円盤Bを番号2の棒から番号3の棒に移す.
⑦円盤Aを番号1の棒から番号3の棒に移す.
となる.したがって,実際の出力は次の通り.
A 1 3
B 1 2
A 3 2
C 1 3
A 2 1
B 2 3
A 1 3
実装
brainfuckでは関数という概念がないので,当然再帰関数を書くことができない.
したがって代わりにスタックと呼ばれるデータ構造を用いて解くことを考える.
スタックに対して行える操作は二つ
元のスタック
このスタックにデータ 5 をpushすると,スタックは
となる.
元のスタック
このスタックをpopすると,スタックは
となり,値 6 を得られる.
もちろん,brainfuckにはスタックの操作をサポートするような機能はないが,幸いにも「ポインタが現在示している場所」を基準としたメモリ操作ができるので,これを利用する.たとえば,整数値を持つスタックを組む場合,
- 最初ポインタの指す場所は0番地にある
- pushするときは,今指している場所に"+","-",","などを用いて値を入れ,>でポインタをひとつ進める.
- popするときは今指している場所の値を使った後,<でポインタをひとつ戻す
というごく簡単な命令に落としこむことができる.
今回は,このスタックに与えるデータとして次のような数値の四つ組を使った.したがって,push,popの際のポインタ移動は4つずつになる.
NUM:円盤の番号[1〜26]
FLG:フラグ[0,1]
このフラグの値は,
1のとき「NUM番以下の円盤を全て動かせ」という意味で,
0のとき「NUM番の円盤を動かせ」という意味になる.
S:円盤の現在位置[1〜3]
T:円盤を動かすべき位置[1〜3]
最初,メモリ上に
というように値を入れる.(実際は負番地のメモリに行かないよう4番地から代入している)
このあと,次の操作をスタックが空になるまで続ける.
① FLGが1のとき
[1] NUMが1より大きいとき
スタックが
となっているので,
| … |
NUM-1 |
1 |
S |
U |
NUM |
0 |
S |
T |
NUM-1 |
1 |
U |
T |
となるように書き換える.(1回popして,3回pushすることに相当)
ここでUは[1,2,3]のうち,SでもTでもない値.
値の四つ組がそれぞれ
- (NUM-1)枚の円盤を何らかの方法で番号Sの棒から番号Uの棒に移す
- NUM番目の円盤を番号Sの棒から番号Tの棒に移す
- (NUM-1)枚の円盤を何らかの方法で番号Uの棒から番号Tの棒に移す
という操作に対応している.
UはU=6-S-Tで求められる.
1回popして,3回pushしているので,ポインタは8つ進む.
[2] NUMが1のとき
1番以下の円盤を何らかの方法で番号Sの棒から番号Tの棒に移す,という操作は
1番の円盤を何らかの方法で番号Sの棒から番号Tの棒に移す,という事と同じだから,FLGを1から0に書き換える.
1回popして,1回pushすることに相当するので,ポインタの指す位置は変わらない.
② FLGが0のとき
(NUM番目のアルファベット) S T
と出力し,値を消してpopする(4番地戻る).
最終更新：2013年03月07日 20:41
