汉诺塔

#汉诺塔

• 游戏规则
• 解决思路
• 递归解法
• 数学归纳法证明
• 时间复杂度

#游戏规则

有 3 根柱子 A、B、C，柱子 A 上有 n 个圆盘（从下到上由大到小）。目标是把所有圆盘按原来的顺序移到柱子 C。

移动条件：

1. 一次只能移动 1 个圆盘
2. 不能把大的圆盘放在小的圆盘上

初始状态:               目标状态:
  |         |         |       |         |         |
  -         |         |       |         |         |
 ---        |         |       |         |         |
-----       |         |       |         |         |
  A         B         C       A         B         C

#解决思路

关键洞察：移动 n 个圆盘 = 移动 n-1 个圆盘 + 移动最大圆盘 + 再移动 n-1 个圆盘。

2 个圆盘的情况：

1. 把小圆盘从 A 移到 B
   -    |    |
  ---   |    |
   A    B    C

2. 把大圆盘从 A 移到 C
   |    |    -
   |    |   ---
   A    B    C

3. 把小圆盘从 B 移到 C → 完成！
   |    |    -
   |    |   ---
   |    |   ---
   A    B    C

3 个圆盘的情况：忽略最大的圆盘，先把上面 2 个移到 B（按 2 圆盘的方法），再把最大的移到 C，最后把 B 上的 2 个移到 C。

#递归解法

hanoi(n, A, B, C):
  if n == 1:
    把圆盘从 A 移到 C
  else:
    hanoi(n-1, A, C, B)  ← 把 n-1 个圆盘从 A 移到 B（借助 C）
    把第 n 个圆盘从 A 移到 C
    hanoi(n-1, B, A, C)  ← 把 n-1 个圆盘从 B 移到 C（借助 A）

在算法描述中调用算法自身的方法就叫递归。归并排序和快速排序都是递归算法。

#数学归纳法证明

不管多少个圆盘，最终都能达成目标：

1. n=1：直接移过去，显然可以
2. 假设 n 个圆盘可以：那么 n+1 个圆盘时，先把 n 个移到 B，把最大的移到 C，再把 n 个移到 C

#时间复杂度

T(n) = 2 × T(n-1) + 1
     = 2ⁿ - 1

移动 n 个圆盘需要 2ⁿ - 1 步，时间复杂度为 O(2ⁿ)。

传说有 64 个圆盘的汉诺塔，僧侣们搬完之日就是世界末日。按每秒 1 步算，需要约 5800 亿年——远超宇宙年龄。

#小结

• 汉诺塔是递归的经典示例
• 移动 n 个圆盘 = 移动 n-1 个 + 移动 1 个 + 移动 n-1 个
• 时间复杂度 O(2ⁿ)，指数级增长
• 理解递归的最佳入门案例