汉诺塔问题（详解）

1问题描述
问题提出：有三个塔(分别为A号，B号和C号)。开始时．有
n个圆形盘以从下到上、从大到小的次序叠置在A塔上。现要将A
塔上的所有圆形盘，借助B搭，全部移动到C搭上。且仍按照原来
的次序叠置。
移动的规则如下：这些圆形盘只能在3个塔问进行移动．一
次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比
它小的盘子的上面。
要求如下：从键盘输入初始圆形盘子个数n．用JAVA实现n
个盘子最佳移动的全过程。
2算法分析
此题的目的是设计一个盘子移动的方案．使得A号塔上的所
有盘子借助于B号塔按照原来的次序移动到C号塔上，并且．要
给出完整的最佳的盘子移动的方案。
我们从实际的、具体的盘子的移动过程来分析．找出问题内
在的规律。经分析无论盘子的个数有多少．是1、2、3..或n个．
也不管我们怎么去移动盘子(当然是按规则来移动)．但在移动的
过程中，将始终会出现这样的状态情况：(n一1)个盘子将会以从下
到上、从大到下的次序叠置在B塔上，这时，A塔上第n个盘子就
能被轻而易举叠放到c塔上；接着，我们再把B塔上的其fn一1)十
盘子移动到C塔上，问靼好像已经解决
但，B塔上fn—1)个盘子怎么移动到C塔上呢?这是我们要解
决的第二个问题。同样，不管我们怎么移动，也将会出现这样的状
态情况：(n一2)个盘子将会以从上到下、从大到小的次序叠置在A
塔上，这时。B塔上第(n一1)个盘子就能被轻而易举放到C塔上；接
着，我们把A塔上的共(n一2)个盘子移动到C塔上。
这样，不断深入，不断细小化，最终，将到达仅有一个盘的情
形。这时，递归也就终止了，问题也得到了解决。通过以上分析．这
里有很明显递归关系
由此，想到了采用递归算法来解决该问题。因为递归算法有这
样特征描述：为了求解出规模力N的问题的解．我们先设法将它分
解成一些规模较小的问题，然后从这些较小问题的解能方便地构
造出大问题的解，并且这些规模较小的问题也能采用同样的方法
分解，分解成规模更小的问题，并能从这些更小的问题的解构造出
规模稍大问题的解。特别地是，当规模N-I时，能直接得到解。
现在，严格按照递归算法来解决问题。先定义递归方法Hanio
(int N，char A，char B，char C)，按如下步骤进行解题(设初始盘子个
数为N)：若A塔上仅仅只有一个盘子(N=1)，则直接从A移动到
C，问题完全解决。若A塔上有一个以上的盘子(N>1)，则需要考虑以下三个步骤。
第一步：把 一1)个盘子从A塔经过移动，叠放到B塔上。在
不违反规则情况下，所有fN一1)个盘子不能作为一个整体一起移
动，而是要符合要求地从一个塔移到另一个塔上。用Hanio(N—1．A，
C，B)调用递归方法，注意：这里是借助于C塔，将(N一1)个盘子从A
塔移动到B塔，A是源塔，B是目标塔。
第二步：将剩下的第N个盘子(也就是最底下的一个)直接从A塔
叠放到空着的C塔上。
第三步 用第一步的方法，再次将B塔上的所有盘子叠放到
C塔上。同样，这一步实际上也是由一系列更小的符合规则的移动
盘子的操作组成的。用Hanio(N一1，B，A，C)调用递归方法，注意：这
里是借助于A塔，将(N—1)个盘子从B塔移动到C塔，B是源塔，℃
是目标塔。
这个算法达到了预期的目标．即在C塔上按正确的次序叠放
了所有的圆形盘子。有了前面问题算j去分析的基础，继而，我们可
以用JAVA来实现算法。
3 JAVA实现
3．1说明如下
(1)n为A塔初始盘子个数；
(2)A塔上盘子从上到下、从小到大编号依次为l，2，3. . ：
(3)Hanio0方法采用递归算法，实现盘子移动的最佳方案：
(5)InputnO方法实现盘子个数n的键盘输入(输入必须为阿
拉伯数字)。
3．2编程如下
import java．io． ；，／引用java包的io子包的所有公有类
public class Hanio／／Hanio类的声明
{static int n；
public static void main(Strin乱J args)throws IOException
I System．out．print(”请输入盘子的个数lI=”)；
n=Integer．parselnt(Inputn0)；
System．out．prindn(”盘子的整个移动过程如下．I ；
Hanio(n， A ， B ， C )；，／调用Hanio方法l
#HanioO方法采用递归算法
public static void Hanio(int N，char A，char B，char C)
{if(N==1)
System．out．prlntln(”Dish l from”+A+”to”+C)；
else ·
{Hanio(N—l，A，C，B)；／／把A上的N一1个盘子借助于C叠放刘
B上
System．out．println(”Dish”+N+”from”+A+”to“+C)：
Hanio(N一1，B，A，C)；／／再把B上的N—1个盘子借助于A叠放到
C上
ll ，，读从键盘输入的数据流的方法
public static String InputnO throws IOException
{String str；
BuferedReader Input=new BuferedReader fnew InputStream．
Reader(System．in11；
str=Input．readLine0；
retum str；}l
3．3编译、解释运行iava程序
上面的代码可以使用记事本录入，保存文件名为Hanio．java。
在运行iava程序前首先使用编译程序iavac进行编译，通过后再
使用java运行即可。具体的命令操作如下。
(1)编译程序
C：＼java>javac Hanio．java
编译成功后生成类文件Hanio．class
(2)运行程序
C：＼java>java Hanio
注：编写iava程序的运行环境必须安装JDK工具包，并进行
配置．可以从WWW．java．com下载。
4总结
其实。递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较为复杂的问题(如规模为N)的求解推到比原问题简
单一些的问题(规模小于N)的求解。’例如上面分析过程中，为求
解Hanio(N，A，B，C)，推到计算Hanio(N一1，A。C。B)。
在回归阶段，当获得最简单情况的解后，逐级返回。依次获得
稍复杂问题的解。在这里的“汉诺塔”问题中，有它的特别的地方，
回归的过程当中．还要涉及到递推。
另外．在编写递归方法时要注意是：每次调用递归方法，方法
中的参数只是局限于当前调用层的，当递推进入“简单问题”层
时，原来层次上的参数便被隐藏起来。在一系列“简单问题”层，它
们各有自己的参数。 ．
最后．通过经典“汉诺塔”问题移动过程的分析、解决以及最
后JAVA编程实现，使我们能够掌握解决此类问题的方法，也使
我们对递归算法能有个更加深刻的理解。

评论

1 楼 bqlin1987 2011-10-26  

谢谢你，我昨天想很一整晚，我就是突破不了如何用程序实现。
你的解答很详细，真的很好！谢谢，请问你是女程序员吗？