円盤の移動回数と各塔の状態との関係についてのメモです.

3本ある塔を, 左から 0, 1, 2 と番号づけます.
円盤の枚数は n 枚です. 小さいほうから 1, 2, 3, … n と番号づけます.
初期状態 (n枚の円盤が塔番号 0 に置かれていた状態)から, m回目の移動が終わった時点において, 各塔に置かれる円盤の状態は以下のとおりです.

  xi ≡ xi+1 + (-1)n-i(bi – bi+1)   (mod 3)   ( i は 1~n )

 xi: 円盤 i ( i は 1 から n) が置かれた塔の番号. つまり, 0, 1, 2 のどれか. ただし, xn+1は 0 とする.
 bi: m の 2進数表示 bnbn-1 … b1. ただし, bn+1は 0 とする.

<例>円盤が3枚ある. 5回目の移動が終了した時点での各円盤の置かれた位置を算出してみよう.
  5の 2進数表現は 101 なので, b3=1, b2=0, b1=1.
  決まりから, x4 = 0, b4 = 0.
  x3 ≡ x4 + (-1)3-3( b3-b4) ≡0 + (1-0) ≡ 1
  x2 ≡ x3 + (-1)3-2( b2-b3) ≡1 – (0-1) ≡ 2
  x1 ≡ x2 + (-1)3-1( b1-b2) ≡2 + (1-0) ≡ 3 ≡ 0

つまり, x1 = 0, x2 = 2, x3 = 1
円盤1が塔0に置かれ, 円盤2が塔2に置かれ, 円盤3が塔1に置かれている.

計算量は当然 O(n) . n: 円盤の枚数

省略しますが, 円盤の置かれた途中状態 xi から, スタートからの移動回数 m の2進数表現 bi も簡単に計算できる.

以上で判るように, 少なくとも塔3本のケースにおいては, 移動回数と円盤の状態が完全に数式で判ります.

練習となるACM問題
 #254 Towers of Hanoi

Comments are closed.

Post Navigation