ハノイの塔を実装する

ハノイの塔についてこちら

前提

  • 3つの杭を3つの配列(orig, tmp, to)で表現する
  • 各配列をスタックとみなし行える操作はpushとpopのみ
  • 円盤1つを配列内のintとして表現。大きな円盤は大きな数字で
    • 例えば、3段のハノイの塔は[3,2,1]といった形で表現する

目標

  • n段のorigをtoに移し替えること

まずは

  • 1段のとき、2段のとき、3段のときを考えてその法則性を探る

1段

  1. orig (1)-> to
orig = []
tmp  = []
to   = [1]

2段

  1. orig (1)-> tmp
# 1段と同じ操作をorig -> tmp
orig = [2]
tmp  = [1]
to   = []
  1. orig (2)-> to
# 1段と同じ操作
orig = []
tmp  = [1]
to   = [2]
  1. tmp (1)-> to
# 1段と同じ操作をtmp -> to
orig = []
tmp  = []
to   = [2,1]

3段

  1. orig (1)-> to
  2. orig (2)-> tmp
  3. to (1)-> tmp
# 2段のときと同じ操作を orig -> tmp で実行
orig = [3]
tmp  = [2,1]
to   = []
  1. orig (3)-> to
# 1段のときと同じ操作
orig = []
tmp  = [2,1]
to   = [3]
  1. tmp (1)-> orig
  2. tmp (2)-> to
  3. orig (1)-> to
# 2段目のときと同じ操作を tmp -> to で実行
orig = []
tmp  = []
to   = [3,2,1]

ちょっと多いけど4段目

  1. orig (1)-> tmp
  2. orig (2)-> to
  3. tmp (1)-> to
  4. orig (3)-> tmp
  5. to (1)-> orig
  6. to (2)-> tmp
  7. orig (1)-> tmp
# 3段のときと同じ操作を orig -> tmp で実行
orig = [4]
tmp  = [3,2,1]
to   = []
  1. orig (4)-> to
# 1段のときの操作
orig = []
tmp  = [3,2,1]
to   = [4]
  1. tmp (1)-> to
  2. tmp (2)-> orig
  3. to (1)-> tmp
  4. tmp (3)-> to
  5. orig (1)-> tmp
  6. orig (2)-> to
  7. tmp (1)-> to
# 3段のときと同じ操作を tmp -> to で実行
orig = []
tmp  = []
to   = [4,3,2,1]

上記の試行から3つの手順に分けられる

N段のハノイの場合

  1. N-1段をorig->tmpに移動
  2. 1番下(N段目)をorig->toに移動
  3. 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)

カウントありのpythonコード