目錄

問題描述

?第一性原理分析

代碼實現

第一步：明確函數要干什么

第二步：寫好遞歸的“結束條件”

第三步：寫遞歸步驟?

?🌳 遞歸調用樹

🔍復雜度分析

時間復雜度：T(n) = 2^n - 1

?空間復雜度分析

---

問題描述

有三個柱子（A, B, C），上面有 n 個大小不等的圓盤，最開始所有圓盤按從大到小順序堆在柱子 A 上。
目標：將所有圓盤移動到柱子 C，移動時要滿足：

1. 一次只能移動一個盤子；

2. 任何時刻小盤子不能壓在大盤子上。

?核心問題：

如何將 n 個盤子 從 A 移動到 C，同時只用 B 做輔助，且不違反約束？

?第一性原理分析

🔹1.基礎情況（Base Case）

• n = 1：只有一個盤子，直接從 A → C，一步解決。這是最小子問題。

🔹2. 如果有兩個盤子，要怎么動？

設柱子為 A（起始）、B（輔助）、C（目標）：

你會這樣操作：

1. 把小盤子從 A → B

2. 把大盤子從 A → C

3. 再把小盤子從 B → C

?🔹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???????

這就引出一個關鍵邏輯：

? 要移動第 n 個（最大）盤子，必須先把上面的 n-1 個盤子“暫時”搬開。

🧩 移動 n 個盤子的本質是 —— 找出一個“序列”，讓我們可以先清掉上面的 n-1 個盤子，再移動第 n 個，然后再恢復那 n-1 個。

換句話說：

• 把 n-1 個盤子移到輔助柱；

• 把第 n 個（最大）盤子移到目標柱；

• 再把那 n-1 個盤子從輔助柱移回來。

這三步操作可以形成遞歸：

Hanoi(n, A, B, C):1. 移動 n-1 個盤子從 A → B（借助 C）Hanoi(n-1, A, C, B)2. 移動第 n 個盤子從 A → C3. 移動 n-1 個盤子從 B → C（借助 A）Hanoi(n-1, B, A, C)

📐 所以從第一性來看，漢諾塔的“遞歸”，不是魔法，而是邏輯：

• 沒有任何一步是“看上去神奇的”；

• 每一個盤子的移動，都必須建立在“先讓出空間”的原則上；

• 這就導致了問題具有自相似性：每一層和上面那一層的問題結構一樣；

原理	對應在漢諾塔問題的體現
?本質原子操作	移動一個盤子，必須遵守限制
?問題的自相似性	每個子問題與原問題結構完全一樣 ? 遞歸自然產生
?從底向上構建解決結構	不依賴公式，從 n = 1 出發，構建到 n = 2, 3...

---

代碼實現

第一步：明確函數要干什么

我們要寫的是一個函數：移動 n 個盤子從柱子 A → 柱子 C，借助柱子 B。

?所以我們需要：

• 盤子的數量：int n

• 三個柱子的名字（我們用字符）：char from, temp, to

#include <iostream>
using namespace std;// 函數聲明：移動 n 個盤子，從 from → to，借助 temp
void hanoi(int n, char from, char temp, char to) {

解釋：

• n：要移動的盤子數

• from：起始柱

• temp：中轉柱（輔助）

• to：目標柱

第二步：寫好遞歸的“結束條件”

為什么要加“終止條件”？

如果你不加，遞歸會無限下去，直到程序崩潰！

    if (n == 1) {cout << "Move disk 1 from " << from << " to " << to << endl;return;}

解釋：

• 如果只剩一個盤子，那就是最簡單的情況，直接從 from → to。

• cout 是打印這一步。

第三步：寫遞歸步驟?

    // 1. 把 n-1 個盤子從 from → temp，借助 tohanoi(n - 1, from, to, temp);// 2. 把第 n 個盤子從 from → tocout << "Move disk " << n << " from " << from << " to " << to << endl;// 3. 把 n-1 個盤子從 temp → to，借助 fromhanoi(n - 1, temp, from, to);
}

分析這三步邏輯：

1. 把頂部的 n-1 個盤子先“挪走”（遞歸調用自己）；

2. 把第 n 個盤子（最大的）真正地移動到底部（打印出來）；

3. 把剛才挪走的 n-1 個盤子搬回來（遞歸調用自己）。

完整代碼

