經典數學遊戲：三根柱子 A、B、C。A 柱自下而上疊放 n 個直徑遞減的圓盤。目標：將所有圓盤移動到 C 柱，規則：
設 move(n, from, to, aux) 表示將 n 個圓盤從 from 移到 to，借助 aux。
from → tofrom 移到 aux（借助 to）from 移到 toaux 移到 to（借助 from）
public class HanoiTower {
private static int step = 0;
public static void main(String[] args) {
int n = 3; // 圓盤數
System.out.println("=== 漢諾塔 " + n + " 層移動步驟 ===");
move(n, 'A', 'C', 'B');
System.out.println("總步數：" + step + " (理論最少 2^n-1 = " + ((1<=== 漢諾塔 3 層移動步驟 === 第 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 總步數：7 (理論最少 2^n-1 = 7)
move(3, A, C, B) ├─ move(2, A, B, C) │ ├─ move(1, A, C, B) → 1:A→C │ ├─ 2:A→B │ └─ move(1, C, B, A) → 1:C→B ├─ 3:A→C └─ move(2, B, C, A) ├─ move(1, B, A, C) → 1:B→A ├─ 2:B→C └─ move(1, A, C, B) → 1:A→C
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間複雜度 | O(2^n) | 遞迴關係 T(n) = 2T(n-1) + 1，解得 T(n) = 2^n - 1 |
| 空間複雜度 | O(n) | 遞迴調用棧最大深度 n |
| 最優解步數 | 2^n - 1 | 證明：每個圓盤至少移動一次，最大圓盤移動 1 次，其餘各移動 2 次 |
public static void moveIterative(int n, char from, char to, char aux) {
// 任務幀：n, from, to, aux, state(0=開始,1=步驟1完成,2=步驟2完成)
class Frame { int n; char f,t,a; int state; }
Deque stack = new ArrayDeque<>();
stack.push(new Frame(n, from, to, aux, 0));
while (!stack.isEmpty()) {
Frame cur = stack.peek();
if (cur.n == 1) {
System.out.println("移動圓盤 1 從 " + cur.f + " 到 " + cur.t);
stack.pop();
continue;
}
switch (cur.state) {
case 0: // 執行步驟1：move(n-1, from, aux, to)
cur.state = 1;
stack.push(new Frame(cur.n-1, cur.f, cur.a, cur.t, 0));
break;
case 1: // 執行步驟2：移動第 n 個
System.out.println("移動圓盤 " + cur.n + " 從 " + cur.f + " 到 " + cur.t);
cur.state = 2;
break;
case 2: // 執行步驟3：move(n-1, aux, to, from)
cur.state = 3;
stack.push(new Frame(cur.n-1, cur.a, cur.t, cur.f, 0));
break;
default: // 完成
stack.pop();
}
}
}
| 變體 | 規則變化 | 解法思路 |
|---|---|---|
| 四柱漢諾塔 | 增加 D 柱 | Frame-Stewart 算法：分成 k 和 n-k 兩組，最優 k 尚無通用公式 |
| 循環漢諾塔 | 柱子排成環，只能順/逆時針移動 | 移動次數 3^n - 1，遞迴關係變化 |
| 雙色漢諾塔 | 圓盤黑白交替，同色不可疊放 | 狀態空間擴大，需 BFS/A* 搜索 |
| 可重複圓盤 | 允許相同大小圓盤 | 狀態表示增加計數器，動態規劃 |
漢諾塔是理解遞迴分治、問題分解、狀態轉移的最佳模型。核心洞見：「將大問題分解為相同結構的小問題，信任遞迴調用能正確解決子問題，專注於當前層級的組合邏輯」。這種思維是掌握動態規劃、回溯、分治算法的基石。
