ハノイの塔と再帰・指数爆発

Q: ハノイの塔と再帰・指数爆発とは何ですか？

円盤の枚数を n としたとき、n 枚のハノイの塔を解く最小手数 T_n は、漸化式 T_1 = 1,\; T_n = 2T_{n-1} + 1 で定義される数列です。

Q: ハノイの塔と再帰・指数爆発は社会やプログラミングでどのように使われていますか？

再帰呼び出しによるハノイの塔自動ソルバー: 最小手数でハノイの塔を解く手順（どの柱からどの柱へ動かすか）をすべて標準出力・配列化するTypeScriptの再帰関数です。

3本の柱と円盤パズル。再帰的思考と2ⁿ-1手の爆発的宇宙を解き明かす

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 3本の柱があり、「1回に1枚しか動かせない」「小さい円盤の上に大きい円盤を乗せてはならない」ルールで全てを目的地に移す。
2: 円盤 n 枚を移動させる最小手数は $2^n - 1$ 手である。
3: 円盤が64枚ある伝説のハノイの塔では、最小手数でも約1844京回（ $2^{64}-1$ ）の手数を要し、1秒に1手動かしても完了まで約5800億年（宇宙の年齢の40倍以上）かかる。

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

1883年にフランスの数学者エドゥアール・リュカが考案したパズル。「n枚の円盤を動かすには、まず上のn-1枚を一時退避させ、一番下の1枚を動かし、退避させたn-1枚をその上に重ねる」という再帰（Recursion）の概念を視覚的に理解する最高峰の教材です。

身につく武器・思考力

プログラミングやアルゴリズムで最も重要な「分割統治法（Divide and Conquer）」と再帰的思考力、および指数関数（$2^n$）の爆発的な増大スケール感覚が身につきます。

実社会・ITでの活躍現場

•プログラミング言語のコールスタック構造と再帰アルゴリズム設計
•ファイルのバックアップ世代管理（Grandfather-Father-Son スケジューリング）
•数学的帰納法を用いたアルゴリズムの正当性証明

Layer 1 — 直感・シミュレーター

柱をクリックして一番上の円盤を選択し、移動先の柱をクリックして運んでください。円盤の枚数（3枚、4枚、5枚）を切り替えて、手数が指数関数的に増えていく感覚をパズルとして楽しめます。

再帰と指数関数パズル：ハノイの塔

すべての円盤を一番右の柱へ移せ。最小手数は 2ⁿ - 1 手！

現在の手数: 0 手理論最小手数: 7 手

A (起点)

B (中継)

C (目的地)

※ 柱をクリックして一番上の円盤を選択し、移動先の柱をクリックして運んでください。

直感チェック！ミニクイズ

円盤が「5枚」のハノイの塔を最短の手数でクリアする場合、必要な手数は何手でしょうか？

Layer 2 — 定義・受験・証明

定義

円盤の枚数を $n$ としたとき、 $n$ 枚のハノイの塔を解く最小手数 $T_n$ は、漸化式 $T_1 = 1,\; T_n = 2T_{n-1} + 1$ で定義される数列です。

公式・数理モデル

T_n = 2^n - 1 \quad (T_1 = 1, \; T_n = 2T_{n-1} + 1)

証明・導出

最大の円盤を柱Aから柱Cへ移動させるためには、その上にある $n-1$ 枚の円盤がすべて補助柱Bに移動していなければなりません（手数 $T_{n-1}$ ）。次に最大円盤を1手で柱Cへ移動させ（1手）、最後に補助柱Bにある $n-1$ 枚を柱Cへ移動させます（手数 $T_{n-1}$ ）。したがって $T_n = 2T_{n-1} + 1$ 。両辺に 1 を加えると $T_n + 1 = 2(T_{n-1} + 1)$ となり、数列 $\{T_n + 1\}$ は初項 $T_1 + 1 = 2$ 、公比 2 の等比数列となるため、 $T_n + 1 = 2^n \implies T_n = 2^n - 1$ が導かれます。

押さえておきたいポイント

最小手数は $2^n - 1$ 手（3枚:7手, 4枚:15手, 5枚:31手, 10枚:1023手）
分割統治法（問題を同じ構造の小さな部分問題に分割する）の典型例
ハノイの塔の状態遷移グラフはシェルピンスキーのガスケット（フラクタル構造）を描く

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

再帰呼び出しによるハノイの塔自動ソルバー

最小手数でハノイの塔を解く手順（どの柱からどの柱へ動かすか）をすべて標準出力・配列化するTypeScriptの再帰関数です。

1export interface MoveStep {
2  disk: number;
3  from: string;
4  to: string;
5}
6
7export function solveHanoi(
8  n: number,
9  fromPeg: string = "A",
10  toPeg: string = "C",
11  auxPeg: string = "B"
12): MoveStep[] {
13  const steps: MoveStep[] = [];
14
15  function move(disk: number, from: string, to: string, aux: string) {
16    if (disk === 1) {
17      steps.push({ disk: 1, from, to });
18      return;
19    }
20    // 1. 上の disk - 1 枚を補助柱へ退避
21    move(disk - 1, from, aux, to);
22    // 2. 最底の円盤を目的地へ移動
23    steps.push({ disk, from, to });
24    // 3. 補助柱の disk - 1 枚を目的地へ重ねる
25    move(disk - 1, aux, to, from);
26  }
27
28  move(n, fromPeg, toPeg, auxPeg);
29  return steps;
30}
31
32// 実行例:
33// const solution = solveHanoi(3);
34// console.log(`総手数: ${solution.length}手`); // 7手