ハノイの塔 (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) ...
