汉诺塔问题：如何把n个圆盘从A柱子移动到C柱子？

例2.7　汉诺塔问题。

有3根柱子（A，B，C）和n个不同尺寸的圆盘（1，2，3，…，n），如图2.11所示。每个圆盘的中心有个孔，圆盘可以堆叠在柱子上。最初，圆盘全部堆在柱子A上，最大的圆盘在最底部，最小的1号圆盘在顶部。要求把所有圆盘都从柱子A移到柱子B上，每次只能移动顶端的一个圆盘，并且不允许把较大的圆盘堆放在较小的圆盘上。可以借助柱子C作为辅助。请找出具体的移动方法。

图2.11　汉诺塔问题

解　根据问题规约法，试着将问题转换为一系列子问题，要把n个圆盘从柱子A移动到柱子B上，可以先完成简单一点的操作，把n-1个圆盘移动到柱子C上，留出最大的圆盘n，然后把n号圆盘移动到柱子B上，剩下的问题就变成了如何把n-1个圆盘从柱子C移动到柱子B上，比原始问题少了一个圆盘，变简单了一点。继续下去，得到规约过程如下：

（1）移动柱子A上的圆盘（1，2，3，…，n-1）到柱子C上的n-1个圆盘问题；(www.xing528.com)

（2）移动柱子A上的圆盘n到柱子B上的1个圆盘问题；

（3）移动柱子C上的圆盘（1，2，3，…，n-1）到柱子B上的n-1个圆盘问题。

同样，n-1个圆盘移动的问题又可以转换为n-2个圆盘和1个圆盘移动的问题，这样形成了一个递归的过程。当最后简化到1个圆盘移动问题时，直接移动就可以了。于是原问题就变成了一组较简单的问题。

用递归方式实现的参考代码如下，对于递归算法的优化方法将在本书3.5节介绍。（完整代码：\C2\s2_7\Tower Of Hanoi.py。）