人工智能(梵塔问题)(20201220084548)

1、梵塔问题实验报告 实验目的 1. 熟悉和掌握问题规约法的原理、实质和规约过程 2. 理解规约图的表示方法 3. 熟悉并掌握递归解决问题的思想 实验原理 1. 利用问题规约法的原理进行问题的分析与描述 2. 利用递归思想进行问题的解决 实验条件 1. Window NT/xp/7及以上的操作系统 2. 内存在512M以上 3. CPU在奔腾II以上 实验内容 梵塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在 印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个 圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不 倦地把它们一个个地从这根棒搬

2、到另一根棒上，规定可利用中间的一根棒作为帮 助，但每次只能搬一个，而且大的不能放在小的上面。 值班僧侣按照法则日夜不 停地搬运，当搬运完成时世界将在一声霹雳中毁灭。 A+JB*C+J 实验分析 我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然 会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座， 那么问题就解决了，此时僧人 64只需这样做： 1. 命令僧人63将63个盘子从A座移到C座 2. 自己将最底下的最大的一个盘子从 A座移到C座 3. 再命令僧人63将63个盘子从B座移到C座 为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一 个

3、僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。 他是这样做的： 1. 命令僧人62将62个盘子从A移动到C 2. 自己将一个盘子从A座移动到B座 3. 再命令僧人62将62个盘子移到B座 再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成 将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1 个僧人，让他完成将一个盘子从一个座移动到另一个座， 至此，全部工作已经完 成，该烦他问题得到解决。 实验步骤 主程序流程图 主程序流程图 梵塔求解流程图 开始 梵塔问题递归过程流程图 程序代码 #i nclude #in elude #in elu

4、de #in elude #in elude #define PAOGAO 190 /*动画抛高，数值越小越高*/ #defi ne PANHOU 10 /*#define PANAMOUNT 19 盘子数 */ int PANAMOUNT; typedef int pans; typedef struct s_pillar int amount; int x,y; pa ns pan 20;/*存放每个盘的代号 */ pillars; pillars pillar4;/* 三个台柱 */ int movecount=O;/* 移动计数 */ void drawpillar(pillars p

5、); void init();/*初始化函数*/ void drawmat(char *mat, int matsize,i nt x,i nt y,i nt color); /* 点陈汉字*/ void drawpa n(pans p,i nt x,i nt y); void zimu();/* 显示字幕 */ void drawpps();/*画装盘的台柱*/ void hanoi();/* 主算法 */ void hanoi(int n, char on e,char two,char three); void sdelay(int delay_t); /* 函数申明 */ void f

