目录

问题描述

 第一性原理分析

代码实现

第一步：明确函数要干什么

第二步：写好递归的“结束条件”

第三步：写递归步骤 

 🌳 递归调用树

🔍复杂度分析

时间复杂度：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 个盘子“永远也完成不了”。