人工智能梵塔问题解读

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

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

3、盘子从A座移动到B座。 他是这样做的：命令僧人62将62个盘子从A移动到C 自己将一个盘子从 A座移动到B座 再命令僧人62将62个盘子移到B座1.2.3.再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成 将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第 1 个僧人，让他完成将一个盘子从一个座移动到另一个座， 至此，全部工作已经完 成，该烦他问题得到解决。实验步骤主程序流程图梵塔求解流程图开始输入盘子数初始化过程绘制初始图形T汉诺塔求解结束主程序流程图梵塔问题递归过程流程图程序代码#in elude #in elude gra phics.h#in elud

4、e #in elude #in elude #define PAOGAO 190 /*动画抛高，数值越小越高*/#defi ne P ANHOU 10/*#define PANAMOUNT 19 盘子数 */int PANAMOUNT;typ edef int pans;typ edef struct s_p illarint amount;int x,y;pans pan20;/*存放每个盘的代号 */p illars;pillars pillar4;/* 三个台柱 */int moveeount=O;/* 移动计数 */void draw pillar( pillars p);void i

5、nit();/*初始化函数*/void drawmat(ehar *mat,i nt matsize,i nt x,i nt y,i nt eolor); /*点陈汉字 */void draw pan(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 fini sh(

6、);void mai n(void) /*主函数*/prin tf(nt please inp ut n(*=19):);/*输入要演示的盘子数 */scan f(%d,&P ANAMOUNT);if(PANAMOUNT19)/* 越界的话 n 当 19 处理 */PANAMOUNT=19 ;ini t();draw pp s();han oi( PANAMOUNT,a,b,c);fin ish();void init() /*初始化函数*/in t gd=DETECT,gm ;int i,n, color ;clrscr();in itgra ph(&gd, &gm,c:tc);cleard

7、evice();pillar1.amou nt = P ANAMOUNT;pillar1.x = 105;pillar1.y = 405;for(i=1;i=p illar1.am oun t;i+)p illar1. pan i=p illar1.am oun t-i+1;P illar2.am ount = 0; pillar2.x = 320; pillar2.y = 405;p illar3.am ount = 0; pillar3.x = 527; pillar3.y = 405;/*柱座标记*/setcolor(YELLOW); settextstyle(0,0,2);outtex

8、txy(105,418,A);outtextxy(320,418,B);outtextxy(527,418,C);setcolor(YELLOW); /* 画框 */setli nestyle(SOLID_LINE,0,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);/*线上字*/outtextxy(250, PAO

9、GAO-PANHOU-50, Press ANY Key to EXIT !); zimu();/*画柱*/void draw pillar( pillars p) int x,y,m ount;x=p.x;y=p.y;mount=p.amount;setfillstyle(SOLID_FILL,BROWN); bar(x,(y-mou nt* PANHOU-20),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)/*依次：字模指针、点阵大小、起始坐标(x,y)

10、、颜色*/int i,j,k, n;n=(matsize-1)/8+1;for(j=0;jmatsize;j+)for(i=0;i n;i+)for(k=0;kk)/* 测试为 1 的位则显示 */putp ixel(x+i*8+k,y+j,color); void draw pan(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);l

11、in e(x-(5+5* p),y,x+(5+5* p),y);lin e(x-(5+5* p),y+1,x+(5+5* p),y+1)；void clear pan(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()/*画装盘的台柱*/p illars p;int i,j;int x,y,m ount;for(i=1;i=3;i+)x = p .x;y = p .y;mount = p .am ount;drawpillar(p)

12、;/* 画台柱 */for(j=1; j=15) clearprocess();/* 清除步骤提示 */ movecount = movecount%15+1; /* 模 20+1*/ setcolor(RED);/*输出移动过程*/settextstyle(TRI PLEX_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,BLACK);/涂黑 _

13、重画 */ bar(3, pillar1.y- PANHOU*19-2O,584,412); drawpps();/* 重画 */acti on (data, pillarifrom, pillarito);/*此处添加动画函数*/pillarito.amount+;/* 入栈 */mountt = pillarito.amount;/*刷新数量 */*重画*/p illarito. panmoun tt = data;draw pp s();void clear pro cess()int i;setfillstyle(SOLID_FILL,BLACK);for(i=0;i=16;i+)ba

14、r(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;int x,y,temp;/*整形变量用与当前帧

15、*/x1 = (float)(fro mp. x);y1 = (float)(fro mp.y - fromp .amou nt* PANHOU -20);/*PANHOU为盘厚常数，减20处理，以便避开柱子*/x2 = (float)(t op .X);y2 = (float)(to p.y - top .amou nt* PANHOU);q = -sqrt(y1- PAOGAO)/(y2-PAOGAO); /* 此处注意产生增根 */if(1-q)/*除数不为0*/a = (x1 - x2*q)/(1-q);elsea = (x1+x2)/2.0;p = (y2-PAOGAO)/(x2-a

16、)/(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); draw pan(pan, x,y);sdelay(1);clearpan(pan,x,y);/* 清除轨迹 */*完成！ */void fini sh()getch();closegra ph(); 程序运行效果图Ad2+J+J+J个人实验小结通过本次实验，我学会了熟悉并掌握问题规约法的原理、实质和规约过程，理 解了规约图的表示方法，熟悉并掌握递归解决问题的思想。使我的软件编程思维 能力得到了很大的提升，使我的自身能力有了长足的进步。读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟。3、读书破万卷，下笔如有神达尔文4、我所学到的任何有价值的知识都是由自学中得来的。5、少壮不努力，老大徒悲伤6、黑发不知勤学早，白首方悔读书迟颜真卿7、宝剑锋从磨砺出，梅花香自苦寒来。8、读书要三到：心