漢諾塔文檔一、軟件概述：漢諾塔（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 ;