汉诺塔几乎是学编程时讲到“递归”必定会出现的题材。用手解要走几百步,写成程序却只要几行。下面就来依次看看其中的道理。柱子分为左、中、右,圆盘按从小到大的顺序编号为 1、2、3……
什么是递归
递归,就是在解决某个问题的步骤中,把同样的步骤用到更小的问题上。问题越缩越小,总会碰到答案一眼就能看出来的问题(比如 0 个圆盘就什么都不用做),到那里就停下来。
用递归来思考汉诺塔
来想一想怎样把 n 个圆盘的塔从左侧移到右侧。
- 把上面的 n−1 个圆盘,从左侧移到中间。
- 把最大的圆盘 n,从左侧移到右侧。
- 把中间的 n−1 个圆盘,移到右侧。
第 1 步和第 3 步都是“移动 n−1 个圆盘的塔”的问题,和原来的问题是同样的形式。不同的只是从哪根柱子移到哪根柱子。所以,只要写出一套“借助剩下的那根柱子,把 n 个圆盘从某根柱子移到另一根柱子”的步骤,就能在里面调用它自己。
伪代码
步骤 hanoi(n, 起点, 终点, 辅助柱):
如果 n 是 0,什么都不做,直接结束
hanoi(n − 1, 起点, 辅助柱, 终点) … 把上面的 n−1 个圆盘移开
把圆盘 n 从 起点 移到 终点
hanoi(n − 1, 辅助柱, 终点, 起点) … 把 n−1 个圆盘移回来
执行 hanoi(3, 左, 右, 中) 就会得出把 3 个圆盘从左侧移到右侧的步骤 只要这些,无论多少个圆盘,都能得出最少步数的走法。能实际运行的 Python 和 C 语言代码,在用 Python 和 C 语言解汉诺塔里有介绍。
调用的展开方式
3 个圆盘时,把 hanoi 是怎样被调用的写出来,就会得到下面这样的树形。缩进越深,就是越里层的调用。
hanoi(3, 左→右)
├─ hanoi(2, 左→中)
│ ├─ hanoi(1, 左→右) … 把 1 移到右侧
│ ├─ 把 2 移到中间
│ └─ hanoi(1, 右→中) … 把 1 移到中间
├─ 把 3 移到右侧
└─ hanoi(2, 中→右)
├─ hanoi(1, 中→左) … 把 1 移到左侧
├─ 把 2 移到右侧
└─ hanoi(1, 左→右) … 把 1 移到右侧 从上往下依次读出来的“移动”,就是这 7 步的答案。一次调用会在里面产生两次调用,所以圆盘每多 1 个,工作量就差不多翻一倍。
计算量
| 要看的项目 | n 个圆盘时 |
|---|---|
| 移动的次数(步数) | 2ⁿ−1 次 |
| 调用 hanoi 的次数(0 个圆盘的调用也算) | 2ⁿ⁺¹−1 次 |
| 调用的深度(需要同时记住的量) | n+1 层 |
步数为什么是 2ⁿ−1 次,在最少步数公式里做了证明。所需时间随圆盘个数呈指数增长(O(2ⁿ)),而需要记住的量只和圆盘个数成正比(O(n))。步数本身就有 2ⁿ−1 次,所以不管怎么改进,要把步骤全部写出来,就是需要这么多时间。
不用递归的解法
不用递归,只靠循环也能解。这就是解法的文章里介绍的、用手解时的那套步骤。
步骤 hanoi_loop(n):
确定 1 的移动方向(n 是奇数就按 左→右→中,偶数就按 左→中→右 的顺序)
对 步 = 1, 2, 3, … , 2ⁿ − 1 重复:
如果 步 是奇数,就把圆盘 1 按确定的方向移到相邻的一根柱子
如果 步 是偶数,就比较没有放 1 的两根柱子最上面的圆盘,
把小的移到大的上面(或空柱子) 不像递归那样需要记住调用,所以用到的内存非常少。
用二进制直接求出任意一步
还有一种方法,不用顺着前面的步骤走,就能直接求出第几步该做什么。把柱子按 0、1、2 编号,对第 m 步(从 1 开始数):
- 要移动的圆盘,是把 m 写成二进制后,末尾连续 0 的个数 + 1 号圆盘。
- 起点柱子,是 (m AND (m − 1)) 除以 3 的余数。
- 终点柱子,是 ((m OR (m − 1)) + 1) 除以 3 的余数。
AND 和 OR,是二进制逐位的“且”和“或”运算。比如 m = 4(二进制是 100),末尾有 2 个 0,所以圆盘是 3 号;起点是 (4 AND 3) = 0,即 0 号柱子;终点是 ((4 OR 3) + 1) = 8,8 除以 3 的余数是 2,即 2 号柱子。
这个式子得出的步骤,圆盘是奇数个时是从 0 号柱子移到 2 号柱子,偶数个时是从 0 号柱子移到 1 号柱子。偶数个圆盘想移到 2 号柱子时,把 1 号和 2 号柱子互换着读就行。步数和二进制的这些联系,在规律性的文章里有更详细的介绍。
