ハノイ塔の非再帰について

VBでハノイの塔(非再帰)で作りたいのですが、
考え方がまったくわかりません。
ハノイの塔(非再帰)をVBで作った事のある方、
良ければ基本的な考え方を教えてください。

No.2 回答者： 16August 回答日時： 2006/01/23 18:01

ハノイの塔を作るというのは手順を書き出すと言うことでしょうか？　既に立派な回答がありますが、

円盤を２枚動かす手順を書き出すfunctionをつくり、
３枚動かす手順を書き出すfunctionをつくり
４枚動かす手順を書き出すfundtionをつくり.......
というような感じですかね。

余計なお世話ですが、
大体何枚くらいの、円盤を想定していらっしゃるのでしょうか？　６４枚分を目指していらっしゃるとか？

No.1 回答者： BLUEPIXY 回答日時： 2006/01/22 06:07

作ったことはないのですが、

それぞれの部分の周期性に着目するとできると思います。
以下の部分を見て下さい。
以下の部分は、５枚の板をＡ，Ｂ，ＣのＡからＢに移動させる手順です。
----------------------------------------------------------------
No.1 DISC:A->B
No.2 DISK:A->C
No.1 DISC:B->C
No.3 DISK:A->B
No.1 DISC:C->A
No.2 DISK:C->B
No.1 DISC:A->B
No.4 DISK:A->C
No.1 DISC:B->C
No.2 DISK:B->A
No.1 DISC:C->A
No.3 DISK:B->C
No.1 DISC:A->B
No.2 DISK:A->C
No.1 DISC:B->C
No.5 DISK:A->B
No.1 DISC:C->A
No.2 DISK:C->B
No.1 DISC:A->B
No.3 DISK:C->A
No.1 DISC:B->C
No.2 DISK:B->A
No.1 DISC:C->A
No.4 DISK:C->B
No.1 DISC:A->B
No.2 DISK:A->C
No.1 DISC:B->C
No.3 DISK:A->B
No.1 DISC:C->A
No.2 DISK:C->B
No.1 DISC:A->B
31 手
----------------------------------------------------------------
コレを見ると、奇数板はＡ→Ｂ→Ｃ回り偶数板はＡ→Ｃ→Ｂ回り（奇数枚数の板をＡからＢに移すとき）で
１：１つ置き
２：３つ置き
３：７つ置き
４：１５置き
になっていることがわかります。
つまり、あるｎ番目の板を動かすには、それ以前のｎ－１の板を先に動かす必要があるので
・前もって動かす手順
・自分を動かす手順
・残りを動かす手順（つまり前もって動かす手順と同じ）
になることがわかります。
なので、
ｎ番目の板：｛(ｎ－１)の周期的出現数｝×２＋１＝ｎの周期的出現数
になること
及び、
初めて出現する位置：前の(ｎ－１）板の手順が終わった時＝（ｎ－１）の周期的出現数
になっていることがわかります。
また、
ｎ枚の板を移動完了させるのに必要な手数は
｛(ｎ－１)の周期的出現数｝×２＋１
になることがわかります。
以上のことから、
ｎ枚の塔を移動させる時の総手数と、それぞれの板を移動させる向きとタイミングがわかりますから、プログラミングできると思います。

この回答へのお礼

詳しい解説ありがとうございます。
この説明をもとに一度作成してみます。

お礼日時：2006/01/22 17:10