ハノイの塔

ハノイの塔

ハノイの塔というパズルを考えます。

ハノイの塔では、次のルールのもとにすべての円盤を移動します。

🔹大きさの異なる複数の円盤があり、小さな円盤の上に大きな円盤を積むことはできない。
🔹円盤を置ける場所は３か所あり、最初は１か所にすべて積まれている。
🔹円盤を１回に１枚ずつ移動し、すべての円盤を別の場所に移動するまでの回数を調べる。

解き方・ソースコード

$ n $ 枚の円盤を移動するの必要な最小の移動回数と、その移動手段を求める方法を考えます。

小さな円盤の上に大きな円盤は積めないので、$ n $ 枚の円盤を移動するには $ n - 1 $ 枚を移動した後に、最大の１枚を移動し、その上に $ n - 1 $ 枚を移動することになります。

円盤を置ける３か所をそれぞれ $ a,b,c $ とし、$ a $ から $ b $ に円盤を移動することを $ a $ -> $ b $ と表現します。

移動に必要なパラメータは、「円盤の残り枚数」「移動元」「移動先」「経由場所」の４つで、これらを引数とする関数を定義し、その中で移動内容を出力します。

処理する枚数は、標準入力としプログラム実行時に変えられるようにしています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 引数 n 円盤の残り枚数
# 引数 src 移動元
# 引数 dist 移動先
# 引数 via 経由場所
def hanoi(n, src, dist, via):
    global cnt
    cnt += 1
    if n > 1:
        # n - 1枚を移動元から経由場所に移す
        hanoi(n - 1, src, via, dist)
        print(src + ' -> ' + dist)
        # n -1枚を経由場所から移動先に移す
        hanoi(n - 1, via, dist, src)
    else:
        print(src + ' -> ' + dist)

n = int(input())    # 円盤の枚数（標準入力）

cnt = 0             # 移動回数
hanoi(n, 'a', 'b', 'c')
print('解（移動回数）：', cnt)

[実行結果（円盤の枚数が3の場合）]

a -> b

a -> c

b -> c

a -> b

c -> a

c -> b

a -> b

解（移動回数）： 7

[実行結果（円盤の枚数が4の場合）]

a -> c

a -> b

c -> b

a -> c

b -> a

b -> c

a -> c

a -> b

c -> b

c -> a

b -> a

c -> b

a -> c

a -> b

c -> b

解（移動回数）： 15