ハノイの塔

ハノイの塔は、決まりに従って棒Aの円盤をすべて別の棒に移すパズルです。自分で解くことも、自動の解き方と手順の一覧を見ることもでき、再帰の授業などに使えます。

使い方

1. 「円盤の数」を3〜10から選びます。
2. 一番上の円盤を別の棒にドラッグするか、棒をタップして一番上の円盤を持ち上げ、別の棒をタップして置きます。1、2、3のキーでも操作できます。
3. 1手戻すには「元に戻す」を、最初からやり直すには「最初から」を押します。
4. 行き詰まったら「解き方を表示」を押すと、現在の状態からの解き方を見られます。「速度」を変えたり、「一時停止」を押して「1手進める」を使ったりできます。

計算方法と補足

• 決まり：円盤は1回に1枚だけ動かし、動かせるのは棒の一番上の円盤だけで、小さい円盤の上に大きい円盤を置いてはいけません。
• n枚の円盤の最少手数は2ⁿ − 1です。n枚を動かすには、n − 1枚を脇に移し、一番大きい円盤を1回動かしてから、n − 1枚をその上に戻します。
• 円盤の数ごとの最高記録はこのブラウザに保存されます。自動の解き方を使ったゲームは記録されません。

よくある質問

ハノイの塔の最少手数は？

n枚の円盤では2ⁿ − 1手です。3枚で7手、4枚で15手、5枚で31手、10枚で1,023手です。

ハノイの塔を簡単に解く方法はありますか？

奇数回目の手では、一番小さい円盤を常に同じ向きに1つ隣の棒へ動かします。偶数回目の手では、一番小さい円盤を使わない唯一の動かし方をします。

ハノイの塔が再帰の説明に使われるのはなぜですか？

n枚の解き方は、n − 1枚の解き方2回と一番大きい円盤の1手でできているため、T(n) = 2·T(n − 1) + 1となります。

すべての手順を一度に見られますか？

「解答の手順一覧」を開くと、すべての手順が「円盤1：A → C」の形で表示されます。