汉诺塔算法的分析与设计

马健喆

摘 要： 为了提升学生的编程能力，从解决计算机科学和应用中经典的汉诺塔问题入手，分析了分治算法与递归算法的关系，分别给出了分治算法、递归算法的设计步骤，给出了分治法的时间复杂度计算公式和求解方法。深入分析了汉诺塔问题的简化过程、分解步骤，设计了汉诺塔算法，给出了完成汉诺塔搬迁需要移动盘子次数的计算公式和求解方法。使学生能够把所学的方法用于解决具体问题，并对算法进行比较分析，从而将理论和实际应用切实结合起来。

关键词： 汉诺塔； 时间复杂度； 递归方法； 分治算法

中图分类号：TP302 文献标志码：A 文章编号：1006-8228（2015）08-49-03

Analysis and design of Hanoi tower algorithm

Ma Jianzhe

（School of Information Engineering， Taiyuan University of Technology， Taiyuan， Shanxi 030024， China）

Abstract： In order to improve the students' ability of programming， starting with the classic Hanoi tower problem in computer science and application， this paper analyzes the relationship between the divide-and-conquer algorithm and the recursive algorithm， gives the design steps of the divide-and-conquer algorithm and the recursive algorithm respectively， gives the calculation formula and the solving method of the time complexity for the divide-and-conquer algorithm， deeply analyzes the simplification process and the decomposition steps of Hanoi tower problem， designs the algorithm for Hanoi tower problem， and gives the calculation formula and the solving method to work out the number of movements required to complete relocation of Hanoi tower. Student can use the method learnt to solve the specific problems， thereby combine theory with practical application.

Key words： Hanoi tower； time complexity； recursive method； divide-and-conquer algorithm

0 引言

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，计算也越容易。要解决一个较大的问题，有时是相当困难的。分治策略是应用最多的一种有效方法，它的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题无疑是会容易些，由此得出原问题的解，就是所谓的“分而治之”的意思。分治策略还可以递归，即子问题仍然可以用分治策略来处理，最后的问题非常基本而且简单[1-2]。

分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。实现算法的同时，需要估计算法所需时间。分治算法在每一层递归上分为三个步骤。

⑴ 分：将原问题分解成一系列子问题。

⑵ 治：递归地解各子问题，若子问题足够小，则直接解之。

⑶ 合：将子问题的结果合并成原问题的解。

分治算法的时间由解决各个子问题所需的时间（由子问题的个数、解决每个子问题的时间决定）确定。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

在C语言中，重复性操作可以通过循环结构或者递归结构完成。递归结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便[3-5]。

从递归算法的结构来分析，设计递归算法时，无非要解决两个问题：递归出口和递归体。即要确定何时到达递归出口，何时执行递归体，执行什么样的递归体。递归算法设计的关键是保存每一层的局部变量并运用这些局部变量。由此，递归算法的设计步骤可从以下三步来进行：

⑴ 分析问题，分解出小问题；

⑵ 找出小问题与大问题之间的关系，确定递归出口；

⑶ 写出算法。

评定算法优劣的标准要看它的时间复杂性、空间复杂性和人工复杂性，其中时间复杂性最为重要，通常是用时间复杂性来衡量某个算法的“好”或“坏”。不同的算法具有不同的时间复杂性函数，说它们当中哪些“效率足够高”，哪些“效率太低”，总要看当时的情况。但是，计算机科学家公认一种简单的区别，这种区别对这些问题提供了重要的透彻的分析，这就是多顶式时间算法和非多顶式时间算法之间的区别。时间复杂性表示成n的函数T（n）。凡是T（n）为n的对数函数、线性函数或多项式的幂函数（也是多项式的特例），称这类算法为“有效算法”，或好的算法；反之，凡是T（n）为指数函数或阶乘函数的，称之为坏的算法。

1 分治法的时间复杂度分析

从分治法的一般设计模式可以看出，用它设计出的算法一般是递归算法。因此，分治法的计算效率通常可以用递归方程来进行分析。一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。为方便起见，设解规模为1的问题耗费1个单位时间。另外，再设将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f（n）个单位时间。如果用T（n）表示该分治法解规模为|P|=n的问题所需的计算时间，则时间复杂度T（n）为：

