汉诺塔(Towers

1、汉诺塔（Towers of Hanoi）问题汉诺塔（Towers of Hanoi）问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔，其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔。从世界创始之日起，婆罗门的牧师们就一直在试图把塔1上的碟子移动到塔2上去，其间借助于塔3的帮助。由于碟子非常重，因此，每次只能移动一个碟子。另外，任何时候都不能把一个碟子放在比它小的碟子上面。按照这个传说，当牧师们完成他们的任务之后，世界末日也就到了。图1-1问题：1、已知有三个塔（1、2、3）和n个从大到小的金碟子，初始状态时n个碟子按从大到小的次序从塔1的底

2、部堆放至顶部。2、要求把碟子都移动到塔2（按从大到小的次序从塔2的底部堆放至顶部）。3、每次移动一个碟子。4、任何时候、任何一个塔上都不能把大碟子放到小碟子的上面。5、可以借助塔3。作业要求：1、在窗口中画出初始时塔和碟子的状态。2、可以以自动或手动两种方式搬移碟子。3、自动搬移可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的移动过程如能实现动画最好。4、定义塔的描述类和碟子的描述类。5、在程序中，碟子的数目及每次移动的时间间隔可以通过对话框设置（也应该有默认值）。6、支持暂停功和继续的功能（在自动搬移过程中可以暂停，并继续）。7、暂停后，可以将当前

3、的状态保存（碟子和塔的组合关系）。8、可以从7中保存的文件中读出某个状态，并继续移动。程序介绍一、程序软件介绍1、软件开发和运行环境开发环境软件语言java，开发工具JBuilder 2005，JDK的版本是1.5；开发环境是Windows XP。运行环境由于采用Java语言，可以运行在任何操作系统上。运行环境Windows XP，配置为Pentium(R) 4 CPU 2.0GHz,256MB内存。2、程序介绍程序包括Disk，Tower，HannoiTowerPanel，ShowHanoiFrame，SetupWindow，ExampleFileFilter等6个类及一个face文件夹。D

4、isk类：定义了描述碟子的类，其实就是继承了JButton。Tower类：定义了描述塔的类，主要是关键点的位置和放置盘子的方法。HannoiTowerPanel类：构造显示汉诺塔的JPanel，及主要方法，包括JPanel的绘制响应的鼠标事件及递归算法，自动演示汉诺塔的搬运过程。ShowHanoiFrame类：调用此软件的主界面类，构造了菜单及工具栏。SetupWindow类：当点击设置时，响应的设置窗口。ExampleFileFilter类：JDK自带的源程序，用于根据要求过滤显示需要（.dat文件）的文件。face文件夹：里面有一些小图片，作为工具栏的显示图标。3、程序运行首先保证机器上已

5、经装有了JDK1.5，编译完毕，通过调用ShowHanoiFrame开启主界面。如果机器上装了JAVA运行环境1.5（JRE1.5）, 只需右键点击附给的TowersOfHanoi.jar文件，选择打开方式，即可运行。二、按照作业的要求，下面就每一条对所编写的程序进行说明。1、在窗口中画出初始时塔和碟子的状态。HannoiTowerPanel类的构造方法实现了碟子的放置，类中paintComponent()方法完成绘制了塔和地面。2、可以以自动或手动两种方式搬移碟子。HannoiTowerPanel类的autoHanoiDemo()方法实现了自动演示汉诺塔的搬运过程；添加了鼠标响应事件，拖动碟

6、子到相应位置即可手动摆放（当然如果拖动不能满足要求，碟子回到原位）。3、自动搬移可以通过定时器或多线程的方法，每一次移动的时间间隔可以自定，以人眼观察比较舒服为宜，每一次的移动过程如能实现动画最好。利用线程，可以设定自动演示搬移碟子的快慢，并且实现了动画效果。4、定义塔的描述类和碟子的描述类。Disk类：定义了描述碟子的类，其实就是继承了JButton。Tower类：定义了描述塔的类，主要是关键点的位置和放置盘子的方法。5、在程序中，碟子的数目及每次移动的时间间隔可以通过对话框设置（也应该有默认值）。碟子数目默认值为4，动画移动的时间间隔默认值是10毫秒。通过点击工具栏的设置图标或者CTRL+

7、C快捷键，调出改变碟子数目和移动速度的对话框。6、支持暂停功能和继续的功能（在自动搬移过程中可以暂停，并继续）。在自动搬移过程中，通过点击工具栏的暂停图标或者CTRL+P快捷键，实现暂停功能；通过点击工具栏的开始图标或者CTRL+R快捷键，实现继续演示功能。7、暂停后，可以将当前的状态保存（碟子和塔的组合关系）。暂停后，通过点击工具栏的保存图标或者CTRL+S快捷键，打开状态保存窗口，存为.dat文件。8、可以从7中保存的文件中读出某个状态，并继续移动。通过点击工具栏的打开图标或者CTRL+O快捷键，打开状态读取窗口，读出以前保存的状态，并可以通过点击工具栏的开始图标或者CTRL+R快捷键，实

8、现继续演示功能。三、递归算法介绍这是个著名难题, 通常采用递归的方法来解决，并且其相关算法都可以容易得到，因此在这里我选择使用递归算法，详细步骤如下：若你有一个以上的盘子(设为n个), 则考虑三个步骤。第一步, 把 n-1 个盘子从塔A搬到塔C。第一步不违反说明的第一条限制(一次只能搬动一个盘子);所有 n-1 个盘子不能作为一个整体一起搬动,而是符合要求地从一个塔移到另一个塔上。注意尽管最终目标是把盘子从A搬到B, 但是你可以用相同的算法把盘子从一个塔移到另一个塔上, 只要把源塔和目的塔的名字改变一下即可。第二步: 将剩下的一只盘 (也就是最大的一只) 直接从A塔搬到那个仍然空着的塔 B。第三步: 用第一步所说的方法, 再次将C塔上的盘搬到B塔。和第一步一样. 这一步实际上是由一序列更小的一次仅搬一个盘的操作组成。这一步是没有问题的, 因为B塔上仅有的一只盘是最大的盘。这个算法达到了预期的目标, 即在B塔上按正确的顺序堆放了所有的盘。这种算法的总移动次数为次，当N10,总移动次数为1023，当N16,总移动次数为65535，当N32,总移动次数为4,294,967,695，显然但N超过32次时，运算量将空前