ハノイの塔 (3回目)

2024/8/21(土)
ハノイの塔 (3回目)
 
再帰を使用しない手順(偶数奇数をまとめる)(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
と書く事にする
 
 
■ 具体的な動かし方
▼ 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
 
 
■ 奇数偶数をまとめる
nが奇数の時
　A = Aのtop, pB = Bのtop, pC = Cのtop
　pAB = A->B, pBC = B->C, pCA = C->A
　pBA = B->A, pCB = C->B, pAC = A->C
nが偶数の時(A⇔B)
　pA = Bのtop, pB = Bのtop, pC = Cのtop
　pAB = B->A, pBC = A->C, pCA = C->B
　pBA = A->B, pCB = C->A, pAC = B->C
と定義する
つまり以下偶数の時は(A⇔B)と読み替える
 
nが偶数の時のみ以下の2行を追加
　pBA
　pB < pC なら pBC 違うなら pCB
 
pAC
pA ≠ pBの間以下を繰り返す
　pA < pB なら pAB 違うなら pBA
　pCB
　pC < pA なら pCA 違うなら pAC
　pBA
　pB < pC なら pBC 違うなら pCB
　pAC