#include <iostream>
using namespace std;// 遞歸函數：將 n 個盤子從 from 移動到 to，借助 temp
void hanoi(int n, char from, char temp, char to) {if (n == 1) {cout << "Move disk 1 from " << from << " to " << to << endl;return;}// 第一步：把 n-1 個盤子從 from → temphanoi(n - 1, from, to, temp);// 第二步：移動第 n 個盤子到目標柱cout << "Move disk " << n << " from " << from << " to " << to << endl;// 第三步：把 n-1 個盤子從 temp → tohanoi(n - 1, temp, from, to);
}int main() {int n;cout << "Enter number of disks: ";cin >> n;hanoi(n, 'A', 'B', 'C');return 0;
}

---

?🌳 遞歸調用樹

我們現在來畫出 hanoi(3, A, B, C) 的調用樹結構，說明遞歸是怎么層層展開的。

                            hanoi(3, A, B, C)/         |         \hanoi(2, A, C, B)     Move 3     hanoi(2, B, A, C)/     |     \                       /     |     \hanoi(1,A,B,C)  M2  hanoi(1,C,A,B)   hanoi(1,B,C,A)  M2  hanoi(1,A,B,C)

?標上實際操作編號：

                            hanoi(3, A, B, C)/         |         \hanoi(2, A, C, B)     Move 3     hanoi(2, B, A, C)/     |     \                       /     |     \hanoi(1,A,B,C)  M2  hanoi(1,C,A,B)   hanoi(1,B,C,A)  M2  hanoi(1,A,B,C)/          |         \          |         /          |         \
step1         step2    step3      step4    step5     step6       step7

調用	操作內容	A	B	C
hanoi(3, A, B, C)	主函數入口	[3, 2, 1]	[]	[]
hanoi(2, A, C, B)	把上面兩個盤子從 A ? B
hanoi(1, A, B, C)	直接移動盤子 1
Move disk 1 A→C	Step 1	[3, 2]	[]	[1]
Move disk 2 A→B	Step 2	[3]	[2]	[1]
Move disk 1 C→B	Step 3	[3]	[2, 1]	[]
Move disk 3 A→C	Step 4	[]	[2, 1]	[3]
hanoi(2, B, A, C)	把兩個盤子從 B ? C
Move disk 1 B→A	Step 5	[1]	[2]	[3]
Move disk 2 B→C	Step 6	[1]	[]	[3, 2]
Move disk 1 A→C	Step 7	[]	[]	[3, 2, 1]

---

🔍復雜度分析

時間復雜度：T(n) = 2^n - 1

漢諾塔的遞歸形式是這樣的：

T(n) = 2 * T(n - 1) + 1

意思是：

• 為了移動 n 個盤子：

  • 我們要先移動 n - 1 個盤子（第一次調用）；

  • 移動第 n 個盤子（+1 次）；

  • 再移動 n - 1 個盤子（第二次調用）。

利用迭代展開式來看：

T(n) = 2*T(n-1) + 1= 2*(2*T(n-2) + 1) + 1 = 4*T(n-2) + 2 + 1= 8*T(n-3) + 4 + 2 + 1= ...= 2^k * T(n - k) + (2^(k-1) + ... + 2 + 1)

?當 k = n-1 時，T(1) = 1，代入得到：

T(n) = 2^(n - 1) * T(1) + (2^(n - 2) + ... + 1)= 2^(n - 1) * 1 + (2^(n - 1) - 1)= 2^n - 1

所以時間復雜度是：?? T(n) = O(2^n)

也就是說：

• 每增加一個盤子，所需的移動次數翻倍 + 1。

• 極其不可擴展。

?空間復雜度分析

我們來看遞歸函數會“開多少層棧”：

void hanoi(int n, char from, char temp, char to)
{if (n == 1) return;hanoi(n - 1, from, to, temp); // 一次遞歸調用// move...hanoi(n - 1, temp, from, to); // 第二次遞歸調用
}

遞歸深度分析：

• 最大的遞歸深度就是從 n → n-1 → n-2 → ... → 1

• 所以最多開 n 層函數棧

所以空間復雜度是：🧠 Space: O(n)

• 因為遞歸是深度優先遍歷

• 不會存儲所有子問題，只保存當前路徑

🕊? 如果你是“神廟僧侶”，每天只移動 1 次？

漢諾塔在傳說中是：64 個金盤子，僧侶每天移動一塊。

T(64) = 2^64 - 1 ≈ 1.84 × 10^19 次

即使 1 秒動一次，你也需要：

≈ 5.8 × 10^11 年

而宇宙年齡都才 138 億年。所以說移動 64?個盤子“永遠也完成不了”。