6、inish();/* 完成！ */ void main(void)/* 主函数 */ prin tf(ntplease in put n(*=19):);/*输入要演示的盘子数 */ scan f(%d, if(PANAMOUNT19) /* 越界的话 n 当 19 处理 */ PANAMOUNT=19 ; ini t(); drawpps(); han oi(PANAMOUNT,a,b,c); fin ish(); void init() /*初始化函数 */ int gd=DETECT,gm ; int i,n, color ; clrscr(); in itgraph( cleardev

7、ice(); pillar1.amou nt = PANAMOUNT; pillar1.x = 105; pillar1.y = 405; for(i=1;i=pillar1.am oun t;i+) pillar1.pa ni=pillar1.am oun t-i+1; pillar2.am ount = 0; pillar2.x = 320; pillar2.y = 405; pillar3.am ount = 0; pillar3.x = 527; pillar3.y = 405; setcolor(YELLOW);/* 柱座标记 */ settextstyle(0,0,2); outt

8、extxy(105,418,A); outtextxy(320,418,B); outtextxy(527,418,C); setcolor(YELLOW); /* 画框 */ setli nestyle(SOLID_LINE,O,NORM_WIDTH); li ne(0,0,0,479); lin e(0,0,639,0); lin e(639,0,639,479); lin e(0,479,639,479); /*线上字*/ line(0,PAOGAO-PANHOU-40,450,PAOGAO-PANHOU-40); /* 黄金线 */ settextstyle(0,0,1); outte

9、xtxy(250,PAOGAO-PANHOU-50,Press ANY Key to EXIT !); zimu(); void drawpillar(pillars p)/* 画柱 */ int x,y,m ount; x=p.x; y=p.y; moun t=p.am ount; setfillstyle(SOLID_FILL,BROWN); bar(x,(y-mou nt*PANHOU-2O),x+5,y); bar(x-45,y,x+55,y+5); void drawmat(char *mat, int matsize,i nt x,i nt y,i nt color) /*依次：字

10、模指针、点阵大小、起始坐标(x,y)、颜色*/ i nt i,j,k, n; n=( matsize-1)/8+1; for(j=0;jmatsize;j+) for(i=0;i n;i+) for(k=0;k8;k+) if(matj*n+i void drawpa n(pans p,i nt x,i nt y) setfillstyle(SOLID_FILL,LIGHTGRAY); bar(x-(5+5*p),y-PANHOU+1,x+(5+5*p),y); setli nestyle(SOLID_LINE,O,NORM_WIDTH); setcolor(BLACK); lin e(x-(

11、5+5*p),y,x+(5+5*p),y); lin e(x-(5+5*p),y+1,x+(5+5*p),y+1); void clearpa n(pans p,i nt x,i nt y) setfillstyle(SOLID_FILL,BLACK); bar(x-(5+5*p),y-PANHOU,x+(5+5*p),y); void drawpps() /*画装盘的台柱*/ pillars p; int i,j; int x,y,m ount; for(i=1;i=3;i+) p = pillari; x = p.x; y = p.y; mount = p.am ount; drawpil

12、lar(p);/* 画台柱 */ for(j=1; j=15) clearprocess();/* 清除步骤提示 */ movecount = movecount%15+1; /* 模 20+1*/ setcolor(RED); /*输出移动过程*/ settextstyle(TRIPLEX_FONT, HORIZ_DIR, 1); outtextxy(560,30+movecou nt*10,a); outtextxy(580,30+movecou nt*10,-); outtextxy(620,30+movecou nt*10,b); setfillstyle(SOLID_FILL,BLA

13、CK);/*涂黑 _ 重画 */ bar(3,pillar1.y-PANHOU*19-20,584,412); drawpps();/* 重画 */ acti on (data,pillarifrom,pillarito);/*此处添加动画函数 */ pillarito.amount+;/* 入栈 */ mountt = pillarito.amount;/*刷新数量 */ pillarito.pa nmoun tt = data; drawpps();/* 重画 */ void clearprocess() int i; setfillstyle(SOLID_FILL,BLACK); for

14、(i=0;i=16;i+) bar(545,30+i*10,638,40+i*10); sdelay(1);/* 动画延迟 n 个(1/18.2)秒*/ 整数1代表(1/18.2)秒*/ void sdelay(i nt delay_t) clock_t start_time ; start_time=clock(); while(clock()-start_time)delay_t) ; /* 循环空语句 */ void action(pans pan,pillars fromp,pillars top)/* 移动动画 */ float x1,y1,x2,y2; float p,q,a; i

15、nt x,y,temp;/*整形变量用与当前帧*/ x1 = (float)(fromp.x); y1 = (float)(fromp.y - fromp.amou nt*PANHOU -20); /*PANHOU为盘厚常数，减20处理，以便避开柱子*/ x2 = (float)(top.x); y2 = (float)(top.y - top.amou nt*PANHOU); q = -sqrt(y1-PAOGAO)/(y2-PAOGAO); /* 此处注意产生增根 */ if(1-q)/*除数不为0*/ a = (x1 - x2*q)/(1-q); else a = (x1+x2)/2.0; p = (y2-PAOGAO)/(x2-a)/(x2-a);/* 除以平方 */ if(x1 = x2) for(x=floor(x1+0.5); xfloor(x2+0.5); x=x- 7 ) if(kbhit() exit(); /* 用户按 ESC则退出 */ y = floor(p*(x-a)*(x-a)+PAOGAO)+0.5); drawpa n(p