人工智能(梵塔问题)上课讲义

人工智能（梵塔问题）

学习好资料

梵塔问题实验报告

实验目的

1.熟悉和掌握问题规约法的原理、实质和规约过程

2.理解规约图的表示方法

3.熟悉并掌握递归解决问题的思想

实验原理

1.利用问题规约法的原理进行问题的分析与描述

2.利用递归思想进行问题的解决

实验条件

1.WindowNT/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移动到C

2.自己将一个盘子从A座移动到B座

3.再命令僧人62将62个盘子移到B座

再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完

成招2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第

1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已

经完成，该烦他问题得到解决。

实验步骤

⑴主程序流程图

士理良法拜囱

（2）梵塔求解流程图

精品资料

学习好资料

林铉附厮延I口■锂公用

程序代码

#include<stdio.h>

//include<graphics.h>

//include<time.h>

#include<dos.h>

#include<math.h>

#definePAOGAO190/*动画抛高，数值越小越高*/

#definePANHOU10

/*#definePANAMOUNT19盘子数*/

intPANAMOUNT;

typedefintpans;

typedefstructs_pillar

{"

intamount;

intxzy;

panspan[20];/*存放每个盘的代号*/

Jpillars;

pillarspillar[4];/*三个台柱*/

intmovccount=0;/*移动计数*/

精品资料

学习好资料

voiddrawpillar(pillarsp);

voidinit();/*初始化函数*/

voiddrawmatfchar*matjntmatsizejntxjntyjntcolor);/*点陈汉字*/

voiddrawpan(panspjntxjnty);

voidzimu();/*显示字幕*/

voiddrawpps();/*画装盘的台柱*/

voidhanoi();/*主算法*/

voidhanoi(intn,charone,chartwo,charthree);

voidsdelay(intdelay」);/*函数申明*/

voidfinishf);/*完成!*/

voidmain(void)/*主函数*/

{

printf("\n\tpleaseinputn(n<=19):”);/*输入要演示的盘子数*/

scanf("%d",&PANAMOUNT);

if(PANAMOUNT<l||PANAMOUNT>19)/*越界的话n当19处理*/

PANAMOUNT=19;

init();

drawppsf);

hanoifPANAMOUNL'a'/b'/c');

finish();

)

voidinit()/*初始化函数*/

{

intgd=DETECT,gm;

inti,n,color;

clrscr();

initgraph(&gd,&gm,"c:\\tc");

cleardevice();

pillar[l].amount=PANAMOUNT;

精品资料

学习----------好资料

pillar[l].x=105;

pillar[l].y=405;

for(i=l;i<=pillar[l].amount;i++)

{

pillar[l].pan[i]=pillar[l].amount-i+l;

)

p川ar[2].amount=0;

pillar[2].x=320;

pillar[2].y=405;

p川ar[3].amount=0;

pillar[3].x=527;

pillar[3].y=405;

setcolor(YELLOW);/*柱座标记*/

settextstyle(0,0,2);

outtextxy(105,418JA")；

outtextxy(320,418jB“)；

outtextxy(527,418,"C");

setcolor(YELLOW);/*画框*/

setlinestyle(SOLID_LINE,0,NORM_WIDTH);

lineO0,0,479);

line。。,639,0);

line(639,0,639,479);

line(0,479,639,479);

line(0,PAOGAO・PANHOU-40,450,PAOGAO・PANHOU・4。);/*黄金线*/

settextstyle(O,O,l)；

/*线上字*/

outtextxy(250zPAOGAO-PANHOU-50,"PressANYKeytoEXIT!");

zimu();

)

voiddrawpillarfpillarsp)/*画柱*/

{

intx,y,mount;

x=p.x;

y=py;

mount=p.amount;

setfillstyle(SOLID_FILL,BROWN);

bar(x,(y-mount*PANHOU-20),x+5,y);

bar(x-45,yzx+55,y+5);

精品资料

学习好资料

)

voiddrawmat(char*matjntmatsizejntxjntyjntcolor)

/*依次：字模指针、点阵大小、起始坐标(x,y)、颜色*/

{inti,j,k,n;

n=(matsize-l)/8+l;

for(j=0;j<matsize;j++)

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

for(k=0;k<8;k++)

if(mat[j*n+i]&(0x80»k))/*测试为1的位则显示*/

putpixel(x+i*8+k,y+j,color);

)

