汉诺塔的圆盘有 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 部分。
- 把上面的 n−1 个圆盘,从左侧移到中间。
- 把最大的圆盘,一步从左侧移到右侧。
- 把中间的 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 步完成。
