基于递归算法的Hanoi Tower动画演示系统

传统的汉诺塔递归算法需要四个参数。改进后的算法为三个参数,使函数接口更简单易用。汉诺塔的动画演示系统采用了采取离散点的方式展示塔盘在移动过程中动画。动画采取塔盘移动中间路径的有限个点进行模拟动画移动的过程，提高动画演示程序运行的效率。移动塔盘的过程中会遇到中间塔影响，应当移动路径应当跳过中间塔。一次移动动画离散取点个数为10-15个,可模拟出真实的移动效果。

【关键词】递归算法 Hanoi Tower动画演示系统

1 Hanoi Tower问题以及传统的递归算法的解法

汉诺塔问题源自印度神话,大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。常见求解此问题的递归函数为void hanoi(intn,charX,charY,charZ),需要四个参数,即移动的盘子数量n,移动的发源地X塔,移动途径Y塔,移动的目的地Z塔,其中变量X,Y,Z都是字符型变量,取值范围为{A,B,C}。

2 改进后的汉诺塔问题递归算法

传统的算法求解汉诺塔问题函数有四个参数，第三个参数即移动途经的Y塔。这个参数可以省略，因为总共有三个塔，比如塔的名字为甲塔，乙塔，丙塔，假设移动的个数大于1，从甲塔移动到乙塔必然可以推测出借助丙塔。塔的名字为X塔，Y塔，Z塔，假设移动的个数大于1，从X塔移动到Y塔必然可以推测出必借助Z塔 , 从X塔移动到Z塔必然可以推测出必借助Y塔, 从Y塔移动到X塔必然可以推测出借助必Z塔, 从Y塔移动到Z塔必然可以推测出必借助X塔。从Z塔移动到X塔必然可以推测出借助必Y塔, 从Z塔移动到Y塔必然可以推测出必借助X塔。所以新的递归算法就是去掉变量char Y.通过X塔和Z塔可以计算出途径过哪座塔.改进后的汉诺塔函数声明为void han (char x, char y ,inti);函数定义为:

voidhan (char x, char y ,inti)

{

if(i>1)

{

han(x,(char)(3*'B'-x-y), i-1);

han(x , y , 1);

han((char)(3*'B'-x-y) ,y, i-1);

}

else

{ printf("%c --->%c ", x , y );

move(x , y ); push(y , readtop(x));

pull(x);

show();

Sleep(1000);

}

}

其中途徑的塔通过表达式3*'B'-x-y计算出来。用三个塔的字母之和减去已知的两座塔字母和可以得到第三座塔的字母。因为x,y,z三个参数的取值为字符A, B, C,他们的和是3倍的B所以途径的塔通过表达式3*'B'-x-y计算出来。

改进的汉诺塔演示系统开发工具为VC++6.0,使用C语言。程序头文件包含了stdio.h,windows.h以及math.h。使用的库函数有五个,分别为:声明于stdio头文件中的函数getchar(),printf(),以及声明于Windows头文件的GetStdHandle(),SetConsoleCursorPosition(),Sleep().

由于汉诺塔的计算量是以汉诺塔的层数的指数函数,超过10层的汉诺塔计算量已经很大,为量演示方便特设置汉诺塔演示系统的塔的高度小于10. 考虑到方便演示问题,可以定义全局整型常量MaxHigh为汉诺塔的最大高度,数值为5。同时可以定义全局整型常量MaxWidth为汉诺塔最大宽度。MaxHighMaxWidth可设置均设置5。使用若干个符号横向排列模拟汉诺塔上的盘子。汉诺塔的底盘用直线段绘制，如图1所示。

定义全局整型数组Mtrix[3][MaxHigh+1]用于存储三座塔(A塔,B塔,C塔)的从低到高各层盘子的大小.,其中一维数组Mtrix[0]用于存放A塔各层盘子的大小,Mtrix[1]用于存放B塔各层盘子的大小,Mtrix[0]用于存放C塔各层盘子的大小。例如:Mtrix[0][1]表示A塔的第一层(即底层)盘子的大小;Mtrix[0][4]表示A塔的第4层上盘子的大小;Mtrix[1][2]表示B塔的第2层上盘子的大小;Mtrix[2][3]表示C塔的第3层上盘子的大小.但是三个一维数组的首元素不用来保存盘子的大小,而用来保存每个塔的最大有效高度,即每个塔上有盘子的层数。例如：Mtrix[0][0]表示A塔的盘子的层数，Mtrix[1][0]表示B塔的盘子的层数,Mtrix[2][0]表示C塔的盘子的层数。盘子的层数小于等于全局常量MaxHigh。

全局整型变量 Top表示演示塔的图像的垂直方向起始位置，全局整型变量Left表示演示塔的图像的水平方向的起始位置。

