問題
n枚の異なる大きさの円盤と３本の杭がある。初期状態では、最初の杭にすべての円盤が積み重なっていて、大きいものが下、小さいものが上になるように大きさの順になっている。
円盤の移動を繰り返して、すべての円盤を別の杭に移す。
ただし、円盤は１枚ずつしか移動させられないし、自身より小さい円盤の上には移動させられないものとする。
この時、最短で何回の移動が必要か。
方針
実際にやってみると、６段程度であれば難しくないです。
積み上げようとする杭とは別の杭を一時的な置き場所として利用しつつ、目的の杭に積み上げていくことなるでしょう。
下表のような、マイルストーンを頭にいれて行うとやり易いと思います。
（※途中でどちらの杭に積もうとしていたのか忘れがちなので・・・）
杭１
|
杭２
|
杭３
|
6
|
0
|
0
|
5
|
1
|
0
|
4
|
0
|
2
|
3
|
3
|
0
|
2
|
0
|
4
|
1
|
5
|
0
|
0
|
0
|
6
|
では、円盤が何段であってもこの問題は解けるのでしょうか？
答えはYESです。
なぜなら、N段の問題を解くということは、N-1段の問題を解くのと同じことだからです。
つまり、n枚の円盤を移動させた回数をM(n)とすると
M(n) = M(n - 1) + 1 + M(n - 1)
※n > 1 のとき
ということになります。
さて、ここでの問題は、移動自体の方法論ではなく、何回移動が必要か？ということです。
この式が、まさにこの問題の答えということになりますね。
この式が、まさにこの問題の答えということになりますね。
M(n) = 2 * M(n - 1) + 1
M(1) = 1
は、コードでは、再帰的な表現となります。
コード
swift3
// main.swift
// TowerOfHanoi
//
// Created by 山崎真一郎 on 2017/02/06.
// Copyright © 2017 山崎真一郎. All rights reserved.
//
import Foundation
func itemM(n: Int) -> Int
{
if (n == 1)
{
return 1
}
return 2 * itemM(n: n - 1) + 1
}
for i in 1...10
{
var num = itemM(n: i)
print("i:\(i) num:\(num)")
}
実行結果
i:1 num:1
i:2 num:3
i:3 num:7
i:4 num:15
i:5 num:31
i:6 num:63
i:7 num:127
i:8 num:255
i:9 num:511
i:10 num:1023
Program ended with exit code: 0
