ハノイの塔 (2回目)

2024/12/18(水)
ハノイの塔 (2回目)
 
再帰を使用しない手順(偶数奇数別)(hanoi)
 
■ 定義
▼ 前提
3本(A,B,C)の棒とn枚の円盤(小さい順に1～nとする)がある
Aに1～nの円盤が上から順に積まれている
 
▼ 目標
1～nの円盤全てをCに移動させる
 
▼ ルール
小さい円盤の上に大きい円盤は置けない
1度に動かせる円盤は1枚のみ
 
A,B,Cの一番上の円盤をpA, pB, pCとし、円盤が無い時は最大値とする
 
円盤1をAからCに移動する事を1:A->C
棒を0
円盤を1 222 33333 …
と書く事にする
 
 
■ 具体的な動かし方
▼ nが奇数の場合
A->C
pA ≠ pBの間以下を繰り返す
　pA < pB なら A->B 違うなら B->A
　C->B
　pC < pA なら C->A 違うなら A->C
　B->A
　pB < pC なら B->C 違うなら C->B
　A->C
 
n = 1のとき
1:A->C check
 
n = 3のとき
                                   1:A->C check
2:A->B 1:C->B 3:A->C 1:B->A 2:B->C 1:A->C check
 
n = 5のとき
                                   1:A->C check
2:A->B 1:C->B 3:A->C 1:B->A 2:B->C 1:A->C check
4:A->B 1:C->B 2:C->A 1:B->A 3:C->B 1:A->C check
2:A->B 1:C->B 5:A->C 1:B->A 2:B->C 1:A->C check
3:B->A 1:C->B 2:C->A 1:B->A 4:B->C 1:A->C check
2:A->B 1:C->B 3:A->C 1:B->A 2:B->C 1:A->C check
 
移動回数は1,7,31,…
 
A->C 1回
check (以下loop)
　(A->B or B->A) C->B
　(A->C or C->A) B->A
　(B->C or C->B) A->C 6回
 
1回,6回,6回,…の繰返しになっており
(A->B or B->A)はどちらかは小の上に大が来るので
移動出来ない為一意に決まる
 
また
円盤1は1回おきに動かす事になり
1より小さい円盤はないので移動方向は一意に決まる
よって移動方向の判定は1回おきとなる
 
n = 5の時
                                   1:A->C check
2:A->B 1:C->B 3:A->C 1:B->A 2:B->C 1:A->C check
4:A->B 1:C->B
 
    A        B        C
    0        0        0
    0        0        0
    0        0        0
    0        1       222
555555555 4444444   33333
 
この次は(A->C or C->A)だが
A->Cは移動できないのでC->Aに決まる
 
 
▼ nが偶数の場合
nが奇数の場合に2行追加しAとBを入れ替える
A->B 追加
pA < pC なら A->C 違うなら C->A 追加
B->C
pB ≠ pAの間以下を繰り返す
　pB < pA なら B->A 違うなら A->B
　C->A
　pC < pB なら C->B 違うなら B->C
　A->B
　pA < pC なら A->C 違うなら C->A
　B->C
 
n = 2のとき
1:A->B 2:A->C 1:B->C check
 
n = 4のとき
                     1:A->B 2:A->C 1:B->C check
3:A->B 1:C->A 2:C->B 1:A->B 4:A->C 1:B->C check
2:B->A 1:C->A 3:B->C 1:A->B 2:A->C 1:B->C check
 
n = 6のとき
                    1:A->B 2:A->C 1:B->C check
3:A->B 1:C->A 2:C->B 1:A->B 4:A->C 1:B->C check
2:B->A 1:C->A 3:B->C 1:A->B 2:A->C 1:B->C check
5:A->B 1:C->A 2:C->B 1:A->B 3:C->A 1:B->C check
2:B->A 1:C->A 4:C->B 1:A->B 2:A->C 1:B->C check
3:A->B 1:C->A 2:C->B 1:A->B 6:A->C 1:B->C check
2:B->A 1:C->A 3:B->C 1:A->B 2:A->C 1:B->C check
4:B->A 1:C->A 2:C->B 1:A->B 3:C->A 1:B->C check
2:B->A 1:C->A 5:B->C 1:A->B 2:A->C 1:B->C check
3:A->B 1:C->A 2:C->B 1:A->B 4:A->C 1:B->C check
2:B->A 1:C->A 3:B->C 1:A->B 2:A->C 1:B->C check
 
移動回数は3,15,63,…
 
A->B 追加
(A->C or C->A) 追加
B->C 3回
check (以下loop)
　(B->A or A->B) C->A
　(B->C or C->B) A->B
　(A->C or C->A) B->C 6回
 
3回,6回,6回,…の繰返しになっており
(B->A or A->B)はどちらかは小の上に大が来るので
移動出来ない為一意に決まる
 
交互に動かす円盤1の移動は一意に決まるので方向
チェックは必要ない
 
■ 結果
▼ 補足
大小チェックのない移動は円盤1
 
▼ nが奇数の場合
A->C
pA ≠ pBの間以下を繰り返す
　pA < pB なら A->B 違うなら B->A
　C->B
　pC < pA なら C->A 違うなら A->C
　B->A
　pB < pC なら B->C 違うなら C->B
　A->C
 
▼ nが偶数の場合
nが奇数の場合に2行追加しAとBを入れ替える
A->B 追加
pA < pC なら A->C 違うなら C->A 追加
B->C
pA ≠ pBの間以下を繰り返す
　pB < pA なら B->A 違うなら A->B
　C->A
　pC < pB なら C->B 違うなら B->C
　A->B
　pA < pC なら A->C 違うなら C->A
　B->C
 
▼ 次回奇数偶数まとめます