汉诺塔的圆盘有 n 个时,把塔移到另一根柱子的最少步数是 2ⁿ−1 次。就是把 2 乘上圆盘个数那么多次,再减去 1 的数。

圆盘个数最少步数
1 个1 次
2 个3 次
3 个7 次
4 个15 次
5 个31 次
6 个63 次
7 个127 次
8 个255 次
9 个511 次

圆盘每多 1 个,步数就差不多翻一倍。我们来依次看看为什么会这样。

关注最大的圆盘

来想一想把 n 个圆盘的塔从左侧移到右侧。最大的圆盘在其他圆盘的下面,所以原样是动不了的。要把大圆盘搬到右侧,在那一瞬间必须是下面的状态。

  • 大圆盘上面,什么都没有。
  • 右侧柱子是空的(因为比大圆盘小的圆盘,不能放在它下面)。

也就是说,剩下的 n−1 个圆盘,必须全部叠在中间的柱子上。

把步数分成 3 部分

由此,移动 n 个圆盘的步骤可以分成下面 3 部分。

  1. 把上面的 n−1 个圆盘,从左侧移到中间。
  2. 把最大的圆盘,一步从左侧移到右侧。
  3. 把中间的 n−1 个圆盘,移到大圆盘上面。

第 1 步和第 3 步,都正是“移动 n−1 个圆盘的塔”这个问题。把 n 个圆盘的最少步数记作 T(n),就有

T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1

这样的关系。1 个圆盘时是 1 次,所以 T(1) = 1。由此依次可以求出 3、7、15、31……

式子为什么是 2ⁿ−1

在这个关系的两边加上 1,就得到

T(n) + 1 = 2 × (T(n−1) + 1)

也就是说,“步数加 1 的数”,圆盘每多 1 个就正好翻一倍。1 个圆盘时 T(1) + 1 = 2,所以 n 个圆盘时就是 2 乘 n 次的 2ⁿ。再减去 1,就得到 T(n) = 2ⁿ−1。

为什么不可能比这更少

上面的步骤能用 2ⁿ−1 次移完,这一点已经清楚了。那么,有没有更少步数的方法呢?

正如刚才所说,第一次移动大圆盘的瞬间,剩下的 n−1 个圆盘必须全部叠在另外一根柱子上。在这之前,至少要花移动 n−1 个圆盘的塔的步数。同样,把大圆盘最后放到右侧之后,要把剩下的 n−1 个圆盘重新叠到它上面,也至少要花移动 n−1 个圆盘的塔的步数。大圆盘本身,至少也要动 1 次。

不管什么步骤,这 3 部分步数都必定要花。所以,不可能比 2 × T(n−1) + 1 次更少。人们还知道,最少步数的走法其实只有这 1 种。

应用的“经典”模式是 127 步

“汉诺塔”应用的经典模式是 7 个圆盘,所以最少步数是 2⁷−1 = 127 步。步数达到 127,就说明是用最少步数的走法解开的。按玩法文章里介绍的“把小圆盘朝同一个方向绕行”的走法,正好 127 步完成。