voiddrawpan(panspjntxjnty)

(

setfillstyle(SOLID_FILL,LIGHTGRAY);

bar(x-(5+5*p),y-PANHOU+l/x+(5+5*p)/y);

setlinestyle(SOLID_LINEzO,NORM_WIDTH);

setcolor(BLACK);

line(x-(5+5*p)/y/x+(5+5*p)/y);

line(x-(5+5*p),y+l/x+(5+5*p),y+l);

)

voidclearpanfpanspjntxjnty)

(

setfillstyle(SOLID_FILL,BLACK);

bar(x-(5+5*p),y-PANHOU,x+(5+5*p),y);

)

voiddrawpps()/*画装盘的台柱*/

{

pillarsp;

intij;

intx,y,mount;

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

{

p=pillar[i];

x=p.x;

y=p-y;

mount=p.amount;

drawpillar(p);/*画台柱*/

精品资料

学习好资料

for(j=l;j<=mount;j++)

drawpan(p.pan[j]/x/y-PANHOU*G-l));

)

)

)

voidhanoi(intn,charone,chartwo,charthree)

{

voidmovefcharx,chary);/*声明*/

if(n==l)

(

movefone.three);

)

else

(

hanoi(n-l,one,threeztwo);

move(one,three);

hanoi(n-lztwo,onez:hree);

)

)

voidmove(charx,chary)

{

voidclearprocessO;/*申明函数*/

voidactionf);/*申明移动动画函数*/

intifromjto;

pansdata;

intmountf,mountt;

chara[l];

charb[l];

a[0]=x;a[l]='\0';

b[O]=y;b[l]='\O';

ifrom=x-96;

ito=y-96;

mountf=pillar[ifrom].amount;/*数量*/

mountt=pillar[ito].amount;

data=pillar[ifrom].pan[mountf];

pillar[ifrom].amount-;/*出栈*/

精品资料

学习好资料

sdelay(6);/*暂停屏幕*/

if(movecount>=15)clearprocess。;/*清除步骤提示*/

movecount=movecount%15+l;/*模20+1*/

setcolor(RED);/*输出移动过程*/

settextstyle(TRIPLEX_FONT,HORIZ_DIR,1);

outtextxy(560,30+movecount*10,a);

outtextxy(580,30+mo\/ecount*10,"…>");

outtextxy(620/30+movecount*10/b);

setfillstyle(SOLID_FILL,BLACK);/*涂黑—重画*/

bar(3,pillar[l].y-PANIIOU*19-20/584,412);

drawpps();/*重画*/

action(data,pillar[ifrom],pillar[ito]);/*此处添加动画函数*/

pillar[ito].amount++;/*入栈*/

mountt=pillar[ito].amount;/*刷新数量*/

pillar[ito].pan[mountt]=data;

drawpps();/*重画*/

)

voidclearprocess()

{

inti;

setfillstyle(SOLID_FILL,BLACK);

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

(

bar(545z30+i*10,638,40+1*10);

sdelay(l);/*动画延迟n个(1/18.2)秒*/

)

精品资料

学习好资料

)

整数1代表(1/18.2)秒*/

voidsdelay(intdelay_t)

("

clock_tstart_time;

start_time=clock();

while((clock()-start_time)<delay_t);/*循环空语句*/

)

voidactionfpanspan,pillarsfromp,pillarstop)/*移动动画*/

(

floatxl/yl/x2/y2;

floatp,q,a;

intxytemp;/*整形变量用与当前帧*/

xl=(float)(fromp.x);

yl=(float)ffromp.y-fromp.amount*PANHOU-20);

/*PANHOU为盘厚常数，减20处理，以便避开柱子*/

x2=(float)(top.x);

y2=(float)ftop.y-top.amount*PANHOU);

q=-sqrt((yl-PAOGAO)/(y2-PAOGAO));/*此处注意产生增根*/

if(l-q)/*除数不为0*/

(

a=(xl-x2*q)/(l-q);

}else

a=(xl+x2)/2.0;

p=(y2-PAOGAO)/(x2-a)/(x2-a);/*除以平方平

if(xl<=x2)

{

for(x=floor(xl+0.5);x<floor(x2+0.5);x=x+7)

(

if(kbhit())exit。;/*用户按ESC则退出*/

y=floor((p*(x-a)*(x-a)+PAOGAO)+0.5);