圆盘3
0 / 7最少步
00:00

最少步数：7 步

n 个圆盘最少要走 2ⁿ − 1 步。 现在 n = 3，所以最少是 2^3 − 1 = 7。 每多一个圆盘，最少步数大约翻一倍再加 1。

先点起始柱拿起顶部圆盘，再点目标柱放下。大盘不能压在小盘上。

联机竞速 · 邀请好友

联网竞速

同盘数通关，步数少者胜，步数相同比用时。

当前设置：3 个圆盘

什么是汉诺塔？

汉诺塔是经典的递归问题：将 n 个大小不同的圆盘从起始柱 A 移动到目标柱 C，每次只能移动一个圆盘，且大盘不能放在小盘上方。中间柱 B 可作辅助。

递归解法

  1. 将上面 n−1 个圆盘从 A 移到 B（以 C 为辅助）
  2. 将最大圆盘从 A 移到 C
  3. 将 n−1 个圆盘从 B 移到 C（以 A 为辅助）

这三步本身就是递归的——步骤 1 和 3 是规模更小的汉诺塔问题。

时间复杂度

递推关系: T(n) = 2·T(n−1) + 1，解为 T(n) = 2ⁿ − 1。 这意味着 3 个盘最少 7 步，8 个盘最少 255 步——每增加一个盘，步数翻倍加一。

与二进制的联系

汉诺塔的每一步可以用二进制数来编码：将步骤编号写成二进制，最低位的 1 所在位置就是要移动的圆盘编号。这揭示了递归结构和二进制计数之间的深层联系。

试试自动演示

点击「自动演示」可以观看递归算法一步步执行。调整速度，仔细观察圆盘的移动模式——你会看到递归的「自相似」结构。