摘要:该文对经典的“汉诺塔”问题进行了详细的分析,并用C语言实现。通过问题的具体实现,使学习者了解问题的全过程,推广到一般。
关键词:汉诺塔;递归;C语言
中图分类号:TP301.6文献标识码:A文章编号:1009-3044(2010)09-2130-02
Algorithm Analysis and C Realization of Hanio Issue
BAI Hui-bo1,GAO Rui-ping2
(1.Qinhuangdao Branch of Daqing Petroleum Institute, Qinhuangdao 066004, 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 solves this issue and Extend to the general.
Key words: hanio; recursive; the C programming language
1 问题描述
汉诺塔是一个经典的数学问题,其具体描述如下:有三根相邻的塔子,标号为A,B,C,A塔子上从下到上按金字塔状叠放着n个不同大小的圆盘,现在把所有盘子借助于A,B,C三个塔子一个一个移动到塔子C上,并且每次移动在同一根塔子上都不能出现大盘子在小盘子上方.根据问题描述得到以下规则:
1)圆盘必须一个一个的移动;
2)大的圆盘必须在小圆盘的下方或单一圆盘;
3)满足规则2)的序列可以出现在A,B,C任意一根塔子上。
C语言演示程序规则:
1)输入一个盘子的个数n(时间可接受范围内的值0
2)用C语言演示盘子在塔A,B,C间的移动全过程。
2 算法分析
题目实现的是设计一个盘子移动的方案,使得A塔上的所有盘子借助于B塔按照原来的次序移动到C塔上,并且给出完整的最佳的盘子移动的方案。
从实际的具体的盘子的移动过程来分析,找出问题内在的规律。当n=1时,问题比较简单,只要将塔A上的编号为1盘子直接移动到塔C即可;当n>1时,需利用塔B作为辅助塔,若能设法将压在编号为n的盘子之上的n-1个盘子从塔A(依据移动规则)移至塔B上,则可将编号为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)个盘子就能被轻而易举放到C塔上;接着,把A塔上的共(n-2)个盘子移动到C塔上。
这明显是一个递归的过程,不断深入,不断细小化,最终,将到达仅有一个盘的情形,这时, 递归也就终止了,问题也得到了解决。通过以上分析,递归的出口是当n=1时,能直接得到解。现在,严格按照递归算法来解决问题。先定义递归方法Hanio(int n,zarray * A, zarray *B, zarray *C),按如下步骤进行解题(设初始盘子个数为N):若A塔上仅仅只有一个盘子(n=1), 则直接从A移动到C,问题完全解决。若A塔上有一个以上的盘子(n>1),则需要考虑以下三个步骤。
第一步: 把(n-1)个盘子从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)调用递归方法, 注意:这里是借助于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 struct
{plate p[INIT_SIZE];
int top;/*栈顶*/
int x,y,xof,yof; /*塔的绘制视区*/
}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数据的初始化, 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上的编号为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.