1、人工智能（梵塔問題） 學(xué)習(xí)好資料 梵塔問題實驗報告 實驗?zāi)康?1. 熟悉和掌握問題規(guī)約法的原理、實質(zhì)和規(guī)約過程 2. 理解規(guī)約圖的表示方法 3. 熟悉并掌握遞歸解決問題的思想 實驗原理 1. 利用問題規(guī)約法的原理進(jìn)行問題的分析與描述 2. 利用遞歸思想進(jìn)行問題的解決 實驗條件 1. Window NT/xp/7及以上的操作系統(tǒng) 2. 內(nèi)存在512M以上 3. CPU在奔騰II以上 實驗內(nèi)容 64 梵塔問題源于印度古老的一個傳說。相傳開天辟地的神勃拉瑪創(chuàng)造世界時 在印度北部的佛教圣地的圣廟里，安放了三根金剛石的棒，第一根上面套著 個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的

2、眾 僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒 作為幫助，但每次只能搬一個，而且大的不能放在小的上面。值班僧侶按照法 則日夜不停地搬運，當(dāng)搬運完成時世界將在一聲霹靂中毀滅。 精品資料 實驗分析 我們假設(shè)把該任務(wù)交給一個僧人，為了方便敘述，將他編號為 64。僧人 自然會這樣想：假如有另外一個僧人能有辦法將 63個盤子從一個座移到另一個 座，那么問題就解決了，此時僧人 64只需這樣做： 1. 命令僧人63將63個盤子從A座移到C座 2. 自己將最底下的最大的一個盤子從 A座移到C座 3. 再命令僧人63將63個盤子從B座移到C座 為了解決將63個盤子從A座移到B座的問題，

3、僧人63又想：如果能再有 一個僧人62能將62個盤子移動到另一座，我就能將 63個盤子從A座移動到B 座。他是這樣做的： 1. 命令僧人62將62個盤子從A移動到C 2. 自己將一個盤子從A座移動到B座 3. 再命令僧人62將62個盤子移到B座 再進(jìn)行一次遞歸。如此“層層下放”，直到后來找到第2個僧人，讓他完成將 2個盤子從一個座移到另一個座，進(jìn)行到此，問題就解決了。最后找到第1個 僧人，讓他完成將一個盤子從一個座移動到另一個座，至此，全部工作已經(jīng)完 成，該煩他問題得到解決。 實驗步驟 主程序流程圖 主程序流程圖 梵塔求解流程圖 程序代碼 #i nclude #in elude vgraphi

4、cs.h #in elude #in elude #in elude #define PAOGAO 190 /動畫拋高，數(shù)值越小越高*/ #defi ne PANHOU 10 /*#defi ne PANAMOUNT 19 盤子數(shù) */ int PANAMOUNT; typedef int pans; typedef struct s_pillar _ int amount; int x,y; pa ns pan 20;/*存放每個盤的代號*/ pillars; pillars pillar4; /* 三個臺柱 */ int movecount=O; /* 移動計數(shù) */ void drawp

5、illar(pillars p); void init();/*初始化函數(shù)*/ void drawmat(char *mat,int matsize,int x,int y,int color); /*點陳漢字*/ void drawpa n(pans p,i nt x,i nt y); void zimu();/*顯示字幕 */ void drawpps();/*畫裝盤的臺柱*/ void han oi();/* 主算法 */ void hanoi(int n, char on e,char two,char three); void sdelay(int delay_t); /* 函數(shù)申明

6、 */ void finish(); /*完成！ */ void mai n(void) /* 主函數(shù) */ prin tf(ntplease in put n(n =19): );/* 輸入要演示的盤子數(shù) */ sca nf(%d, if(PANAMOUNT19) /越界的話 n 當(dāng) 19 處理*/ PANAMOUNT=19 ; ini t(); drawpps(); han oi(PANAMOUNT,a,b,c); fini sh(); void init() /*初始化函數(shù)*/ in t gd=DETECT,gm ; int i,n, color ; clrscr(); in itgra

7、ph( cleardevice(); 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);柱座標(biāo)記 */ settextstyle(0,0

8、,2); outtextxy(105,418,A); outtextxy(320,418,B); outtextxy(527,418,C); setcolor(YELLOW); /畫框 */ setli nestyle(SOLID_LINE,0,NORM_WIDTH); lin e(0,0,0,479); lin e(0,0,639,0); lin e(639,0,639,479); lin e(0,479,639,479); lin e(0,PAOGAO-PANHOU-40,450,PAOGAO-PANHOU-40)黃金線 */ settextstyle(0,0,1); 線上字*/ outt

9、extxy(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-20),x+5,y); bar(x-45,y,x+55,y+5); void drawmat(char *mat,i nt matsize,i nt x,i nt y,i nt color) /*依次：

10、字模指針、點陣大小、起始坐標(biāo)(x,y)、顏色*/ int i,j,k,n; n=( matsize-1)/8+1; for(j=0;jvmatsize;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,0,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; drawpi

12、llar(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,BLAC

13、K)涂黑重畫 */ bar(3,pillar1.y-PANHOU*19-20,584,412); drawpps();重畫 */ action(data,pillarifrom,pillarito);/* 此處添加動畫函數(shù) */ pillarito.amou nt+;/* 入棧 */ mountt = pillarito.amount;/* 刷新數(shù)量 */ pillarito.pa nmoun tt = data; drawpps();重畫 */ void clearprocess() int i; setfillstyle(SOLID_FILL,BLACK); for(i=0;i=16;i+

14、) bar(545,30+i*10,638,40+i*10); sdelay(1);/動畫延遲 n 個(1/18.2)秒*/ 整數(shù)1代表(1/18.2)秒*/ void sdelay(i nt delay_t) clock_t start_time ; start_time=clock(); while(clock()-start_time)delay_t) ; /*循環(huán)空語句 */ void action(pans pan,pillars fromp,pillars top) /*移動動畫 */ float x1,y1,x2,y2; float p,q,a; int x,y,temp; /*

15、整形變量用與當(dāng)前幀*/ x1 = (float)(fromp.x); y1 = (float)(fromp.y - fromp.amou nt*PANHOU -20); /*PANHOU為盤厚常數(shù)，減20處理，以便避開柱子*/ x2 = (float)(top.x); y2 = (float)(top.y - top.amou nt*PANHOU); q = -sqrt(y1-PAOGAO)/(y2-PAOGAO); 此處注意產(chǎn)生增根 */ if(1-q)/*除數(shù)不為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(pa n,x,y); sdelay(1); clearpa n(pa n,