递归解密：汉诺塔算法精解

汉诺塔问题是经典的递归算法案例，其核心是将问题分解为子问题。以下是清晰的解决思路和代码实现：

问题分析

1. 问题描述：将 $n$ 个盘子从柱子 A 借助柱子 B 移动到柱子 C
2. 规则：
   • 每次只能移动一个盘子
   • 大盘子不能放在小盘子上方
3. 递归思想：
   • 当 $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$ 时的调用栈来深入理解递归过程。