用最少步数解汉诺塔时,那个步骤里有着令人惊讶的漂亮规律。这里就 n 个圆盘的塔从左侧移到右侧的最少步骤(2ⁿ−1 步),依次介绍能发现的规则。圆盘按从小到大的顺序编号为 1、2、3……
每个圆盘的移动次数是 2 的幂
在最少步骤里,每个圆盘移动的次数是固定的。有 n 个圆盘时,第 k 号圆盘会移动 2ⁿ⁻ᵏ 次。
| 圆盘(4 个圆盘时) | 移动次数 |
|---|---|
| 1 | 8 次 |
| 2 | 4 次 |
| 3 | 2 次 |
| 4 | 1 次 |
| 合计 | 15 次 |
最大的圆盘 1 次,下一个 2 次,再下一个 4 次……每小一号就翻一倍。合计起来是 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1,和最少步数正好一致。
原因用和最少步数公式同样的思路就能明白。移动 n 个圆盘,要把 n−1 个圆盘的塔移动 2 次。所以,比 n 号小的圆盘,动的次数是移动 n−1 个圆盘时的 2 倍。
第几步动哪个圆盘
4 个圆盘的最少步骤里,把从第 1 步开始依次移动的圆盘编号排出来,就是下面这样。
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 每隔一步出现,在它们之间每隔一个有 2,再在它们之间有 3……这和尺子刻度长度的排列(短、中、短、长……)是同样的形状。
这个排列,只要把步数写成二进制,就能马上求出。
| 第几步 | 二进制 | 末尾 0 的个数 | 动的圆盘 |
|---|---|---|---|
| 1 | 1 | 0 个 | 1 |
| 2 | 10 | 1 个 | 2 |
| 3 | 11 | 0 个 | 1 |
| 4 | 100 | 2 个 | 3 |
| 5 | 101 | 0 个 | 1 |
| 6 | 110 | 1 个 | 2 |
| 7 | 111 | 0 个 | 1 |
| 8 | 1000 | 3 个 | 4 |
第 m 步动的,是把 m 写成二进制后“末尾连续 0 的个数 + 1”号圆盘。奇数步的二进制末尾是 1,所以总是动 1。这就是解法的文章里“奇数步动 1”的原因。
此外,起点和终点的柱子,也只靠二进制的计算就能求出(算法的文章)。
与格雷码的联系
把二进制从 0 开始依次数的时候,每加 1 变化的位数各不相同(0111 到 1000 有 4 位变化)。于是,把数排成每前进一步只有 1 位变化的表示方法,叫作“格雷码”。
| 序号 | 格雷码 | 变化的位(从右数) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
变化的位的排列“1 2 1 3 1 2 1”,和汉诺塔里移动的圆盘的排列完全相同。把 1 个圆盘看作二进制的 1 位,认为“那一位变化 = 那个圆盘移动”,那么汉诺塔的最少步骤,就和依次走过格雷码是一回事。
圆盘绕行的方向
解法的文章里介绍过,1 总是朝同一个方向绕行。其实其他圆盘也有同样的规则。
- 奇数号圆盘(1、3、5……),全都和 1 朝同一个方向绕行。
- 偶数号圆盘(2、4、6……),全都和 1 朝相反的方向绕行。
把左侧的塔移到右侧时,奇数个圆盘的话,1 的方向是“左 → 右 → 中间”,偶数个圆盘的话是“左 → 中间 → 右”。每个圆盘,到最后都一次也不改变方向。
还有一条在10 层的解法里介绍过的规则。在最少步骤里,绝不会把奇数号圆盘直接放在奇数号圆盘上,也不会把偶数号圆盘直接放在偶数号圆盘上。
摆放一共有 3ⁿ 种
遵守规则的圆盘摆放,一共有多少种呢?每个圆盘都可以放在 3 根柱子中的任何一根,而放在同一根柱子上的圆盘的顺序,由从大到小就定死了,所以摆放有 3ⁿ 种。
| 圆盘个数 | 摆放数 |
|---|---|
| 3 个 | 27 种 |
| 5 个 | 243 种 |
| 7 个 | 2,187 种 |
| 9 个 | 19,683 种 |
而且,从任何一种摆放到任何一种摆放,遵守规则都一定能移过去。把所有摆放用点表示,再把一步就能互相移动的点用线连起来,得到的图形,也已知和大三角形里套着小三角形的“谢尔宾斯基三角形”很相似。
“汉诺塔”应用的“题目”模式,就是从这所有的摆放里,做出要摆成样本形状的题目。即使是 9 个圆盘的★5,也是把 19,683 种摆放全都查过最少步数之后才出题的。
