inthink.guide
ショップホームへ戻る

遊ぶ。予想する。理解する。

ハノイの塔

3～5枚の円盤で遊び、今の配置に合ったヒントを使い、2つの短いアニメーションで再帰的な解き方を学べます。手順付きの例はいつでも開けます。

ハノイの塔で遊ぶ
ABC円盤44円盤33円盤22円盤11

小さい円盤の山を移して、最大の円盤を動かせるようにします。

ハノイの塔のルール

  1. すべての円盤を柱Aから柱Cへ移します。
  2. 一度に動かせるのは1枚だけで、柱の一番上から取ります。
  3. 大きい円盤を小さい円盤の上に置いてはいけません。

ハノイの塔で遊ぶ

移動元の柱を選び、次に移動先を選びます。数字は大きさを表し、1が最小です。1手戻したり、最初から試したりできます。

0手
ABC円盤33円盤22円盤11

移動元を選び、次に移動先を選びます。

ヒントは今の配置から考えます。円盤を勝手に動かすことはありません。ルールを守った遠回りでも解けます。

ハノイの塔の解き方

最大の円盤から考えましょう。4枚の例では3枚の小さい円盤が邪魔をしています。円盤4を動かす前に、小さい問題を解きます。

  1. 小さい山をよける

    円盤1・2・3をAからBへ移し、Cを補助に使います。円盤4はAに残します。Cが空き、円盤4を動かせるようになります。

    ABC円盤44円盤33円盤22円盤11

  2. 最大の円盤を動かす

    円盤4をAからCへ移します。この1手で最大の円盤が最終位置に着きます。

    ABC円盤44円盤33円盤22円盤11

  3. 小さい山を目的地へ移す

    円盤1・2・3をBからCへ移し、Aを補助に使います。円盤4の上に重ねれば完成です。

    ABC円盤44円盤33円盤22円盤11

小さい山でも同じ計画を繰り返します。最大の円盤の上をよけ、それを動かし、小さい山を上に戻します。1枚だけなら直接動かします。これが再帰です。小さい問題ごとに移動元・移動先・補助の柱が変わります。

次の目標を予想して学ぶ

練習中の盤面は変わらない、独立した4枚の例です。一時停止し、1手ずつ見て、予想に答えたり説明を開いたりできます。

1. 最大の円盤の道をあける

3枚の小さい円盤が円盤4の道をあける様子を見ます。大きい円盤を動かす前の置き場所を予想しましょう。

独立した4枚の例

目標：Cを補助に使い、3枚をAからBへ移す。

ABC円盤44円盤33円盤22円盤11

まず道をあけます。上の3枚をAからBへ移します。

8手中0手

2. 小さい問題を繰り返す

円盤4はすでにCにあります。残りは3枚の同じ問題で、柱の役割だけが変わります。

独立した4枚の例

目標：Aを補助に使い、3枚をBからCへ移す。

ABC円盤44円盤33円盤22円盤11

円盤4はCに残します。次は3枚をBからCへ移す問題です。

Aを補助に3枚をBからCへ移すとき、円盤1は最初にどこへ行くでしょう？

7手中0手

手順付きの解答例

例はすべての円盤がAにある状態から始まり、Cで終わります。すぐに開いても、練習中の配置は変わりません。

最小の手数

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

標準の解法では小さい山を2回、最大の円盤を1回動かすため、T(n) = 2T(n − 1) + 1となります。1枚なら1手なので、n枚の最小手数は2ⁿ − 1です。

3枚：7手。4枚：15手。5枚：31手。

3枚 — 7手

開始：すべてA。目的地：C。円盤1が最小です。

  1. 円盤1をAからCへ移す。
  2. 円盤2をAからBへ移す。
  3. 円盤1をCからBへ移す。
  4. 円盤3をAからCへ移す。
  5. 円盤1をBからAへ移す。
  6. 円盤2をBからCへ移す。
  7. 円盤1をAからCへ移す。
4枚 — 15手

開始：すべてA。目的地：C。円盤1が最小です。

  1. 円盤1をAからBへ移す。
  2. 円盤2をAからCへ移す。
  3. 円盤1をBからCへ移す。
  4. 円盤3をAからBへ移す。
  5. 円盤1をCからAへ移す。
  6. 円盤2をCからBへ移す。
  7. 円盤1をAからBへ移す。
  8. 円盤4をAからCへ移す。
  9. 円盤1をBからCへ移す。
  10. 円盤2をBからAへ移す。
  11. 円盤1をCからAへ移す。
  12. 円盤3をBからCへ移す。
  13. 円盤1をAからBへ移す。
  14. 円盤2をAからCへ移す。
  15. 円盤1をBからCへ移す。
5枚 — 31手

開始：すべてA。目的地：C。円盤1が最小です。

  1. 円盤1をAからCへ移す。
  2. 円盤2をAからBへ移す。
  3. 円盤1をCからBへ移す。
  4. 円盤3をAからCへ移す。
  5. 円盤1をBからAへ移す。
  6. 円盤2をBからCへ移す。
  7. 円盤1をAからCへ移す。
  8. 円盤4をAからBへ移す。
  9. 円盤1をCからBへ移す。
  10. 円盤2をCからAへ移す。
  11. 円盤1をBからAへ移す。
  12. 円盤3をCからBへ移す。
  13. 円盤1をAからCへ移す。
  14. 円盤2をAからBへ移す。
  15. 円盤1をCからBへ移す。
  16. 円盤5をAからCへ移す。
  17. 円盤1をBからAへ移す。
  18. 円盤2をBからCへ移す。
  19. 円盤1をAからCへ移す。
  20. 円盤3をBからAへ移す。
  21. 円盤1をCからBへ移す。
  22. 円盤2をCからAへ移す。
  23. 円盤1をBからAへ移す。
  24. 円盤4をBからCへ移す。
  25. 円盤1をAからCへ移す。
  26. 円盤2をAからBへ移す。
  27. 円盤1をCからBへ移す。
  28. 円盤3をAからCへ移す。
  29. 円盤1をBからAへ移す。
  30. 円盤2をBからCへ移す。
  31. 円盤1をAからCへ移す。

今の配置が例と違う場合は？

大きさのルールを守る配置なら、どれでもCへ移せます。同じ配置に戻るのはループで、行き詰まりではありません。上の式は標準の開始状態にだけ使い、任意の配置の残り手数ではありません。今の配置からのヒントを使いましょう。

パズル →