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

汉诺塔文档一、软件概述: 汉诺塔( Hanoi ) 是一个古老的数学问题。相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏,其装置是一块铜板,上而有三根奸(编号 1、2、 3), 1 杆上自下而上、由大到小按顺序串上 64 个金盘( 如图, 由于空间有限, 只画了 10 个盘)。游戏的目标是把 1 杆上的金盘全部移到 3 杆上, 并仍原有顺序叠好。条件是每次只能移动一个盘,并且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出 N 个盘从 1 杆移到3 杆的移动过程。 、算法: :( 递归算法) 这个移动过程很复杂与烦琐, 但规律性却很强。使用递归调用技术来解决这个移动过程,先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法,着眼点应该是移动 A 杆最底部的大盘, 而不是其顶部的小盘。不考虑 64 个盘而考虑 N 个盘的一般情况。要想将 A杆上的N 个盘移至 C 杆,我们可以这样设想: 盘为临时杆,从 A 杆将 1至N -1 号盘移至 B 杆。 杆中剩下的第 N 号盘移至 C 杆。 杆为临时杆,从 B 杆将 1至N -1 号盘移至 C 杆。 :( 循环算法) 在程序中开一个 2 维的数组 iResultArray [][], 由数学公式, 移动 N 个盘所需要的步骤是 2 AN -1步, 通过计算算得这个步数,计入变量 iStep ,则 iResultArray 有2 AN -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 个阶段的重演,但源轴号和目的轴号都有变。假设第 1? J -1 个盘子己经被从原来的第 il 轴经过 12 轴最终移到了 i3 轴,则第 J 阶段为: 1, 将第 J 个盘子从第1 轴移动到第 i2 轴,再将 i3 看作上一步的 il, il 看作上一步的 i 2, 12看作上一步的 i 3, 经过这样一个变化后重演第 J -1 阶段以前的工作。这个重演可以看作是对 iResultArray 数组中小于等于图1 汉诺塔问题 2 A( iStep -l)的替换。从而实现重复算法。 界面实现在控制界而类 MyPanel 中设置 3*10 的 iDiskStack HH 二维数组用以表示盘片的位置, 假设 iDiskStack[l][l]=10, 则第 1 个轴上最底下位置上放着第 10 号盘片。(出于若盘片过多,运算量太大, 则程序将无法终止, 故只设最大为 10 个盘片) 假设 iDiskStack[2][10]=5, 则第 2 个轴上最高的位置上放着第 5 号盘片, 以此类推。在每输入一个新的盘片数 N时(1<N<=10), 程序会初始化 1? N 号盘片的位置。并通过函数 MoveStep () 来控制每步的情况。比如程序在运行期间,发出一个一 MoveStep(l,3) 的情求,则程序会搜索 iDiskStackm 里面下标最大的非 0 元素(即 1 号轴上最顶上的盘子) 并将其移动到 iDiskStack[3] 里面下标最小的 0 元素(即1 号轴上最顶上的盘子的紧挨着的上面一个位置), 并调用 paintlmmediately 强制重绘屏幕。三、使用方法: 系统需求硬件: INTEL Pentium II PC 或以上机型。软件: Microsoft Windows 98/ ME /2000/ XP /2003 或 LINUX 等 Java 2 sdk 版或以上 安装方法 1, 首先下载安装 Java 2 sdkl . ( 如果已经正确安装该版本或以上版本的 JSDK , 则可跳到步骤 3)2 ,打开 Windows 的系统变_ fl 属性页,在 path 中添加“C :\j2 sdkl .\ bm ;C :\j2 sdkl .\ jre \ biii ”二项,在 CLASSPATH 添加“?;C :\j2 sdklAl \ lib ;C :\j2 sdkl .\ jre \ lib ”( 其