汉诺塔问题是经典的递归算法案例，其核心是将问题分解为子问题。以下是清晰的解决思路和代码实现：
问题分析
- 问题描述：将 $n$ 个盘子从柱子 A 借助柱子 B 移动到柱子 C
- 规则：
- 每次只能移动一个盘子
- 大盘子不能放在小盘子上方
- 递归思想：
- 当 $n=1$ 时：直接将盘子从 A 移动到 C
- 当 $n>1$ 时： $$ \begin{cases} \text{1. 将 } n-1 \text{ 个盘子从 A 借助 C 移动到 B} \ \text{2. 将第 } n \text{ 个盘子从 A 移动到 C} \ \text{3. 将 } n-1 \text{ 个盘子从 B 借助 A 移动到 C} \end{cases} $$
C++ 实现
#include <iostream> using namespace std; void move(int n, char from, char to) { cout << "移动盘子 " << n << " : " << from << " -> " << to << endl; } void hanoi(int n, char A, char B, char C) { if (n == 1) { move(n, A, C); } else { hanoi(n - 1, A, C, B); // 步骤1 move(n, A, C); // 步骤2 hanoi(n - 1, B, A, C); // 步骤3 } } int main() { int n = 3; // 示例：3个盘子 hanoi(n, 'A', 'B', 'C'); return 0; }输出示例（n=3）
移动盘子 1 : A -> C 移动盘子 2 : A -> B 移动盘子 1 : C -> B 移动盘子 3 : A -> C 移动盘子 1 : B -> A 移动盘子 2 : B -> C 移动盘子 1 : A -> C复杂度分析
- 时间复杂度：$O(2^n)$
递推关系：$T(n) = 2T(n-1) + 1$ - 空间复杂度：$O(n)$（递归栈深度）
通过递归将大问题分解为相同结构的子问题，是解决汉诺塔问题的核心思想。建议通过调试观察 $n=2,3$ 时的调用栈来深入理解递归过程。
