《C编程技巧：117个问题解决方案示例 》 —3.7　解决经典的汉诺塔问题

3.7　解决经典的汉诺塔问题

你想用递归的方法解决汉诺塔的经典问题。

解决方案

编写一个C程序，按照以下规格说明使用递归方法解决汉诺塔的经典问题：

程序要求用户输入圆盘数n（1≤n≤10）。

程序定义了函数move()，它以递归方式调用自身来解决问题。

程序在屏幕上显示计算结果。

代码

以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:\Code中，文件名为Hnoi.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理

传说汉诺塔位于汉诺城的一座寺庙中，该地位于亚洲。有三个如图3-4所示的立柱，此外，还有64个金盘，所有金盘的半径都不同。每个圆盘在中心都有一个孔，这样圆盘可以堆叠在任何立柱上，从而形成一个塔，就像一堆堆成纺锤形的CD。首先，圆盘按照从上到下逐渐增加的半径的顺序堆叠在左立柱上（参见图3-4，但该图仅显示了四个圆盘）。寺庙中的僧侣试图将所有64个圆盘都移动到右立柱。中间的立柱可用于临时存放。他们的行为受到以下条件的限制：

应一次移动一个圆盘。

从立柱上取下的圆盘不能放在地上。它必须放在三个立柱中的一个上面。

较大的圆盘不能放在较小的圆盘上面。你当然可以将较小的圆盘放在较大的圆盘上面。

图3-4　在递归过程中可以成功解决经典的汉诺塔问题

人们相信，当完成分配给僧侣的任务时，世界将会终结。计算机科学家对这个问题表现出浓厚的兴趣，因为它显示了递归的效用，而不是因为他们对世界末日的可能性感到担忧。使用递归，可以通过编写一个简单的程序来解决这个问题。虽然你也可以简单地利用迭代而不使用递归来解决这个问题，但程序会变得非常复杂。

出于编程目的，你可以假设左立柱周围堆叠了n个圆盘，其中n是整数变量。圆盘从上到下依次编号，最上面的圆盘编号为1，最下面的圆盘编号为n。让我们开发一个程序，用于将n个圆盘从左立柱移动到右立柱，而不违反前面提到的三个条件中的任何一个。问题可以用递归形式表示如下：

1.使用右立柱来临时存放，将顶部的（n-1）个圆盘从左立柱移动到中间立柱。

2.将第n个圆盘（最大的圆盘，因此也是最下面的圆盘）从左立柱移动到右立柱。

3.使用左立柱来临时存放，将（n-1）个圆盘从中间立柱移动到右立柱。

所有这三个步骤准确无误地出现在LOC 19～25中定义的递归函数move()中。对于每次递归调用，n的值减1，因此递归在有限数量的调用之后停止。此外，n＝0是此程序的停止条件。