汉诺塔演示.doc

1、汉诺塔演示.txt 你不能让所有人满意，因为不是所有的人都是人成功人士是在牛 B 的路上，一路勃起你以为我会眼睁睁看着你去送死吗？我会闭上眼睛的摘要:该文对经典的“汉诺塔”问题进行了详细的分析,并用 C 语言实现。通过问题的具体实现,使学习者了解问题的全过程,推广到一般。关键词:汉诺塔;递归;C 语言 Algorithm Analysis and C Realization of Hanio IssueBAI Hui-bo1,GAO Rui-ping2(1.Qinhuangdao Branch of Daqing Petroleum Institute, Qinhuangdao 066004,

2、 China;2.Hebei Normal University of Science and Technology, Qinhuangdao 06600, China)Abstract: This text carries on detailed analysis about classical Hanio issue and provides realization of algorithm in C.Through concrete realization of the problem,can make learners observe the whole course which so

3、lves this issue and Extend to the general.Key words: hanio; recursive; the C programming language1 问题描述汉诺塔是一个经典的数学问题,其具体描述如下:有三根相邻的塔子,标号为 A,B,C,A 塔子上从下到上按金字塔状叠放着 n 个不同大小的圆盘,现在把所有盘子借助于 A,B,C 三个塔子一个一个移动到塔子 C 上,并且每次移动在同一根塔子上都不能出现大盘子在小盘子上方.根据问题描述得到以下规则:1)圆盘必须一个一个的移动;2)大的圆盘必须在小圆盘的下方或单一圆盘;3)满足规则 2)的序列可以出现

4、在 A,B,C 任意一根塔子上。C 语言演示程序规则:1)输入一个盘子的个数 n(时间可接受范围内的值 0 2)用 C 语言演示盘子在塔 A,B,C 间的移动全过程。2 算法分析题目实现的是设计一个盘子移动的方案,使得 A 塔上的所有盘子借助于 B 塔按照原来的次序移动到 C 塔上,并且给出完整的最佳的盘子移动的方案。从实际的具体的盘子的移动过程来分析,找出问题内在的规律。当 n=1 时,问题比较简单,只要将塔 A 上的编号为 1 盘子直接移动到塔 C 即可;当 n1 时,需利用塔 B 作为辅助塔,若能设法将压在编号为 n 的盘子之上的 n-1 个盘子从塔 A(依据移动规则)移至塔 B 上,则

5、可将编号为 n 的盘子从塔 A 移至塔 C,然后再将塔 B 上的 n-1 个盘子(依据移动规则)移至塔 C;经分析可知,在移动的过程中, 将始终会出现这样的状态情况: (n-1)个盘子将会以从下到上、从大到小的次序叠置在 B 塔上,这时,A 塔上第 n 个盘子就能被轻而易举叠放到 C 塔上; 接着, 我们再把 B 塔上的共(n-1)个盘子移动到 C 塔上, 问题好像已经解决。但 B 塔上(n-1)个盘子怎么移动到 C 塔上呢?同样, 利用塔 C 作为辅助塔, 将会出现这样的状态情况:(n-2)个盘子将会以从上到下、从小到大的次序叠置在 A 塔上,这时,B 塔上第(n-2)个盘子就能被轻而易举放

6、到 C 塔上;接着,把 A 塔上的共(n-2)个盘子移动到 C 塔上。这明显是一个递归的过程,不断深入,不断细小化,最终,将到达仅有一个盘的情形,这时, 递归也就终止了,问题也得到了解决。通过以上分析,递归的出口是当 n=1 时,能直接得到解。现在,严格按照递归算法来解决问题。先定义递归方法 Hanio(int n,zarray * A, zarray *B, zarray *C),按如下步骤进行解题(设初始盘子个数为 N):若 A 塔上仅仅只有一个盘子(n=1), 则直接从 A 移动到 C,问题完全解决。若 A 塔上有一个以上的盘子(n1),则需要考虑以下三个步骤。第一步: 把(n-1)个盘

7、子从 A 塔经过移动, 叠放到 C 塔上。在不违反规则情况下,所有(n-1)个盘子不能作为一个整体一起移动,而是要符合要求地从一个塔移到另一个塔上。用Hanio(n-1,A,C,B)调用递归方法,注意:这里是借助于 C 塔,将(n-1)个盘子从 A 塔移动到 B 塔, A 是源塔, B 是目标塔。第二步: 将剩下的第 n 个盘子(也就是最底下的一个)直接从 A 塔叠放到空着的 C 塔上。第三步: 用第一步的方法,再次将 B 塔上的所有盘子叠放到 C 塔上。同样,这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用 Hanio(n-1,B,A,C)调用递归方法, 注意:这里是借助于

8、A 塔,将(n-1)个盘子从 B 塔移动到 C 塔,B 是源塔,C 是目标塔。这个算法达到了预期的目标,即在 C 塔上按正确的次序叠放了所有的圆形盘子。3 算法实现定义结构体 plate 表示盘子:typedef struct int x,y,xsize,ysize;/*盘子通过绘制椭圆实现,x,y,xsize,ysize 确定椭圆的大小*/int No;/*盘子的编号,编号为 0 的表示塔柱,大于零的是盘子*/plate;定义一个堆栈 zarray 来表示塔:typedef structplate pINIT_SIZE;int top;/*栈顶*/int x,y,xof,yof; /*塔的绘

9、制视区*/zarray;用 zarray 的三个变量 A、B、C 分别表示三个塔,初始盘子在 A 塔,设置屏幕绘制区域并相对与绘制区域分别绘制 A、B、C 三塔、盘子,并在相应盘子的位置标明其编号(编号和盘子一起移动)调用 hanoi()函数,并在 move()函数中源塔和目标塔的盘子进行绘制。程序的主要函数由:initZarray(),setLongth(),getplate(),pushplate(),popplate(), outNo(),toDraw(),toDrawZhu(),getn(),hanoi(),move()等组成。initZarray()负责塔 A,B,C 数据的初始化,

10、 pushplate()负责将盘子压入目标塔中,并对新压入的盘子进行绘制,popplate()负责从源塔取下一个盘子,并对源塔进行重新绘制。 1)函数 main()的算法函数 main()的算法如图 1,程序执行用户根据提示输入合法的 n 值,根据得到的 n 值初始化塔A,B,C 和 n 个盘子的大小,设置绘图视区在屏幕上绘制塔 A,B,C 和盘子,调用 hanoi()函数。2)函数 hanoi()的算法函数 hanoi()的算法如图 1,当程序第一被调用时,源塔 A 有 n 个盘子,将塔 C 作为辅助塔,调用 move()函数将源塔 A 上的 n-1 个盘子移至塔 B 上,将源塔 A 上的编

11、号为 n 的盘子移到目标塔 C,完成将最大盘子移至目标塔 C,接下来,将塔 B 作为源塔有 n-1 个盘子,塔 A 作为辅助塔递归调用,每次都将源塔上的最大盘子移至目标塔,直到递归结束。3)函数 move()的算法函数 move()的算法如图 2,函数的作用就是调用 popplate()函数,将源塔出栈重绘,再将出栈的盘子 p 调用 pushplate()函数压入目标塔,重新绘制。popplate()函数和 pushplate()见图2。4 结束语本文深入分析了用递归实现汉诺塔的问题,并用图形仿真程序显示的盘子的移动过程,对汉诺塔的本质进行了新的剖析,对数据结构的教学有一定的好处。参考文献:1 严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,1996.2 王强如.C 语言绘图与计算机仿真技术M.北京:北京航空航天大学出版社,1995.本文来源于 (论文网) 原文链接：http:/