ハノイの塔

問題

ハノイの塔

3つの塔とN枚のサイズの異なる円盤がある。1つの塔から別の塔に移動させる。

  • 1度に1つの円盤しか動かせない。
  • 塔の一番上の円盤だけ移動できる
  • 円盤はそれよりも大きいものの上にしか置けない。

考え方

まずは具体的にやってみる。塔をstart, mid, endに分ける。 n=2の場合で考える。

  • 1枚目をmidに移動させる
  • 2枚目をendに移動させる
  • 1枚目をmidからendに移動させる

再帰的に考える。 n枚目をendに移動させるときにはn-1枚目までのmidへの移動が完了している。n枚目をendに移動させて、n-1枚の山をmidからendに移動させる。

時間計算量は一度のstepで2つに分岐するので O(2^{N})である。

コード例

スタックを用いて実装する。

def moveToEnd(n, start, mid, end):
    if n == 0:
        return 0
    #--n-1までをmidに移動させた状態
    moveToEnd(n-1, start, end, mid)
    #--n-thをendへ
    item = start.pop()
    end.push(item)
    #--n-1までをendに移動させる
    moveToEnd(n-1, mid, start, end)

if __name__ == "__main__":
    S = [Stack() for _ in range(3)]
    for i in range(5):
        S[0].push(i)

    moveToEnd(5, S[0], S[1], S[2])

    while not S[2].isEmpty():
        print(S[2].pop())