ハノイの塔
問題
ハノイの塔
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つに分岐するのでである。
コード例
スタックを用いて実装する。
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())