函数int* find(char c)用来寻找字母所对应塔的盘数数组的首指针。盘数数组保存了塔的各个层上盘子的大小信息.find函数把塔名和数组联系在一起.find函数定义为:

int* find(char c)

{ intnum = c - 'A';

returnMtrix[num];

}

汉诺塔移动时需要记载移走的盘子,需要修改盘数数组,首先调用find函数寻找盘数数组的首指针,然后找到最上层的盘子令其数据为0,表示盘子移走,最后让记载盘子总数的a[0]减一,表示移走了一个盘子. find函数定义为:

voidpull( char c)

{ int *a = find(c);

a[a[0]] = 0 ;

a[0] --;

}

汉诺塔移动时需要读取记载移走的盘子的大小的信息,需要读取盘数数组,首先调用find函数寻找盘数数组的首指针,然后返回最数组中最上层的盘子的大小。readtop函数定义为:

intreadtop(char x)

{ int *a = find(x);

return a[a[0]];

}

汉诺塔移动时需要记载移来的新的盘子,需要修改盘数数组,首先调用find函数寻找盘数数组的首指针, 然后让记载盘子总数的a[0]加一,表示移来了一个新盘子,最后找到最上层的盘子数据等于以来的盘子的大小. 其函数声明为push( char c , int b) ,其中参数c表示新增盘子所在的塔的名,参数b为移来盘子的大小,其函数定义为:

push( char c , int b)

{ int *a = find(c);

a[0]++;

a[a[0]]= b;

}

汉诺塔需要移动光标来画像素点，进而模拟塔盘的移动，对于控制台应用程序来说需要一个移动控制台光标到制定的坐标(x,y)的函数，x表示垂直方向，y表示水平方向。其函数定义为：

void go(int x, int y)

{

HANDLE hOut =GetStdHandle(STD_OUTPUT_HANDLE);//获取当前窗口句柄

COORD pos= {y, x};

SetConsoleCursorPosition(hOut,pos);

}

塔盘移动的时候需求塔的最高层盘垂直坐标和水平坐标，分别用自定义函数intfindtop(char x)和函数intfindleft(char x)完成坐标的寻找。

汉诺塔演示系统需要展示出移動每一步的移动之后最终图形,用show()函数来完成这一功能,但是show函数不具有演示盘子飞到空中的效果,show函数的定义略去。飞到空中的效果用move函数来完成.move(char x , char y )函数的能是展示出从x塔到y塔的塔盘移动的路径，其中参数x表示出发的塔的名,y表示目标塔的名。move函数的是通过逐帧展示移动盘子的图像来表现移动的动画, move函数调用了自定义函数Draw_kong( int x, int y ),其功能为把盘子从位置(x, y)c处移走后空白的效果。move函数调用自定义函数DrawLine( int x, int y , int width)，其功能为移动长度为witth的塔盘到坐标（x,y）处并显示塔盘。move函数采用了采取离散点的方式展示塔盘在移动过程中动画。动画采取塔盘移动中间路径的有限点进行模拟动画移动的过程，提高动画演示程序运行的效率。离散点的选择方法是均匀选取中间点。离散点的个数为5~9个即可模拟出真实的移动效果。塔盘在二边的塔互相移动的过程,塔盘中会遇到中间塔影响，塔盘移动路径应当跳过中间塔，移动算法仍然采取离散取点的方式展示。

系统需要在main函数完成函数的总调度，首先初始化塔的初始状态，即所有盘子全部在A塔，调用show展示初始状态的图形，然后汉诺塔计算移动核心函数han('A', 'B' , layer),即完成了汉诺塔演示系统的演示。

3 动画展示模块的效果

汉诺塔动画演示系统的效果如图1所示，（a）图展示从A塔到B塔的移动效果,图（b）~（f）展示从A塔到C塔移动一个盘的动态效果,动画展示了移动的中间路径的若干个离散的状态，在移动过程中跨越了中间的B塔，移动的路径是先升后降。每张图的右边文字显示的是移动信息。

参考文献

[1]李健.汉诺塔算法演示系统的设计与实现[J].现代计算机月刊,2011(10):76-80.

[2]孙玉霞.C语言程序设计中若干问题的探讨[J].沈阳航空工业学院学报,2004(03).

[3]张宏梅，鲁邦定.“汉诺塔”问题的算法分析及JAVA实现[J].电脑知识与技术:学术交流,2007,1(01):179-179.

作者简介

杜海龙 (1986-)，男，硕士研究生学历。现为无锡太湖学院物联网工程学院助教。主要研究方向为人工智能与模式识别。

作者单位

无锡太湖学院物联网工程学院 江苏省无锡市 214000