ハノイの塔を実装する
前提
- 3つの杭を3つの配列(orig, tmp, to)で表現する
- 各配列をスタックとみなし行える操作はpushとpopのみ
- 円盤1つを配列内のintとして表現。大きな円盤は大きな数字で
- 例えば、3段のハノイの塔は
[3,2,1]
といった形で表現する
- 例えば、3段のハノイの塔は
目標
- n段のorigをtoに移し替えること
まずは
- 1段のとき、2段のとき、3段のときを考えてその法則性を探る
1段
- orig (1)-> to
orig = [] tmp = [] to = [1]
2段
- orig (1)-> tmp
# 1段と同じ操作をorig -> tmp orig = [2] tmp = [1] to = []
- orig (2)-> to
# 1段と同じ操作 orig = [] tmp = [1] to = [2]
- tmp (1)-> to
# 1段と同じ操作をtmp -> to orig = [] tmp = [] to = [2,1]
3段
- orig (1)-> to
- orig (2)-> tmp
- to (1)-> tmp
# 2段のときと同じ操作を orig -> tmp で実行 orig = [3] tmp = [2,1] to = []
- orig (3)-> to
# 1段のときと同じ操作 orig = [] tmp = [2,1] to = [3]
- tmp (1)-> orig
- tmp (2)-> to
- orig (1)-> to
# 2段目のときと同じ操作を tmp -> to で実行 orig = [] tmp = [] to = [3,2,1]
ちょっと多いけど4段目
- orig (1)-> tmp
- orig (2)-> to
- tmp (1)-> to
- orig (3)-> tmp
- to (1)-> orig
- to (2)-> tmp
- orig (1)-> tmp
# 3段のときと同じ操作を orig -> tmp で実行 orig = [4] tmp = [3,2,1] to = []
- orig (4)-> to
# 1段のときの操作 orig = [] tmp = [3,2,1] to = [4]
- tmp (1)-> to
- tmp (2)-> orig
- to (1)-> tmp
- tmp (3)-> to
- orig (1)-> tmp
- orig (2)-> to
- tmp (1)-> to
# 3段のときと同じ操作を tmp -> to で実行 orig = [] tmp = [] to = [4,3,2,1]
上記の試行から3つの手順に分けられる
N段のハノイの場合
- N-1段をorig->tmpに移動
- 1番下(N段目)をorig->toに移動
- N-1段をtmp->toに移動
手順1と3を再帰的に行うことで
コードにすると(python)
動かした回数を出したい場合は、実際に動かす操作を行なっている箇所、つまりto.appendの前後どちらかでカウントをインクリメントすればよい
def move(n, orig, to, tmp): if n == 0: return # n-1段をorigからtmpに移動する move(n-1, orig, tmp, to, cnt) # n段目をtoに移動する to.append(orig.pop()) # n-1段をtmpからtoに移動する move(n-1, tmp, to, orig, cnt) import sys # 引数でハノイの塔の高さを指定する if len(sys.argv) != 2: exit N = int(sys.argv[1]) # N段の塔、空の塔を配列で擬似的に表す orig = [i for i in range(N, 0, -1)] tmp = [] to = [] # origの塔をtoに動かす move(N, orig, to, tmp)