论文部分内容阅读
摘要：对汉诺塔游戏问题进行了研究，发现了对汉诺塔游戏用递归算法实现符合问题逻辑结构。设计了基于JSSE的递归算法实现了手动移盘和自动移盘的游戏功能。
关键词：汉诺塔；盘子问题；游戏设计
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)08-10ppp-0c
1 引言
相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆（编号A、B、C），A杆上自下而上、由大到小按顺序串上64个金盘。游戏的目标是把 A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。僧侣们说游戏结束的时候就是世界末日。现要求利用递归调用技术把N个盘从A杆移到C杆的移动过程演示出来。
2 问题分析
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
分析问题，找出移动盘子的正确算法。
这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：
（1）以C盘为临时杆，从A杆将1至N-1号盘移至B杆。
（2）将A杆中剩下的第N号盘移至C杆。
（3）以A杆为临时杆，从B杆将1至N-1号盘移至C杆。
我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同， 唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。 这就是需要找的递归调用模型。
3 递归算法设计
根据以上分析，在三个柱子中选择一个作为临时杆，可得到基本递归算法如下：
public class TowersOfHanoi//实现递归算法的类
{
private int totalDisks;
public TowersOfHanoi(int disks)
{
totalDisks=disks;
}
public void solve()
{
moveTower (totalDisks,1,3,2);
}
private void moveTower(int numDisks,int start,int end,int temp)
{
if(numDisks==1)
moveOneDisk(start,end);
else
{
moveTower(numDisks-1,start,temp,end);
moveOneDisk(start,end);
moveTower(numDisks-1,temp,end,start);
}
}
private void moveOneDisk(int start,int end)
{
System.out.println("Move one disk from" start "to" end);
}
}
4 游戏界面设计
4.1 布局设计
在Java的GUI界面设计中，布局控制是通过为容器设置布局编辑器来实现的。java.awt包中共定义了五种布局编辑类，每个布局编辑类对应一种布局编辑策略，分别是FlowLayout、BorderLayout、CardLayout、GridLayout和GridBagLayout。当一个容器选定一种布局编辑策略时，它应该创建该策略对应的布局编辑类的对象，并将此对象设置为自己的布局编辑器。没有设置布局编辑器的容器，其中的对象会互相覆盖，影响使用，所以必须为每个容器设置一个合适的布局编辑器。
本游戏界面采用BorderLayout布局编辑器实现布局控制，它把容器内的空间简单地划分为东、西、南、北、中五个区域，每加入一个组件都应该指明把这个组件加在哪个区域中。
BorderLayout只能指定五个区域位置，如果容器中需要加入超过五个组件，就必须使用容器的嵌套或改用其他的布局策略。
4.2 GUI组件设计
4.2.1 容器设计
容器组件的主要作用是包容其他组件并按一定的方式组织排列它们，同一个容器中的所有部件通常总是同时被显示和同时被隐藏的。从AWT组件体系结构中可以看出，所有的容器组件都是Container类的子类，而Container类又是Component类的子类。作为Container子类的容器可以分为三组：Panel和Applet一组的容器都是无边框的；ScrollPane一组是可以自动处理滚动操作的容器；Windows、Frame、Dialog和FileDialog是一组大都含有边框，可以移动、放大、缩小、关闭，功能较强的容器。
4.2.2 盘子组件设计
游戏界面中的盘子类继承Button按钮，按钮一般都对应一种特定的功能或操作，当用户鼠标点击按钮时，系统就执行这个预先定义好的操作。本游戏中有手动移盘的操作，故将盘子类设计为按钮Button类的子类，以方便手工移动。另外为每个盘子设置唯一的编号以区别大小不同的盘子。最后为盘子类设置属性上方有盘，以判断每个盘子对象上面是否还有其他盘子。如果该属性值为真，表示不能移动该盘子。
class Disk extends Button {
private static final long serialVersionUID = -6174681128406353175L;
int number;
boolean 上方有盘 = false;
public Disk(int number, HannoiTower con) {
this.number = number;
setBackground(Color.blue);
addMouseMotionListener(con);
addMouseListener(con);
}
public boolean get上方有盘() {
return 上方有盘;
}
public void set上方有盘(boolean b) {
上方有盘 = b;
}
public int getNumber() {
return number;
}
}
4.2.3 塔节点设计
塔节点的功能是实现盘子在移动过程中的定位。故应为该类的对象设置横纵坐标属性。塔节点表示盘子放置的位置，还应该设置一个布尔属性表示该节点现在有没有盘子，只有当没有盘子时才能放置。最后还要设置返回该属性值的方法等。
class TowerPoint {
int x, y;
boolean 有盘子;
Disk 盘子 = null;
HannoiTower con = null;
public TowerPoint(int x, int y, boolean boo) {
this.x = x;
this.y = y;
有盘子 = boo;
}
public boolean 是否有盘子() {
return 有盘子;
}
public void set有盘子(boolean boo) {
有盘子 = boo;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public void 放置盘子(Disk 盘子, HannoiTower con) {
this.con = con;
con.setLayout(null);
this.盘子 = 盘子;
con.add(盘子);
int w = 盘子.getBounds().width;
int h = 盘子.getBounds().height;
盘子.setBounds(x - w / 2, y - h / 2, w, h);
有盘子 = true;
con.validate();
}
public Disk 获取盘子() {
return 盘子;
}
}
4.3 事件处理机制
图形用户界面之所以能为广大用户所喜爱并最终成为事实上的标准，很重要的一点就在与它可以用更灵活、简便的方式来接收用户命令。用户在图形用户界面中输入命令是通过移动鼠标对特定图形界面元素单击、双击鼠标或击键来实现的，为了能够接受用户命令，图形用户界面首先应该能够识别这些操作并做出相应的响应。通常每一个键盘或鼠标操作会引发一个系统预先定义好的事件，用户程序只须编制代码定义每个特定事件发生时程序应作出何种响应即可。这些代码会在它们对应的事件发生时由系统自动调用，这就是图形用户界面中事件和事件响应的基本原理。如下代码是鼠标拖动事件的处理：
public void mouseDragged(MouseEvent e) {
Disk disk = null;
if (e.getSource() instanceof Disk) {
disk = (Disk) e.getSource();
move = true;
e = SwingUtilities.convertMouseEvent(disk, e, this);
}
if (e.getSource() == this) {
if (move
关键词：汉诺塔；盘子问题；游戏设计
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)08-10ppp-0c
1 引言
相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆（编号A、B、C），A杆上自下而上、由大到小按顺序串上64个金盘。游戏的目标是把 A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。僧侣们说游戏结束的时候就是世界末日。现要求利用递归调用技术把N个盘从A杆移到C杆的移动过程演示出来。
2 问题分析
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18，446，744，073，709，551，615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
分析问题，找出移动盘子的正确算法。
这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：
（1）以C盘为临时杆，从A杆将1至N-1号盘移至B杆。
（2）将A杆中剩下的第N号盘移至C杆。
（3）以A杆为临时杆，从B杆将1至N-1号盘移至C杆。
我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同， 唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。 这就是需要找的递归调用模型。
3 递归算法设计
根据以上分析，在三个柱子中选择一个作为临时杆，可得到基本递归算法如下：
public class TowersOfHanoi//实现递归算法的类
{
private int totalDisks;
public TowersOfHanoi(int disks)
{
totalDisks=disks;
}
public void solve()
{
moveTower (totalDisks,1,3,2);
}
private void moveTower(int numDisks,int start,int end,int temp)
{
if(numDisks==1)
moveOneDisk(start,end);
else
{
moveTower(numDisks-1,start,temp,end);
moveOneDisk(start,end);
moveTower(numDisks-1,temp,end,start);
}
}
private void moveOneDisk(int start,int end)
{
System.out.println("Move one disk from" start "to" end);
}
}
4 游戏界面设计
4.1 布局设计
在Java的GUI界面设计中，布局控制是通过为容器设置布局编辑器来实现的。java.awt包中共定义了五种布局编辑类，每个布局编辑类对应一种布局编辑策略，分别是FlowLayout、BorderLayout、CardLayout、GridLayout和GridBagLayout。当一个容器选定一种布局编辑策略时，它应该创建该策略对应的布局编辑类的对象，并将此对象设置为自己的布局编辑器。没有设置布局编辑器的容器，其中的对象会互相覆盖，影响使用，所以必须为每个容器设置一个合适的布局编辑器。
本游戏界面采用BorderLayout布局编辑器实现布局控制，它把容器内的空间简单地划分为东、西、南、北、中五个区域，每加入一个组件都应该指明把这个组件加在哪个区域中。
BorderLayout只能指定五个区域位置，如果容器中需要加入超过五个组件，就必须使用容器的嵌套或改用其他的布局策略。
4.2 GUI组件设计
4.2.1 容器设计
容器组件的主要作用是包容其他组件并按一定的方式组织排列它们，同一个容器中的所有部件通常总是同时被显示和同时被隐藏的。从AWT组件体系结构中可以看出，所有的容器组件都是Container类的子类，而Container类又是Component类的子类。作为Container子类的容器可以分为三组：Panel和Applet一组的容器都是无边框的；ScrollPane一组是可以自动处理滚动操作的容器；Windows、Frame、Dialog和FileDialog是一组大都含有边框，可以移动、放大、缩小、关闭，功能较强的容器。
4.2.2 盘子组件设计
游戏界面中的盘子类继承Button按钮，按钮一般都对应一种特定的功能或操作，当用户鼠标点击按钮时，系统就执行这个预先定义好的操作。本游戏中有手动移盘的操作，故将盘子类设计为按钮Button类的子类，以方便手工移动。另外为每个盘子设置唯一的编号以区别大小不同的盘子。最后为盘子类设置属性上方有盘，以判断每个盘子对象上面是否还有其他盘子。如果该属性值为真，表示不能移动该盘子。
class Disk extends Button {
private static final long serialVersionUID = -6174681128406353175L;
int number;
boolean 上方有盘 = false;
public Disk(int number, HannoiTower con) {
this.number = number;
setBackground(Color.blue);
addMouseMotionListener(con);
addMouseListener(con);
}
public boolean get上方有盘() {
return 上方有盘;
}
public void set上方有盘(boolean b) {
上方有盘 = b;
}
public int getNumber() {
return number;
}
}
4.2.3 塔节点设计
塔节点的功能是实现盘子在移动过程中的定位。故应为该类的对象设置横纵坐标属性。塔节点表示盘子放置的位置，还应该设置一个布尔属性表示该节点现在有没有盘子，只有当没有盘子时才能放置。最后还要设置返回该属性值的方法等。
class TowerPoint {
int x, y;
boolean 有盘子;
Disk 盘子 = null;
HannoiTower con = null;
public TowerPoint(int x, int y, boolean boo) {
this.x = x;
this.y = y;
有盘子 = boo;
}
public boolean 是否有盘子() {
return 有盘子;
}
public void set有盘子(boolean boo) {
有盘子 = boo;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public void 放置盘子(Disk 盘子, HannoiTower con) {
this.con = con;
con.setLayout(null);
this.盘子 = 盘子;
con.add(盘子);
int w = 盘子.getBounds().width;
int h = 盘子.getBounds().height;
盘子.setBounds(x - w / 2, y - h / 2, w, h);
有盘子 = true;
con.validate();
}
public Disk 获取盘子() {
return 盘子;
}
}
4.3 事件处理机制
图形用户界面之所以能为广大用户所喜爱并最终成为事实上的标准，很重要的一点就在与它可以用更灵活、简便的方式来接收用户命令。用户在图形用户界面中输入命令是通过移动鼠标对特定图形界面元素单击、双击鼠标或击键来实现的，为了能够接受用户命令，图形用户界面首先应该能够识别这些操作并做出相应的响应。通常每一个键盘或鼠标操作会引发一个系统预先定义好的事件，用户程序只须编制代码定义每个特定事件发生时程序应作出何种响应即可。这些代码会在它们对应的事件发生时由系统自动调用，这就是图形用户界面中事件和事件响应的基本原理。如下代码是鼠标拖动事件的处理：
public void mouseDragged(MouseEvent e) {
Disk disk = null;
if (e.getSource() instanceof Disk) {
disk = (Disk) e.getSource();
move = true;
e = SwingUtilities.convertMouseEvent(disk, e, this);
}
if (e.getSource() == this) {
if (move