人工智能化梵塔问题

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

2、，但每次只能搬一个，而且大的不能放在小的上面。值班僧侣按照法则日夜不停地搬运，当搬运完成时世界将在一声霹雳中毁灭。实验分析我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64o僧人自然会这样想：假如有另外一个僧人能有办法将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

3、.命令僧人62将62个盘子从A移动到C2 .自己将一个盘子从A座移动到B座3 .再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，该烦他问题得到解决。实验步骤主程序流程图主程序流程图梵塔求解流程图梵塔问题递归过程流程图程序代码#include<stdio.h>#include<graphics.h>#include<time.h>#include<dos.h>

4、;#include<math.h>#definePAOGAO190/*动画抛高，数值越小越高*/#definePANHOU10/*#definePANAMOUNT19盘子数*/intPANAMOUNT;typedefintpans;typedefstructs_pillarintamount;intx,y;panspan20;/*存放每个盘的代号*/pillars;pillarspillar4;/*三个台柱*/intmovecount=0;/*移动计数*/voiddrawpillar(pillarsp);voidinit();/*初始化函数*/voiddrawmat(char*ma

5、t,intmatsize,intx,inty,intcolor);/*点陈汉字*/voiddrawpan(pansp,intx,inty);voidzimu();/*显示字幕*/voiddrawpps();/*画装盘的台柱*/voidhanoi();/*主算法*/voidhanoi(intn,charone,chartwo,charthree);voidsdelay(intdelay_t);/*函数申明*/voidfinish();/*完成！*/voidmain(void)/*主函数*/(printf("ntpleaseinputn(n<=19):");/*输入要演示

6、的盘子数*/scanf("%d”,&PANAMOUNT);if(PANAMOUNT<1|PANAMOUNT>19)/*越界白话n当19处理*/PANAMOUNT=19;init();drawpps();hanoi(PANAMOUNT,'a','b','c');finish();voidinit()/*初始化函数*/(intgd=DETECT,gm;inti,n,color;clrscr();initgraph(&gd,&gm,"c:tc");cleardevice();pillar

7、1.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,&qu

8、ot;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,"PressANYKeyt

9、oEXIT!");/*线上字*/zimu();voiddrawpillar(pillarsp)/*画柱*/intx,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);voiddrawmat(char*mat,intmatsize,intx,inty,intcolor)/*依次：字模指针、点阵大小、起始坐标(x,y)、颜色*/inti,j,k,n;n=(matsize-1)/8+1;for(j=0;

10、j<matsize;j+)for(i=0;i<n;i+)for(k=0;k<8;k+)if(matj*n+i&(0x80>>k)/*测试为1的位则显示*/putpixel(x+i*8+k,y+j,color);voiddrawpan(pansp,intx,inty)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

11、+5*p),y);line(x-(5+5*p),y+1,x+(5+5*p),y+1);voidclearpan(pansp,intx,inty)setfillstyle(SOLID_FILL,BLACK);bar(x-(5+5*p),y-PANHOU,x+(5+5*p),y);)voiddrawpps()/*画装盘的台柱*/pillarsp;inti,j;intx,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<=mount;j+)drawpan(

12、p.panj,x,y-PANHOU*(j-1);voidhanoi(intn,charone,chartwo,charthree)(voidmove(charx,chary);/*声明*/if(n=1)(move(one,three);)else(hanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);)voidmove(charx,chary)(voidclearprocess();/*申明函数*/voidaction();/*申明移动动画函数*/intifrom,ito;pansdata;intmountf,mou

13、ntt;chara1;charb1;a0=x;a1='0'b0=y;b1='0'ifrom=x-96;ito=y-96;mountf=pillarifrom.amount;/*数量*/mountt=pillarito.amount;data=pillarifrom.panmountf;pillarifrom.amount-;/*出栈*/sdelay(6);/*暂停屏幕*/if(movecount>=15)clearprocess();/*清除步骤提示*/movecount=movecount%15+1;/*模20+1*/setcolor(RED);/*输出

14、移动过程*/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);/*此处添加动画函数*

15、/pillarito.amount+;/*入栈*/mountt=pillarito.amount;/*刷新数量*/pillarito.panmountt=data;drawpps();/*重画*/voidclearprocess()inti;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)秒*/voidsdelay(intdelay_t)(clock_tstart_time;start_time=c

16、lock();while(clock()-start_time)<delay_t);/*循环空语句*/)voidaction(panspan,pillarsfromp,pillarstop)/*移动动画*/(floatx1,y1,x2,y2;floatp,q,a;intx,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*PANH

17、OU);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)/(x2-a);/*除以平方*/if(x1<=x2)(for(x=floor(x1+0.5);x<floor(x2+0.5);x=x+7)(if(kbhit()exit();/*用户按ESC则退出*/y=floor(p*(x-a)*(x-a)+PAOGAO)+0.5);drawpan(pan,x,y);sdelay(1);clearpan(pan,x,y);/*清除轨迹*/else(for(x=floor(x1+0.5);x>floor(x2+0.5);x=x-7)if(kbhit()exit();/*用户按ESC则退出*/