汉诺塔模拟程序-课程设计报告.doc
- 文档编号:4861362
- 上传时间:2023-05-07
- 格式:DOC
- 页数:22
- 大小:314KB
汉诺塔模拟程序-课程设计报告.doc
《汉诺塔模拟程序-课程设计报告.doc》由会员分享,可在线阅读,更多相关《汉诺塔模拟程序-课程设计报告.doc(22页珍藏版)》请在冰点文库上搜索。
合肥学院
计算机科学与技术系
课程设计任务书
2011~2012学年第一学期
课程
JAVA语言课程设计
课程设计名称
汉诺塔模拟程序
专业班级
08网络工程
(1)班
学号
0804031034
姓名
Xx
指导教师
金莹郭昌建
2011年9月目录
目录 2
摘要:
3
关键词:
3
1、需求分析 3
1.1课程设计目的 3
1.2课程设计名称及内容 3
1.3任务和要求 3
1.4设计方案提示 4
1.5相关背景 4
1.5.1来源 4
1.5.2传说 4
2、设计部分 5
2.1设计思想 5
2.1.1汉诺塔的演示 5
2.1.2算法分析 5
2.1.3程序流程图 6
2.1.4算法分析图解 7
2.2功能内容设计 8
2.2.1程序实现总体功能 8
2.2.2具体功能设计 9
2.3详细设计 10
3、调试及测试 14
3.1调试过程中遇到的主要问题集解决方法 14
3.2对设计和编码的回顾讨论和分析 14
4、经验和体会 15
5、附录:
16
主要源程序 16
摘要:
本文对经典的“汉诺塔”问题进行了详细的分析,给出了实现的算法,并用JAVA实现。
通过该问题的JAVA实现,可使清晰地观测到解决问题的全过程。
关键词:
汉诺塔;算法;递归;JAVA
1、需求分析
1.1课程设计目的
通过课程设计,学生在下述各方面的能力应该得到锻炼:
(1)进一步巩固、加深学生所学专业课程《JAVA语言教程》的基本理论知识,理论联系实际,进一步培养学生综合分析问题,解决问题的能力。
(2)全面考核学生所掌握的基本理论知识及其实际业务能力,从而达到提高学生素质的最终目的。
(3)利用所学知识,开发小型应用系统,掌握运用JAVA语言编写调试应用系统程序,训练独立开发应用系统,进行数据处理的综合能力。
(4)对于给定的设计题目,如何进行分析,理清思路,并给出相应的数学模型。
(5)熟练掌握JAVA语言的GUI设计、线程技术,灵活运用各种类库。
1.2课程设计名称及内容
课程设计名称:
汉诺塔模拟程序
课程设计内容:
设计一个模拟程序,图形化地展现汉诺塔的求解过程
1.3任务和要求
1.学习数据结构课程中关于汉诺塔的知识和算法。
2.设计图形界面,画出3个柱子和若干个大小不一的圆盘,圆盘数量可人工设定。
3.当点击“开始”按钮后,系统自动展现圆盘的移动过程,一秒移动一次。
1.4设计方案提示
利用线程控制每次移动的时间间隔
1.5相关背景
1.5.1来源
汉诺塔是源自印度神话里的玩具。
大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
1.5.2传说
在印度,有这么一个古老的传说:
在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。
不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:
一次只移动一片,不管在哪根针上,小片必须在大片上面。
僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
不管这个传说的可信度有多大,如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下大的顺序。
这需要多少次移动呢?
这里需要递归的方法。
假设有n片,移动次数是f(n).显然f
(1)=1,f
(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。
此后不难证明f(n)=2^n-1。
n=64时, f(64)=2^64-1=18446744073709551615 假如每秒钟一次,共需多长时间呢?
一个平年365天有31536000秒,闰年366天有31622400
秒,平均每年31556952秒,计算一下,
18446744073709551615/31556952=584554049253.855年,这表明移完这些金片需要5845亿年以上,而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。
真的过了5845亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。
2、设计部分
2.1设计思想
本程序的主要思想是图形与多线程处理,熟悉图形、图像的使用方法,理解计算机动画的原理和java的多线程处理机制,以及Java语言的GUI设计。
2.1.1汉诺塔的演示
1、柱子和盘子可以用图形界面里的直线和矩形模拟。
2、矩形(即盘子)的大小可以通过循环控制,这样可以让盘子看上去有层次感。
3、盘子移动后构造一个重绘方法来擦去旧的盘子
4、盘子的移动时间通过线程来控制
2.1.2算法分析
如果n=1,则将圆盘从A直接移动到C。
如果n=2,则:
(1)将A上的n-1(等于1)个圆盘移到B上;
(2)再将A上的一个圆盘移到C上;
(3)最后将B上的n-1(等于1)个圆盘移到C上。
如果n=3,则:
A)将A上的n-1(等于2,令其为n`)个圆盘移到B(借助于C),步骤如下:
(1)将A上的n`-1(等于1)个圆盘移到C上。
(2)将A上的一个圆盘移到B。
(3)将C上的n`-1(等于1)个圆盘移到B。
B)将A上的一个圆盘移到C。
C)将B上的n-1(等于2,令其为n`)个圆盘移到C(借助A),步骤如下:
(1)将B上的n`-1(等于1)个圆盘移到A。
(2)将B上的一个盘子移到C。
(3)将A上的n`-1(等于1)个圆盘移到C。
到此,完成了三个圆盘的移动过程。
从上面分析可以看出,当n大于等于2时,移动的过程可分解为三个步骤:
第一步把A上的n-1个圆盘移到B上;第二步把A上的一个圆盘移到C上;第三步把B上的n-1个圆盘移到C上;其中第一步和第三步是类同的。
当n=3时,第一步和第三步又分解为类同的三步,即把n`-1个圆盘从一个针移到另一个针上,这里的n`=n-1。
2.1.3程序流程图
图1-12.1.4算法分析图解
2.2功能内容设计
2.2.1程序实现总体功能
(1)设计Hannoi塔中有三个座,名字分别是1、2和3。
初始状态是1座上有n个大小不等的盘子,这些盘子从座底到座顶按着大小顺序依次摆放在1座上。
(2)程序要求在移动盘子过程中,不允许把大盘放置在小盘的上面,用户最终要完成的是把1座上的全部盘子移动到3座上;
(3)可以通过Hannoi塔界面提供的菜单来任意输入盘子数目(程序初始化时可选择1-8个);
(4)可以通过单击Hannoi塔界面上提供的开始按钮按钮,让程序自动完成把1座上的盘子全部移动到3座上;
(5)在移动盘子的过程中,可以随时单击Hannoi塔界面上提供的按钮,结束当时程序;
(6)有计时功能,每一步一秒钟,界面右边有步骤移动显示。
(7)程序可以设置最大和最小盘子的大小;
(8)更改程序可以设置盘子的颜色;
(9)每移动盘子的时候相邻盘子的颜色不同;
2.2.2具体功能设计
1、设计汉诺塔层数选择界面
将布局管理器设置为空。
然后添加开始和退出按钮以及汉诺塔层数选择下拉选择列表。
层数选择界面如下图2-1所示:
图2-2层数选择界面
2、汉诺塔移动演示界面
也是通过布局管理器根据所选择的盘子层数画出相应的盘子,setlocation()来根据需求来定位汉诺塔
演示界面如下图:
图2-3汉诺塔演示界面
图2-4运行中演示界面
2.3详细设计
1、层数选择界面及布局的部分代码
contentPane=(JPanel)getContentPane();
contentPane.setLayout(null);
this.setResizable(false);
setSize(newDimension(300,150));
setTitle("Hanoi");
//选择框
jComboBox1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jComboBox1.setBorder(BorderFactory.createEtchedBorder());
jComboBox1.setBounds(newRectangle(157,38,70,26));
jComboBox1.addItem("1层");
jComboBox1.addItem("2层");
jComboBox1.addItem("3层");
jComboBox1.addItem("4层");
jComboBox1.addItem("5层");
jComboBox1.addItem("6层");
jComboBox1.addItem("7层");
jComboBox1.addItem("8层");
//开始按钮
jButton1.setBounds(newRectangle(66,81,71,27));
jButton1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jButton1.setText("开始");
//开始myDrawingFrame
jButton1.addActionListener(newDefaultFrame_jButton1_actionAdapter(this));
//退出按钮
jButton2.setBounds(newRectangle(156,81,71,27));
jButton2.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jButton2.setText("退出");
//退出事件
jButton2.addActionListener(newDefaultFrame_jButton2_actionAdapter(this));
//Hanoi层数:
文字显示
jLabel1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jLabel1.setToolTipText("");
jLabel1.setText("Hanoi层数:
");
jLabel1.setBounds(newRectangle(68,39,79,25));
//将上述按钮添加到主界面
contentPane.add(jButton2);
contentPane.add(jButton1);
contentPane.add(jComboBox1);
contentPane.add(jLabel1);
2.汉诺塔程序演示界面部分代码:
Init();
setSize(newDimension(400,300));
this.setTitle("Hanoi");
getContentPane().setLayout(null);
//开始按钮
jButton1.setBounds(newRectangle(169,220,60,27));
jButton1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jButton1.setText("开始");
//开始事件
jButton1.addActionListener(newDrawingFrame_jButton1_actionAdapter(this));
this.getContentPane().add(myDrawPanel,null);
this.getContentPane().add(jButton1);
this.setResizable(false);
myDrawPanel.setBounds(newRectangle(0,0,400,200));
myDrawPanel.setLayout(null);
//主界面定位
DimensionscreenSize=Toolkit.getDefaultToolkit().getScreenSize();
DimensionframeSize=this.getSize();
if(frameSize.height>screenSize.height){
frameSize.height=screenSize.height;
}
if(frameSize.width>screenSize.width){
frameSize.width=screenSize.width;
}
this.setLocation((screenSize.width-frameSize.width)/2,
(screenSize.height-frameSize.height)/2);
//初始化窗口的屏幕居中
this.setVisible(true);//通过传入的布尔值显示
3.颜色渐变程序段:
for(inti=1;i<=refHanoi_pan.length;i++){
if(color){//refHanoi_pan[i].z
g.setColor(Color.green);
color=false;
}else{
g.setColor(Color.blue);
color=true;
}
if(refHanoi_pan[0].z==i)
g.setColor(Color.red);g.fillRect(refHanoi_pan[i-1].x,refHanoi_pan[i-1].y,refHanoi_pan[i-1].width,refHanoi_pan[i-1].height);
}3、调试及测试
3.1调试过程中遇到的主要问题集解决方法
在界面设置上,为了轮廓清晰,所以我们将开始界面与运行界面分开了。
并且,为了能够很清楚的看到盘子移动时的效果,而且为了美观,每次盘子移动的时候都会在红、绿、蓝三色中任选一色。
并且相邻两个盘颜色不同。
在程序运行的过程中我在画矩形的时候没有考虑到被移走后,如何把原来的矩形擦掉,后来考虑到构造一个重绘和容器布局的背景色相同的盘子的方法。
这样就能覆盖掉原来的盘子。
在线程的控制上一开始也出了点小问题,最后通过不断地调试和改善,最后实现了预期要实现的功能。
3.2对设计和编码的回顾讨论和分析
本程序的主要思想是图形与多线程处理,熟悉图形、图像的使用方法,理解计算机动画的原理和Java的多线程处理机制,能够编写在Application中使用动画。
4、经验和体会
万事开头难,一个课程设计下来,真的有所体会了,一开始我对JAVA课程设计非常害怕,因为感觉自己平时上课时只掌握了java的基础知识,也没有多么深入研究,而且,平时的上级实验也都是比较简单的。
当我拿到这个题目后,我迷茫了好长时间,因为线程方面学得不理想。
虽然对汉诺塔的背景传说比较了解,对其如何运行也比较清楚,其算法我们在大二的数据结构中也有介绍,但是,都不是很熟练掌握,所以,在拿到题目的第一件事就是了解其算法。
通过上网查了一些资料,还有到类库中查询函数。
渐渐有了眉目,自己也有了信心,正是抱着这份自信我坚持了整整两周时间的不断调试。
现在程序已经完成,虽然感觉里面的功能还不是很完备,但是总体还是能体现JAVA多线程并符合题目要求。
在这次课程设计中,我学到了很多东西,多线程在java中的重要性是显而易见的,也是很有实用价值的。
Java的一大特点就是内置多线程的支持。
多线程是指同时存在几个执行体,按几条不同的执行线索共同工作的情况。
2周的Java课程设计已经结束了,从中学到了很多以前没有的知识,增强了动手能力。
以前总是眼高手低,觉得编程只要理解了思路,多看看就可以了。
但是在课程设计过程中发现即使是很小的一段程序也会有很大的问题,有时候仅仅是因为一个括号的问题而导致了程序的调试不通过。
平时多动手,才会熟能生巧。
俗话说的好,书到用时方恨少,只有平时的积累才能熟练的完成课程设计。
感谢课程设计过程中指导老师的热心帮助和严格要求,以及同学们的帮忙,正是由于大家的帮助才使我能够完成本次课程设计。
5、附录:
主要源程序
DefaultFrame.txt
importjava.awt.Dimension;
importjava.awt.Font;
importjava.awt.Rectangle;
importjava.awt.event.ActionEvent;
importjava.awt.event.ActionListener;
importjavax.swing.BorderFactory;
importjavax.swing.JButton;
importjavax.swing.JComboBox;
importjavax.swing.JFrame;
importjavax.swing.JLabel;
importjavax.swing.JPanel;
publicclassDefaultFrameextendsJFrame{
JPanelcontentPane;//整体布局
JComboBoxjComboBox1=newJComboBox();//下拉菜单
JButtonjButton1=newJButton();//开始按钮
JButtonjButton2=newJButton();//退出按钮
JLabeljLabel1=newJLabel();//层数标签
/**
*构造函数初始化
*/
//抛出异常
publicDefaultFrame(){
try{
//设置主界面退出X按钮
setDefaultCloseOperation(EXIT_ON_CLOSE);
//初始化
jbInit();
}catch(Exceptionexception){
exception.printStackTrace();
}
}
/**
*Componentinitialization.
*初始化界面
*@throwsjava.lang.Exception
*/
privatevoidjbInit()throwsException{
//布局
contentPane=(JPanel)getContentPane();
contentPane.setLayout(null);
this.setResizable(false);
setSize(newDimension(300,150));//定义整体布局的框体大小
setTitle("Hanoi");
//选择框
jComboBox1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,15));//字体大小
jComboBox1.setBorder(BorderFactory.createEtchedBorder());//矩形框布局
jComboBox1.setBounds(newRectangle(157,38,70,26));
jComboBox1.addItem("1层");
jComboBox1.addItem("2层");
jComboBox1.addItem("3层");
jComboBox1.addItem("4层");
jComboBox1.addItem("5层");
jComboBox1.addItem("6层");
jComboBox1.addItem("7层");
jComboBox1.addItem("8层");
//开始按钮
jButton1.setBounds(newRectangle(66,81,71,27));
jButton1.setFont(newjava.awt.Font("Dialog",Font.PLAIN,12));
jButton1.setText("开始");
//开始myDrawingFrame
jButton1.addActionListener(newDefaultFrame_jButton1_actionAdapter(this));
//退出按钮
jButton2.setBounds(newRectangle(156,81,71,27));
jButton2.setFont(newjava.awt.Font("Dial
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汉诺塔 模拟 程序 课程设计 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)