汉诺塔模拟程序-课程设计报告

合肥学院计算机科学与技术系课程设计任务书20112012学年第一学期课程JAVA语言课程设计课程设计名称汉诺塔模拟程序专业班级08网络工程(1)班学号姓名Xx指导教师金莹 郭昌建 2011年9月目 录目 录2摘要：3关键词：31、需求分析31.1 课程设计目的31.2 课程设计名称及内容31.3 任务和要求31.4 设计方案提示41.5 相关背景41.5.1 来源41.5.2 传说42、设计部分52.1 设计思想52.1.1 汉诺塔的演示52.1.2 算法分析52.1.3 程序流程图62.1.4 算法分析图解72.2 功能内容设计82.2.1 程序实现总体功能82.2.2 具体功能设计92.3 详细设计103、调试及测试143.1 调试过程中遇到的主要问题集解决方法143.2 对设计和编码的回顾讨论和分析144、经验和体会155、附录：16主要源程序16摘要：本文对经典的“ 汉诺塔”问题进行了详细的分析，给出了实现的算法，并用JAVA实现。通过该问题的JAVA实现，可使清晰地观测到解决问题的全过程。关键词：汉诺塔；算法；递归；JAVA1、需求分析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)=2n-1。n=64时， f(64)= 264-1= 假如每秒钟一次，共需多长时间呢？一个平年365天有 秒，闰年366天有秒，平均每年秒，计算一下， /=3.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(new Dimension(300, 150); setTitle(Hanoi); /选择框 jComboBox1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jComboBox1.setBorder(BorderFactory.createEtchedBorder(); jComboBox1.setBounds(new Rectangle(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(new Rectangle(66, 81, 71, 27); jButton1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jButton1.setText(开始); /开始myDrawingFrame jButton1.addActionListener(new DefaultFrame_jButton1_actionAdapter(this); /退出按钮 jButton2.setBounds(new Rectangle(156, 81, 71, 27); jButton2.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jButton2.setText(退出); /退出事件 jButton2.addActionListener(new DefaultFrame_jButton2_actionAdapter(this); /Hanoi 层数：文字显示 jLabel1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jLabel1.setToolTipText(); jLabel1.setText(Hanoi 层数：); jLabel1.setBounds(new Rectangle(68, 39, 79, 25); /将上述按钮添加到主界面 contentPane.add(jButton2); contentPane.add(jButton1); contentPane.add(jComboBox1); contentPane.add(jLabel1);2.汉诺塔程序演示界面部分代码： Init(); setSize(new Dimension(400, 300); this.setTitle(Hanoi); getContentPane().setLayout(null); /开始按钮 jButton1.setBounds(new Rectangle(169, 220, 60, 27); jButton1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jButton1.setText(开始); /开始事件 jButton1.addActionListener(new DrawingFrame_jButton1_actionAdapter(this); this.getContentPane().add(myDrawPanel, null); this.getContentPane().add(jButton1); this.setResizable(false); myDrawPanel.setBounds(new Rectangle(0, 0, 400, 200); myDrawPanel.setLayout(null); /主界面定位 Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize(); Dimension frameSize = 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 (int i=1;i=refHanoi_pan.length;i+) if(color) /refHanoi_pani.z g.setColor(Color.green); color = false; else g.setColor(Color.blue); color = true; if(refHanoi_pan0.z = i) g.setColor(Color.red); g.fillRect(refHanoi_pani-1.x,refHanoi_pani-1.y,refHanoi_pani-1.width,refHanoi_pani-1.height); 3、调试及测试3.1 调试过程中遇到的主要问题集解决方法在界面设置上，为了轮廓清晰，所以我们将开始界面与运行界面分开了。并且，为了能够很清楚的看到盘子移动时的效果，而且为了美观，每次盘子移动的时候都会在红、绿、蓝三色中任选一色。并且相邻两个盘颜色不同。在程序运行的过程中我在画矩形的时候没有考虑到被移走后，如何把原来的矩形擦掉，后来考虑到构造一个重绘和容器布局的背景色相同的盘子的方法。这样就能覆盖掉原来的盘子。在线程的控制上一开始也出了点小问题，最后通过不断地调试和改善，最后实现了预期要实现的功能。3.2 对设计和编码的回顾讨论和分析本程序的主要思想是图形与多线程处理，熟悉图形、图像的使用方法，理解计算机动画的原理和Java的多线程处理机制，能够编写在Application中使用动画。4、经验和体会万事开头难，一个课程设计下来，真的有所体会了，一开始我对JAVA课程设计非常害怕，因为感觉自己平时上课时只掌握了java的基础知识，也没有多么深入研究，而且，平时的上级实验也都是比较简单的。当我拿到这个题目后，我迷茫了好长时间，因为线程方面学得不理想。虽然对汉诺塔的背景传说比较了解，对其如何运行也比较清楚，其算法我们在大二的数据结构中也有介绍，但是，都不是很熟练掌握，所以，在拿到题目的第一件事就是了解其算法。通过上网查了一些资料，还有到类库中查询函数。渐渐有了眉目，自己也有了信心，正是抱着这份自信我坚持了整整两周时间的不断调试。现在程序已经完成，虽然感觉里面的功能还不是很完备，但是总体还是能体现JAVA多线程并符合题目要求。在这次课程设计中，我学到了很多东西，多线程在java中的重要性是显而易见的，也是很有实用价值的。Java的一大特点就是内置多线程的支持。多线程是指同时存在几个执行体，按几条不同的执行线索共同工作的情况。2周的Java课程设计已经结束了，从中学到了很多以前没有的知识，增强了动手能力。以前总是眼高手低，觉得编程只要理解了思路，多看看就可以了。但是在课程设计过程中发现即使是很小的一段程序也会有很大的问题，有时候仅仅是因为一个括号的问题而导致了程序的调试不通过。平时多动手，才会熟能生巧。俗话说的好，书到用时方恨少，只有平时的积累才能熟练的完成课程设计。感谢课程设计过程中指导老师的热心帮助和严格要求，以及同学们的帮忙，正是由于大家的帮助才使我能够完成本次课程设计。5、附录：主要源程序DefaultFrame.txtimport java.awt.Dimension;import java.awt.Font;import java.awt.Rectangle;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.BorderFactory;import javax.swing.JButton;import javax.swing.JComboBox;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;public class DefaultFrame extends JFrame JPanel contentPane;/整体布局 JComboBox jComboBox1 = new JComboBox();/下拉菜单 JButton jButton1 = new JButton();/开始按钮 JButton jButton2 = new JButton();/退出按钮 JLabel jLabel1 = new JLabel();/层数标签 /* * 构造函数初始化 */ /抛出异常 public DefaultFrame() try /设置主界面退出X按钮 setDefaultCloseOperation(EXIT_ON_CLOSE); /初始化 jbInit(); catch (Exception exception) exception.printStackTrace(); /* * Component initialization. * 初始化界面 * throws java.lang.Exception */ private void jbInit() throws Exception /布局 contentPane = (JPanel) getContentPane(); contentPane.setLayout(null); this.setResizable(false); setSize(new Dimension(300, 150);/定义整体布局的框体大小 setTitle(Hanoi); /选择框 jComboBox1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 15);/字体大小 jComboBox1.setBorder(BorderFactory.createEtchedBorder();/矩形框布局 jComboBox1.setBounds(new Rectangle(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(new Rectangle(66, 81, 71, 27); jButton1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jButton1.setText(开始); /开始myDrawingFrame jButton1.addActionListener(new DefaultFrame_jButton1_actionAdapter(this); /退出按钮 jButton2.setBounds(new Rectangle(156, 81, 71, 27); jButton2.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jButton2.setText(退出); /退出事件 jButton2.addActionListener(new DefaultFrame_jButton2_actionAdapter(this); /Hanoi 层数：文字显示 jLabel1.setFont(new java.awt.Font(Dialog, Font.PLAIN, 12); jLabel1.setToolTipText(); jLabel1.setText(Hanoi 层数：); jLabel1.setBounds(new Rectangle(68, 39, 79, 25); /将上述按钮添加到主界面 contentPane.add(jButton2); contentPane.add(jButton1); contentPane.add(jComboBox1); contentPane.add(jLabel1); /button2退出事件 public void jButton2_actionPerformed(ActionEvent e) System.exit(0); /button1 new myDrawingFrame对象 public void jButton1_actionPerformed(ActionEvent e) DrawingFrame myDrawingFrame = new DrawingFrame(this,this.jComboBox1.getSelectedIndex()+1); myDrawingFrame.show(); this.setVisible(false); class DefaultFrame_jButton1_actionAdapter implements ActionListener private DefaultFrame adaptee; DefaultFrame_jButton1_actionAdapter(DefaultFrame adaptee) this.adaptee = adaptee; public void actionPerformed(ActionEvent e) adaptee.jButton1_actionPerformed(e); class DefaultFrame_jButton2_actionAdapter implements ActionListener private DefaultFrame adaptee; DefaultFrame_jButton2_actionAdapter(DefaultFrame adaptee) this.adaptee = adaptee; public void actionPerformed(ActionEvent e) adaptee.jButton2_actionPerformed(e); DrawingFrame.txtpackage hanoi;import java.awt.Color;import java.awt.Dimension;import java.awt.Font;import java.awt.Graphics;import java.awt.Rectangle;import java.awt.TextArea;import java.awt.Toolkit;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JOptionPane;import javax.swing.JPanel;/* * Title: Hanoi Pan * * Description: * * Copyright: Copyright (c) 2005 * * Company: * * author not attributable * version 1.0 */class Hanoi_pan public int x,y,z; public final int width,height; public Hanoi_pan(int arg_x,int arg_y,int z,int arg_width,int arg_height) x=arg_x; y=arg_y; width=arg_width; height=arg_height; class DrawPanel extends JPanel private Hanoi_pan refHanoi_pan; public DrawPanel(Hanoi_pan myHanoi_pan) refHanoi_pan=myHanoi_pan; /* * 生成块状汉诺塔 */ public void paintComponent(Graphics g) boolean color = false; super.paintComponent(g); g.setColor(Color.black); g.drawLine(35,150,125,150); g.drawLine(155,150,245,150); g.drawLine(275,150,365,150); g.drawLine(80,50,80,150); g.drawLine(200,50,200,150); g.drawLine(320,50,320,150); g.drawString(1, 80, 170); g.drawString(2, 200, 170); g.drawString(3, 320, 170); for (int i=1;i + z + n); SetLocation(x,n,z); try repaint(); Thread.sleep(1000); catch (InterruptedException e) if (Thread.currentThread().isAlive() JOptionPane.showMessageDialog(null,唉，太慢了，关掉吧！); myDefaultFrame.setVisible(true); this.dispose(); /System.out.println(move pan + n + from + x + to + z); /* * 定位汉诺塔 * param x * param n * param z */ private void SetLocation(int x,int n,int z) myHanoi_pan0.z = n ; switch (x) case 1: bench0-; break; case 2: bench1-; break; case 3: bench2-; break; switch (z) case 1: myHanoi_pann-1.x=80-myHanoi_pann-1.width/2; myHanoi_pann-1.y=140-bench0*10; bench0+; break; case 2: myHanoi_pann-1.x=200-myHanoi_pann-1.width/2; myHanoi_pann-1.y=140-bench1*10; bench1+; break; case 3: myHanoi_pann-1.x=320-myHanoi_pann-1.width/2; myHanoi_pann-1.y=140-bench2*10; bench2+; break; /* * 根据level初始化汉诺塔 */ private void Init() for (int i=1;i 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);/通过传入的布尔值显示 public void jButton1_actionPerformed(ActionEvent e) if (PaintThread=null) PaintThread=new Thre