汉诺塔试验报告-源程序.docx

汉诺塔文档一、软件概述：汉诺塔（Hanoi)是一个古老的数学问题。相传在古印度的布拉玛婆罗门圣庙的僧侣在进行 一种被称为汉诺塔的游戏，其装置是一块铜板，上而有三根奸（编号1、2、3), 1杆上自下 而上、由大到小按顺序串上64个金盘（如图，由于空间有限，只画了 10个盘）。游戏的目 标是把1杆上的金盘全部移到3杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并 且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出N个盘从1杆移 到3杆的移动过程。图1汉诺塔问题2.1、算法：2.1.1:(递归算法) 这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先 得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动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.2:(循环算法）在程序中开一个2维的数组iResultArray,由数学公式，移动N个盘所需要的步骤是2AN-1 步，通过计算算得这个步数，计入变量iStep,则iResultArray有2AN-1行，每行2个元素， 其中第一个元素是源盘所在的轴号（用1，2,3表示)，第二个元素是目的盘所在的轴号。 为叙述方便，现假设盘子的数目有4个。则可分解为：第一阶段：将1号盘从1轴移至2 轴；第二阶段：将2号盘从1轴移至3轴，将1号盘从2轴移至3轴；第三阶段：将3号盘从1轴移至2轴，将1, 2号盘从3轴移至2轴；第四阶段：将4号盘从1轴移至3轴，将 1, 2, 3号盘从2轴移至3轴。对于第J个阶段，都是将1轴中的可以移动的盘子A移到没有盘子的轴上，然后将剩下的 那组盘子移动到A上，而这一步又恰是第J-1个阶段的重演，但源轴号和目的轴号都有变。 假设第1J-1个盘子己经被从原来的第il轴经过12轴最终移到了 i3轴，则第J阶段为：1, 将第J个盘子从第1轴移动到第i2轴，再将i3看作上一步的il, il看作上一步的i2, 12看 作上一步的i3,经过这样一个变化后重演第J-1阶段以前的工作。这个重演可以看作是对 iResultArray数组中小于等于2A(iStep-l)的替换。从而实现重复算法。2.2界面实现在控制界而类MyPanel中设置3*10的iDiskStack HH二维数组用以表示盘片的位置,假设 iDiskStackll=10,则第1个轴上最底下位置上放着第10号盘片。（出于若盘片过多，运 算量太大，则程序将无法终止，故只设最大为10个盘片）假设iDiskStack210=5,则第 2个轴上最高的位置上放着第5号盘片，以此类推。在每输入一个新的盘片数N时 (1N=10),程序会初始化1N号盘片的位置。并通过函数MoveStep ()来控制每步的情 况。比如程序在运行期间，发出一个一 MoveStep(l,3)的情求，则程序会搜索iDiskStackm 里面下标最大的非0元素（即1号轴上最顶上的盘子）并将其移动到iDiskStack3里面下 标最小的0元素（即1号轴上最顶上的盘子的紧挨着的上面一个位置），并调用 paintlmmediately强制重绘屏幕。三、使用方法：3.1系统需求硬件：INTEL Pentium II PC或以上机型。软件：Microsoft Windows 98/ME/2000/XP/2003 或 LINUX 等 Java 2 sdk 1.4.1 版或以上3.2安装方法1, 首先下载安装Java2sdkl.4.1 (如果已经正确安装该版本或以上版本的JSDK,则可跳到 步骤3)2，打开Windows的系统变_fl属性页，在path中添加 “C:j2sdkl.4.1bm;C:j2sdkl.4.1jrebiii”二项，在CLASSPATH添加 “;C:j2sdklAllib;C:j2sdkl.4.1jrelib”(其中（：勹28(&1.4.1是允&2 8业1.4.1在您硬盘上的安装目录）3，点击开始一运行一cmd (win98下是command)4，通过cd命令进入本程序所在的文件夹，这时如果敲入dir可以看到Hanoia.java文件 5，敲入“javaHanoia”，回车（注意大小写）如果出现如下图形界而，则恭喜您！您己经正确安装！图2許次进入程序界面3.3运行方法1, 正确安装后，您可以看到图22, 在程序右上角的数字提示框中，输入一个110之间的数（比如4),并点击“START! 按钮图3准备就绪3, 调节速率滑杆，您可以控制每步之间的延迟时间。滑杆越靠右，步骤就演示得越清晰。4, 点击“SOLVE!”按钮，此时您可以看到程序在一步步地执行图4正在顺利解决中图5所有的盘子都已经移完了，OK!5, 在所有的盘子移完后，您可以继续输入一个新的盘子数N,并重复上述步骤观看新的演示。6, 按“EXIT.”钮退出 3.4常见问题FAQ1，在命示行提示符下输入“java Hanoia”，为什么显示“Bad Command or file”或“java is not recognized as an internal or external command，operable program or batch file. ” ？答：请安装java的SDK，有关安装SDK的具体方法请参阅2,在命示行提示符下输入“java Hanoia”，为什么显示如下出错信息：“Exception in thread main java.lang.NoClassDefFoundError: hanoia (wrong name: Hanoia)at java.lang.ClassLoader.defineClassO(Native Method)at java.lang.ClassLoader.defineClass(ClassLoader.java:502)at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:123)at .URLClassLoader.defineClass(URLClassLoader.java:250)at .URLClassLoader.access$ 100(URLClassLoader.java:54)at .URLClassLoaderS 1 .run(URLClassLoader.java: 193)at java.security. AccessController.doPrivileged(Native Method)at .URLClassLoader.findClass(URLClassLoader.java: 186)at java.lang.ClassLoader.loadClass(ClassLoader.java:299)at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:265)atjava.lang.ClassLoader.loadClass(ClassLoader.java:255)at java.lang.ClassLoader.loadClassIntemal(ClassLoader.java:315)答：请检査您的大小写是否正确，请检査当前目录下是否有Hanoiaxlass文件。另种可能是 您下载的程序不完整或已经被破坏。3,如果我遇到其它错误？最常见的错误是您的JAVA的CLASSPATH没有配置或配置有问题。在CLASSPATH添加 “;C:j2sdklAlMib;C:j2sdkl.4.1jrelib”(无引号。其中C:j2sdkL4.1是Java 2 sdk 1.4.1在您硬盘上的安装目录) 注意最左边别忘了那个句点！ ！ ！附：软件源代码:代码1主程序：Hanoia.java/*Hanoia.javaSolving the Hanoi problem Author :李想 Class:软 22 Number: 023156*/ / Java core packages import java.awt.*; import j ava. awt. event. *;/ Java extension packages import javax.swing.*; import javax.swing.event. *;public class Hanoia extends JFramepublic static final int iMaxDisk=10;public static int n;public static int sleepTime;private JPanel panelRight;private MyPanel mypanelLeft;private JButton buttonStart,buttonSolution,buttonExit;private JTextField tflnputn;private JTextArea taMsg;private JSlider jsTime;public Hanoia() super(LiXiangs Hanoia Program);mypanelLeft=new MyPanelQ;panelRight=new JPanel(); panelRight.setLayout(new FlowLayoutQ);tflnputn=new JTextField(9); tfInputn.setPreferredSize(new Dimension(100, 24); panelRight.add(tflnputn);buttonStart=new JButton(,f START!M); buttonStart.setPreferredSize(new Dimension(100,24); buttonStart.addActionListener( new ActionListener()public void actionPerformed (ActionEvent event)tryn = Integer.parselnt( tfInputn.getText(); if(0n&n0)taMsg.setText(Thinking”)；mypanelLeft.solve();taMsg.setForeground(Color.blue);taMsg.setText(Finished!);panelRight.add(buttonSolution);buttonExit=new JButton(MEXIT.M); buttonExit.setPreferredSize(new Dimension(100, 24); buttonExit.addActionListener( new ActionListenerQpublic void actionPerformed (ActionEvent event)System. exit(O);panelRight.add(buttonExit);jsTime=new JSlider(SwingConstants.HORIZONTAL，0，l 000,0); jsTime.setPreferredSize(new Dimension(100, 30)； jsTime.setMajorTickSpacing( 100); jsTime.setPaintTicks(true); jsTime.setSnapToTicks(true); jsTime.addChangeListener( new ChangeListener()public void stateChanged(ChangeEvent event)sleepTime=jsTime.getValue();Solution.setSleepTime(sleepTime);panelRight.add(jsTime);taMsg=new JTextArea(9,l); taMsg.setPreferredSize(new Dimension(100, 24); taMsg.setEditable(false); taMsg.setForeground( Color.blue);taMsg.setText(MPlease enter a nNumber between 1 nand l.M); panelRight.add(taMsg);Container container = getContentPane(); mypanelLefl.setPreferredSize(new Dimension(360, 200); container.add(mypanelLeft,Border Layout.WEST); panelRight.setPreferredSize(new Dimension(100, 200); container.add(panelRight,BrderLayout.EAST);setSize( 470, 240); show();public static void main(String args) Hanoia application = new Hanoia();application.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);代码2界而程序MyPanel.java/*/import java.awt.*; import javax.swing. *;public class MyPanel extends JPanel public static int iDiskStack=new int4ll; public static Solution solution=new SolutionQ; public static Image imageDisk; public static Image imageRod;public MyPanel() super(); intij;imageDisk=new Image 11; for (i= 1 ;i= 10；i+)imageDiski=Toolkit.getDefaultToolkit().createImage(Image.class.getResource(7resource/image/disk+i+.gif)；imageRod=new Image 11; for (i= 1 ;i=3 ;i-H-)imageRodi=Toolkit.getDefaultTcx)lkit().createImage(Image.class.getResource(n/resource/image/rod.gif);public void paintComponent (Graphics g)super.paintComponent (g); int i，j,k; for (i= 1 ;i=3g.drawImage(imageRodi,i* 120-60,20,this); for (i= 1 ;i=3 ；i-H-)for(j=l;j0)g.drawImage(imageDiskk?i* 120-110,180-j * 15,this);public void solve()start;int i Step,iCount,iiCount,iiMid,iiS witch;int iSiliq=new int Hanoia.n+1; iSiliq0=0;for (iCount=l ;iCount=Hanoia.n;iCount+)iSiliqiCount=iSiliqiCount-1 *2+1;iStep=iSiliqHanoia.n;int iResultArray=new int iStep2; int i2or3;if (Hanoia.n%2=0)i2or3=2;elsei2or3=3;for (iCount=l ;iCount=Hanoia.n;iCount+)iiMid=iSiliqiCount-1 ; iResultArrayfiiMid 0=1; iResultArrayiiMid 1 =i2or3;for (iiCount=l ;iiCount=iiMid;iiCount-H-)iiSwitch=iResultArray iiMid-iiCount 0; if (iiSwitch=l)iiSwitch=i2or3;else if (iiSwitch=i2or3)iiSwitch=l;iResult Array iiMid+iiCount 1 =iiSwitch;iiSwitch=iResult Array iiMid-iiCount 1 ;