下面讨论如何求解这个与分治法有密切关系的递归方程。通常可以用展开递归式的方法来解这类递归方程，反复代入求解，解此递归方程可得时间复杂度T（n）。从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。

2 汉诺塔算法设计与分析

相传印度教的天神梵天在创造地球这一世界时，建了一座神庙，神庙里竖有三根宝石柱子，柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，即所谓的汉诺塔（又称Hanoi塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下三条规则：

⑴ 每次只能移动一个盘子；

⑵ 盘子只能在三根柱子上来回移动，不能放在他处；

⑶ 在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。

天神说：“当这64个盘子全部移到第三根柱子上后，世界末日就要到了”。这就是著名的汉诺塔问题。用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，调试、编译、连接和运行，从而形成该问题的求解。图1给出了求解n个圆盘难题的总体求解过程。其汉诺塔问题的算法为：

⑴ 递归调用n-1个圆盘的汉诺塔问题算法，把上面的n-1个圆盘从A柱移到B柱；

⑵ 把最下面的一个圆盘从A柱直接移到C柱；

⑶ 递归调用n-1个圆盘的汉诺塔问题算法，把B柱上临时存放的n-1个圆盘移到C柱。

图1 n个圆盘难题总体求解过程

汉诺塔问题是一个典型的只有用递归方法（而不能用其他方法）来解决的问题。根据递归方法，可发现将64个盘子的汉诺塔问题转化为求解63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上，这样则可以解决64个盘子的汉诺塔问题。依此类推，63个盘子的汉诺塔求解问题可以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问题又可以转化为61个盘子的汉诺塔求解问题，直到1个盘子的汉诺塔求解问题。再由1个盘子的汉诺塔的求解求出2个盘子的汉诺塔，直到解出64个盘子的汉诺塔问题。图2给出了汉诺塔算法的程序流程图。

[n==1？][开始][输入盘子的数量n][调用递归函数hanoi（）][调用move（）函数

将盘子从A移到C][将前n-1个盘子

从A移到B][再将A的第n个

盘子移动到C][最后将B上的n-1个

盘子移到C上] [Y][N] [结束]

图2 汉诺塔算法程序流程图

下面利用C语言给出该问题的求解算法的描述。

hanoi（int n，char left，char middle，char right）

{ if（n==1） move（1，one，_，three）；

else

{ hanoi（n-1，left，right，middle）；

move（1，left，_，right）；

hanoi（n-1，middle，left，right）；

}

}

以上代码中，n表示n个盘子的汉诺塔问题，left表示第一个柱子，middle表示第二个柱子，right表示第三个柱子。函数hanoi（n-1，left，right，middle）表示n-1阶汉诺塔从第一个柱子借助第三个柱子先移到第二个柱子上，函数move（1，left，_，right）表示将第一个柱子上最后一个盘子直接放到第三个柱子上，函数hanoi（n-1，middle，left，right）表示n-1个盘子借助第一个柱子移到第三个柱子上。在以上C语言描述的算法基础上，进行适当扩充就可以形成一个完整的程序，经过编译和连接后，计算机就可以执行这个程序，按照递归的方法将问题求解出来。

现在的问题是当n=64时，即有64个盘子时，需要移动多少次盘子，要用多少时间。按照上面的算法，n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。于是

h（n）=2h（n-1）+1

=2（2h（n-2）+1）+1=22h（n-2）+2+1

=23h（n-3）+22+2+1

……

=2nh（0）+2n-1+…+22+2+1

=2n-1+…+22+2+1=2n-1

因此，要完成汉诺塔的搬迁，需要移动盘子的次数为：

2n-1=18446744073709551615

如果每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。从这个例子可以了解到理论上可以计算的问题，而实际上并不一定能行，这属于算法复杂性方面的研究内容。

图3给出了Hanoi塔问题3圆盘难题的运行结果，可以看到，将3个盘子从第一个柱子移动到第三个柱子需要移动7次。对上述递归在Hanoi塔问题上的应用分析，如果将64个盘子从第一个柱子移动到第三个柱子需要移动264-1次。