汉诺塔

汉诺塔谜题：按照规则把整叠圆盘从柱子 A 移到另一根柱子上。可以自己解，也可以观看自动解法和步骤列表，例如在讲递归的课上使用。

使用方法

1. 选择“圆盘数”，从 3 到 10。
2. 把最上面的圆盘拖到另一根柱子上；或点击一根柱子拿起最上面的圆盘，再点击另一根柱子放下。按键 1、2、3 也可以操作。
3. 点击“撤销”收回一步，或点击“重新开始”从头再来。
4. 卡住时，点击“演示解法”从当前局面开始观看。可以调整“速度”，或点击“暂停”后使用“单步”。

计算方式与说明

• 规则：每次只能移动一个圆盘，只能移动柱子最上面的圆盘，而且永远不能把大圆盘放在小圆盘上。
• n 个圆盘最少需要 2ⁿ − 1 步。移动 n 个圆盘时，先把 n − 1 个圆盘移开，把最大的圆盘移动一次，再把那 n − 1 个圆盘移回到它上面。
• 每种圆盘数的最佳记录保存在这个浏览器中。使用过自动解法的游戏不计入记录。

常见问题

汉诺塔最少要移动多少步？

n 个圆盘需要 2ⁿ − 1 步：3 个圆盘 7 步，4 个 15 步，5 个 31 步，10 个 1,023 步。

汉诺塔有什么简单的解法吗？

每到奇数步，就把最小的圆盘朝同一个方向移到下一根柱子。每到偶数步，就走唯一一种不动最小圆盘的合法移动。

为什么用汉诺塔来讲递归？

n 个圆盘的解法由两个 n − 1 个圆盘的解法加上最大圆盘的一次移动组成，所以 T(n) = 2·T(n − 1) + 1。

能一次看到全部步骤吗？

打开“解法步骤列表”，就能以“圆盘 1：A → C”的形式看到每一步。