「ハノイの塔」(ランク A) を円盤を動かさずに解く

はじめに

paiza x Qiita のプログラミング問題 の ハノイの塔 をトライしました.

ハノイの塔は再帰の例として有名です. 私も最初はオーソドックスにハノイの塔の操作をするコードを書き, 指定された回数で操作をやめ, そのときの状態を出力するものを作成しました.

その後, いろいろと考えていくうちに, 円盤を動かす操作をしなくても, 指定された回数から円盤の状態を直接求められることに気付き, それをコードにしてみました.

以下に, 概略を説明します.

作戦

n 番目の円盤の場所を決める

まず塔 A, B, C があり, n 個の円盤が A にあるとします. そして, すべての円盤を C に動かすことを考えます. n 個の円盤を移動させるのに必要な操作回数を $a_n$¹ とします. 円盤の動かし方は次のようになります.

1. n-1 個の円盤を A -> B に動かす ($a_{n-1}$ 回の操作)
2. n 番目の円盤を A -> C に動かす (1 回の操作)
3. n-1 個の円盤を B -> C に動かす ($a_{n-1}$ 回の操作)

そのため, 移動回数 $t$ に対して n 番目の円盤の場所は以下のように決めることができます.

• $t \le a_{n-1}$ ; n 番目の円盤は A にある (まだ動いていない)
• $t \gt a_{n-1}$ ; n 番目の円盤は C にある (もう動いた)

n-1 番目の円盤の場所を決める

次に, n-1 番目の円盤の場所を考えます. $t$ の値によって, 場合分けをします.

t < a_(n-1) の場合

まず $t \lt a_{n-1}$ の場合です. この場合, n 番目の円盤はまだ A にあり, C に動かそうとしています. そのため n-1 番目の円盤は, B へ動かすことになります. 手順としては次のようになります.

1. n-2 個の円盤を A -> C に動かす ($a_{n-2}$ 回の操作)
2. n-1 番目の円盤を A -> B に動かす (1 回の操作)
3. n-2 個の円盤を C -> B に動かす ($a_{n-2}$ 回の操作)

そのため, n 番目の円盤の時と同様に考えると, 以下のようにして n-1 番目の円盤の場所を決めることができます.

• $t \le a_{n-2}$ ; n-1 番目の円盤は A にある (まだ動いていない)
• $t \gt a_{n-2}$ ; n-1 番目の円盤は B にある (もう動いた)

t >= a_(n-1) の場合

続いて $t \ge a_{n-1}$ の場合です. このときは n 番目の円盤はすでに C にあり, 1 から n-1 番目の円盤は B から C に移動している途中になります. そのため

• $t - (a_{n-1} + 1 ) \lt a_{n-2}$ ; n-1 番目の円盤は B にある (まだ動いていない)
• $t - (a_{n-1} + 1) \ge a_{n-2}$ ; n-1 番目の円盤は C にある (もう動いた)

コード

ポイントのみ説明します. 全体のコードは, 末尾の Google Colaboratory へのリンクから確認してください.

操作回数の関数定義

操作回数の関数を定義します.

1

# n 個の円盤からなるハノイの塔の操作回数を計算する
def hanoi_trial(n):
  return 2**n - 1

続いて, 変数を定義します. 塔の番号は a, b, c の変数に入れますが, 常に

• a ; 円盤の移動元
• b ; バッファの塔
• c : 円盤の移動先

となるようにします.

2

# 変数設定
tower = [[], [], []] # 各塔にある円盤を格納する変数
a = 0 # 塔の番号を表す. 0 -> 最初, 1 -> バッファ, 2 -> 最後
b = 1
c = 2

標準入力からデータを読み込みます.

• n ; 円盤の数
• t ; 操作回数

3

# 標準入力からデータを読む
s = input().rstrip().split()
n = int(s[0])
t = int(s[1])

続いてメインのコードです. n 番目の円盤から順に, どの塔にいるかを求めていきます.

4

# n 番目の円盤から順に，どの塔にあるかを求めていく
for i in range(n, 0, -1):
  if t <= hanoi_trial(i-1):
    tower[a].append(i)
    b, c = c, b
  else:
    tower[c].append(i)
    t -= (hanoi_trial(i-1)+1)
    a, b = b, a

ちょっと説明します. まず, 操作回数 $t$ が前半 ($t \le a_{i-1}$) の場合です (以下の部分). このときは $i$ 番目の円盤は動いていないので, 移動元 (a) のリストに番号を追加 (tower[a].append(i)) します. そして次の操作の準備として, 塔の番号を入れ替えます. $i-1$ 番目の円盤はバッファの塔に行ってもらうので, b と c を入れ替えます (b, c = c, b).

4-1

  if t <= hanoi_trial(i-1):
    tower[a].append(i)
    b, c = c, b

次に, 操作回数 $t$ が後半 ($t \gt a_{i-1}$) の場合です (以下の部分). このとき, $i$ 番目の円盤は既に動いているので, 移動先 (c) のリストに番号を追加 (tower[c].append(i)) します. その後, 次のループの判定を容易にするため, 前半部分の回数を引き算 (t -= (hanoi_trial(i-1) + 1)) しておきます. 最後に塔の番号を入れ替えますが, $i-1$ 番目の円盤はバッファ b に行ってもらい, その代わりに a がバッファになるので, a と b を入れ替えます (a, b = b, a).

4-2

  else:
    tower[c].append(i)
    t -= (hanoi_trial(i-1)+1)
    a, b = b, a

さいごに

コードを書いてみると, 案外とシンプルなものができました. そのためコードを見ただけでは, 何をしているのかが分かりづらいかもしれません. 考え方そのものは単純なので, ご理解いただけると嬉しいです.

リンク

• ハノイの塔_試行レス版.ipynb
• (参考) ハノイの塔_提出版.ipynb (ハノイの塔の操作をやりながら円盤の配置を求めるコード)

1. $a_n = 2^n-1$ となります. $a_1 = 1$, $a_{n+1} = 2 a_n + 1$ の数列から計算できます. ↩