模拟显示"汉诺塔"问题解决过程

“汉诺塔”是在十九世纪末欧洲出现的一种游戏。游戏的装置是一块铜板，上面有三

根杆，最左杆自下而上、由大到小顺序串有６４个金盘，呈一塔形。游戏的目的是把左边

杆上的金盘全部移到最右边的杆上，规定一次只能移动一个盘，并且不允许大盘在小盘上

面。

下面的程序是让计算机模拟显示“汉诺塔”问题解决过程，使用ＴＵＲＢＯ Ｃ语言

编写。程序里面运用数学函数、输入输出函数、内存分配函数、图形函数及栈的应用。

开始时要求输入金盘数量及移动金盘的速度，该程序金盘数量不大于１５个（修改程序可

达到６４个），按下任一键开始动作并且显示所需要移动金盘的总步数。用不同颜色、不

同大小的长方形表示不同的金盘。另外，输入速度数值越大则模拟显示速度越快。源程序

如下（程序在ＴＵＲＢＯ Ｃ２.０下运行通过）：
/* 模拟显示“汉诺塔”问题解决过程趣味程序 */
#include “stdlib.h”

#include “math.h”

#include “graphics.h”

void hanh(void);

void hanpp(int a,int b);

void hanpush(int b,int k);

int hanpop(int a);

void *block[16];

int HH,i,n,nn,v;

int *bos[3],*tos[3];
movetower(int h,int f,int t,int u) /* 递归调用 */

{ if(h==1)

{ i–;

hanpp(f,t);

delay((32767-v)/10);

}

else

{  movetower(h-1,f,u,t);

i++;

hanpp(f,t);

delay((32767-v)/10 );

movetower(h-1,u,t,f);

}

}
void  hanpp(int a,int b) /* Plate移动*/

{ int k;

k=hanpop(a);

hanpush(b,k);

}
hanpop(int a) /* Plate出栈 */

{ int r,hh;

tos[a]–; r=*tos[a];

hh=tos[a]-bos[a]+1;

putimage(a*100,400-hh*10,block[r],XOR_PUT);

return(r);

}
void hanpush(int b,int k) /* Plate入栈 */

{ int r,hh;

*tos=k; tos++;

hh=tos-bos;

putimage(b*100,400-hh*10,block[k],XOR_PUT);

}

void hanh(void) /* 栈初始化 */

{ int  size,i,x1,x2,y1,y2,hh;

size=imagesize(0,0,100,10);

for(i=1 ;i<=HH;i++)

block=malloc(size);

cleardevice();  setcolor(15);

line(0,301,100,301);

line(50,301,50,150);

f or(i=HH;i>0;i–)

{ x1=50-i*10/2;

y1=310-(HH+1-i)*10;

x2=50+i*10/2;  y2=302-(HH+1-i)*10;

setfillstyle(1,(HH+1-i));

bar(x1,y1,x2 ,y2);

getimage(0,y1,99,y2,block );

}

cleardevice();

printf(” Hit any key to  begin…”);

line(0,401,300,401);

line(50,401,50,250);

lin e(150,401,150,250);

line(250,401,250,250);

for(i=0;i<3; i++)

{ bos=(int *)malloc(HH*sizeof(int));

tos=bos;

}

for(i=HH;i>0;i–)

{ *tos[0]=i;

hh=tos[0]-bos[0];

putimage(0,390-hh*10,block,XOR_PUT);

tos[0]++;

}

getch();

}
main()

{ int a=0,b=1,c=2;

int gdriver=DETECT,gmode;

clrscr();

printf(“Input number of plate—n(n<=15):”);

scanf(“%d”,&n);

printf(“input move speed(0<v<32767)”);

scanf(“%d”,&v);

if((n>15 || n<1) || (v<=0) || (v>32767))

{

printf(“Error in input data!\n”); exit(0);

}

initgraph(&gdriver,&gmode,”"); /* 图形初始化 */

HH=n;

nn=pow(2,n);

hanh();

printf(” All Move Steps=%d”,nn-1);

movetower(n,a,b,c);

printf(“\t The Game Over!\n\n”);

getch();

closegraph();

}