Tower of Hanoi

汉诺塔怎么玩

汉诺塔是经典的递归益智游戏。所有圆盘一开始由大到小、最大的在最下面，全部叠在左边的柱子上。你要把整叠圆盘搬到右边的柱子，一次只能搬一个，并遵守两条规则：每次只能搬动某根柱子最上面的圆盘，而且永远不能把大的圆盘叠在小的上面。点一根柱子拿起它最上面的圆盘，再点另一根柱子把它放下。目标是用最少的步数，在右边的柱子重新叠好这座塔。

最少步数与 2^n−1 公式

解开 n 个圆盘的汉诺塔，所需的最少步数正好是 2ⁿ − 1。三个圆盘要 7 步，四个要 15 步，五个要 31 步。没有任何走法能突破这个下限，所以排行榜上等于 2ⁿ − 1 的成绩就是完美的最佳解。

递归解法策略

• 要把 n 个圆盘从来源柱搬到目标柱，先把最上面的 n − 1 个圆盘搬到备用（辅助）柱。
• 把最大的那个圆盘直接从来源柱搬到目标柱。
• 最后，把备用柱上的 n − 1 个圆盘搬到最大圆盘的上面。每一个子堆叠都用同样的方法解，一路递归到只剩一个圆盘为止。

汉诺塔要怎么用最少步数解？套用上面的递归：把问题拆成「先把 n−1 个移开、搬走最大的、再把 n−1 个移回来」。还有一个简单的迭代技巧——每隔一步就把最小的圆盘朝同一个循环方向移动，中间再做唯一的另一个合法移动——同样能重现最佳的 2ⁿ − 1 步序列。