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

2、中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。值班僧侶按照法則日夜不停地搬運，當搬運完成時世界將在一聲霹靂中毀滅。實驗分析我們假設把該任務交給一個僧人，為了方便敘述，將他編號為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座

3、。他是這樣做的：1. 命令僧人62將62個盤子從A移動到C2. 自己將一個盤子從A座移動到B座3. 再命令僧人62將62個盤子移到B座再進行一次遞歸。如此“層層下放”，直到后來找到第2個僧人，讓他完成將2個盤子從一個座移到另一個座，進行到此，問題就解決了。最后找到第1個僧人，讓他完成將一個盤子從一個座移動到另一個座，至此，全部工作已經(jīng)完成，該煩他問題得到解決。實驗步驟1 主程序流程圖初始化過程繪制初始圖形漢諾塔求解開始輸入盤子數(shù)結束主程序流程圖2 梵塔求解流程圖開始將盤子從A座移到C座n為1？是否遞歸調(diào)用，初始n=n-1盤子數(shù)為n結束梵塔問題遞歸過程流程圖退出一級調(diào)用n=n+1程序代碼#inc

4、lude <stdio.h>#include <graphics.h>#include <time.h>#include <dos.h>#include <math.h>#define PAOGAO 190 /*動畫拋高，數(shù)值越小越高*/#define PANHOU 10/*#define PANAMOUNT 19盤子數(shù)*/ int PANAMOUNT;typedef int pans;typedef struct s_pillar int amount; int x,y; pans pan20; /*存放每個盤的代號*/pillar

5、s;pillars pillar4; /*三個臺柱*/int movecount=0; /*移動計數(shù)*/void drawpillar(pillars p);void init(); /*初始化函數(shù)*/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,cha

6、r two,char three);void sdelay(int delay_t); /*函數(shù)申明*/void finish(); /*完成！*/void main(void) /*主函數(shù)*/ printf("ntplease input n(n<=19): ");/*輸入要演示的盤子數(shù)*/ scanf("%d",&PANAMOUNT); if(PANAMOUNT<1|PANAMOUNT>19) /*越界的話n當19處理*/ PANAMOUNT=19 ; init(); drawpps(); hanoi(PANAMOUNT,&

7、#39;a','b','c'); finish();void init() /* 初始化函數(shù) */ 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+

8、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(S

9、OLID_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

10、,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;j<matsize;j+) for(i=0;i<n;i+) for(k=0;k&l

11、t;8;k+) if(matj*n+i&(0x80>>k) /*測試為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

12、+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<=mount ;j+) drawpan(

13、p.panj,x,y-PANHOU*(j-1); void hanoi(int n,char one,char two,char three) void move(char x,char y); /*聲明*/ if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x,char y) void clearprocess(); /*申明函數(shù)*/ void action(); /*申明移動動畫函數(shù)*/ int ifrom,ito

14、; pans data; int mountf,mountt; char a1; char b1; a0=x;a1='0' b0=y;b1='0' ifrom = x-96; ito = y-96; mountf = pillarifrom.amount; /*數(shù)量*/ mountt = pillarito.amount; data = pillarifrom.panmountf; pillarifrom.amount-; /*出棧*/ sdelay(6); /*暫停屏幕*/ if(movecount>=15) clearprocess();/*清除步驟提

15、示*/ 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,58

16、4,412); drawpps(); /*重畫*/ action(data,pillarifrom,pillarito);/*此處添加動畫函數(shù)*/ pillarito.amount+; /*入棧*/ mountt = pillarito.amount;/*刷新數(shù)量*/ 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);

17、 /*動畫延遲n個(1/18.2)秒*/ 整數(shù)1代表(1/18.2)秒 */void sdelay(int 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; /*整形變量用與當前幀*/ x1 = (float)(fromp.x); y1 = (f

18、loat)(fromp.y - fromp.amount*PANHOU -20); /*PANHOU為盤厚常數(shù),減20處理，以便避開柱子*/ x2 = (float)(top.x); y2 = (float)(top.y - top.amount*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); 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