人工智能(梵塔问题)

梵塔问题实验报告实验目的1. 熟悉和掌握问题规约法的原理、实质和规约过程2. 理解规约图的表示方法3. 熟悉并掌握递归解决问题的思想实验原理1. 利用问题规约法的原理进行问题的分析与描述2. 利用递归思想进行问题的解决实验条件1. Window NT/xp/7及以上的操作系统2. 内存在512M以上3. CPU在奔腾II以上实验内容梵塔问题源于印度古老的一个传说。相传开天辟地的神勃拉玛创造世界时在印度北部的佛教圣地的圣庙里，安放了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。实验分析我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1. 命令僧人63将63个盘子从A座移到C座2. 自己将最底下的最大的一个盘子从A座移到C座3. 再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1. 命令僧人62将62个盘子从A移动到C2. 自己将一个盘子从A座移动到B座3. 再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，该烦他问题得到解决。实验步骤1 主程序流程图初始化过程绘制初始图形汉诺塔求解开始输入盘子数结束主程序流程图2 梵塔求解流程图开始将盘子从A座移到C座n为1？是否递归调用，初始n=n-1盘子数为n结束梵塔问题递归过程流程图退出一级调用n=n+1程序代码#include #include #include #include #include #define PAOGAO 190 /*动画抛高，数值越小越高*/#define PANHOU 10/*#define PANAMOUNT 19盘子数*/ int PANAMOUNT;typedef int pans;typedef struct s_pillar int amount; int x,y; pans pan20; /*存放每个盘的代号*/pillars;pillars pillar4; /*三个台柱*/int movecount=0; /*移动计数*/void drawpillar(pillars p);void init(); /*初始化函数*/void drawmat(char *mat,int matsize,int x,int y,int color); /* 点陈汉字 */void drawpan(pans p,int x,int y);void zimu(); /*显示字幕*/void drawpps(); /*画装盘的台柱*/void hanoi(); /*主算法*/void hanoi(int n,char one,char two,char three);void sdelay(int delay_t); /*函数申明*/void finish(); /*完成！*/void main(void) /*主函数*/ printf(ntplease input n(n=19): );/*输入要演示的盘子数*/ scanf(%d,&PANAMOUNT); if(PANAMOUNT19) /*越界的话n当19处理*/ PANAMOUNT=19 ; init(); drawpps(); hanoi(PANAMOUNT,a,b,c); finish();void init() /* 初始化函数 */ int gd=DETECT,gm ; int i,n,color ; clrscr(); initgraph(&gd,&gm,c:tc); cleardevice(); pillar1.amount = PANAMOUNT; pillar1.x = 105; pillar1.y = 405; for(i=1;i=pillar1.amount;i+) pillar1.pani=pillar1.amount-i+1; pillar2.amount = 0; pillar2.x = 320; pillar2.y = 405; pillar3.amount = 0; pillar3.x = 527; pillar3.y = 405; setcolor(YELLOW); /*柱座标记*/ settextstyle(0,0,2); outtextxy(105,418,A); outtextxy(320,418,B); outtextxy(527,418,C); setcolor(YELLOW); /*画框*/ setlinestyle(SOLID_LINE,0,NORM_WIDTH); line(0,0,0,479); line(0,0,639,0); line(639,0,639,479); line(0,479,639,479); line(0,PAOGAO-PANHOU-40,450,PAOGAO-PANHOU-40); /*黄金线*/ settextstyle(0,0,1); outtextxy(250,PAOGAO-PANHOU-50,Press ANY Key to EXIT !); /*线上字*/ zimu();void drawpillar(pillars p) /*画柱*/ int x,y,mount; x=p.x; y=p.y; mount=p.amount; setfillstyle(SOLID_FILL,BROWN); bar(x,(y-mount*PANHOU-20),x+5,y); bar(x-45,y,x+55,y+5);void drawmat(char *mat,int matsize,int x,int y,int color)/*依次：字模指针、点阵大小、起始坐标(x,y)、颜色*/int i,j,k,n; n=(matsize-1)/8+1; for(j=0;jmatsize;j+) for(i=0;in;i+) for(k=0;kk) /*测试为1的位则显示*/ putpixel(x+i*8+k,y+j,color);void drawpan(pans p,int x,int y) setfillstyle(SOLID_FILL,LIGHTGRAY); bar(x-(5+5*p),y-PANHOU+1,x+(5+5*p),y); setlinestyle(SOLID_LINE,0,NORM_WIDTH); setcolor(BLACK); line(x-(5+5*p),y,x+(5+5*p),y); line(x-(5+5*p),y+1,x+(5+5*p),y+1);void clearpan(pans p,int x,int 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,mount; for(i=1;i=3;i+) p = pillari; x = p.x; y = p.y; mount = p.amount; drawpillar(p); /*画台柱*/ for(j=1; j=15) clearprocess();/*清除步骤提示*/ movecount = movecount%15+1; /*模20+1*/ setcolor(RED); /*输出移动过程*/ settextstyle(TRIPLEX_FONT, HORIZ_DIR, 1); outtextxy(560,30+movecount*10,a); outtextxy(580,30+movecount*10,-); outtextxy(620,30+movecount*10,b); setfillstyle(SOLID_FILL,BLACK);/*涂黑_重画*/ bar(3,pillar1.y-PANHOU*19-20,584,412); drawpps(); /*重画*/ action(data,pillarifrom,pillarito);/*此处添加动画函数*/ pillarito.amount+; /*入栈*/ mountt = pillarito.amount;/*刷新数量*/ pillarito.panmountt = data; drawpps(); /*重画*/void clearprocess() int i; setfillstyle(SOLID_FILL,BLACK); for(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(int 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; /*整形变量用与当前帧*/ x1 = (float)(fromp.x); y1 = (float)(fromp.y - fromp.amount*PANHOU -20); /*PANHOU为盘厚常数,减20处理，以便避开柱子*/ x2 = (float)(top.x); y2 = (float)(top.y - top.amount*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