人工智能梵塔問題

1、-. z.梵塔問題實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康氖煜ず驼莆諉栴}規(guī)約法的原理、實(shí)質(zhì)和規(guī)約過程理解規(guī)約圖的表示方法熟悉并掌握遞歸解決問題的思想實(shí)驗(yàn)原理利用問題規(guī)約法的原理進(jìn)展問題的分析與描述利用遞歸思想進(jìn)展問題的解決實(shí)驗(yàn)條件Window NT/*p/7及以上的操作系統(tǒng)存在512M以上CPU在奔騰II以上實(shí)驗(yàn)容梵塔問題源于印度古老的一個(gè)傳說。相傳開天辟地的神勃拉瑪創(chuàng)造世界時(shí)在印度北部的佛教圣地的圣廟里，安放了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不

2、能放在小的上面。值班僧侶按照法則日夜不停地搬運(yùn)，當(dāng)搬運(yùn)完成時(shí)世界將在一聲霹靂中消滅。實(shí)驗(yàn)分析我們假設(shè)把該任務(wù)交給一個(gè)僧人，為了方便表達(dá)，將他編號為64。僧人自然會(huì)這樣想：假設(shè)有另外一個(gè)僧人能有方法將63個(gè)盤子從一個(gè)座移到另一個(gè)座，則問題就解決了，此時(shí)僧人64只需這樣做：命令僧人63將63個(gè)盤子從A座移到C座自己將最底下的最大的一個(gè)盤子從A座移到C座再命令僧人63將63個(gè)盤子從B座移到C座為了解決將63個(gè)盤子從A座移到B座的問題，僧人63又想：如果能再有一個(gè)僧人62能將62個(gè)盤子移動(dòng)到另一座，我就能將63個(gè)盤子從A座移動(dòng)到B座。他是這樣做的：命令僧人62將62個(gè)盤子從A移動(dòng)到C自己將一個(gè)盤子從A

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

4、AOGAO 190 /*動(dòng)畫拋高，數(shù)值越小越高*/#define PANHOU 10/*#define PANAMOUNT 19盤子數(shù)*/ int PANAMOUNT;typedef int pans;typedef struct s_pillar int amount; int *,y; pans pan20; /*存放每個(gè)盤的代號*/pillars;pillars pillar4; /*三個(gè)臺(tái)柱*/int movecount=0; /*移動(dòng)計(jì)數(shù)*/void drawpillar(pillars p);void init(); /*初始化函數(shù)*/void drawmat(char *mat,

5、int matsize,int *,int y,int color); /* 點(diǎn)漢字 */void drawpan(pans p,int *,int y);void zimu(); /*顯示字幕*/void drawpps(); /*畫裝盤的臺(tái)柱*/void hanoi(); /*主算法*/void hanoi(int n,char one,char two,char three);void sdelay(int delay_t); /*函數(shù)申明*/void finish(); /*完成！*/void main(void) /*主函數(shù)*/ printf(ntplease input n(n=1

6、9): );/*輸入要演示的盤子數(shù)*/ scanf(%d,&PANAMOUNT); if(PANAMOUNT19) /*越界的話n當(dāng)19處理*/ PANAMOUNT=19 ; init(); drawpps(); hanoi(PANAMOUNT,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.* = 105; pillar

7、1.y = 405; for(i=1;i=pillar1.amount;i+) pillar1.pani=pillar1.amount-i+1; pillar2.amount = 0; pillar2.* = 320; pillar2.y = 405; pillar3.amount = 0; pillar3.* = 527; pillar3.y = 405; setcolor(YELLOW); /*柱座標(biāo)記*/ sette*tstyle(0,0,2); outte*t*y(105,418,A); outte*t*y(320,418,B); outte*t*y(527,418,C); setco

8、lor(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); /*黃金線*/ sette*tstyle(0,0,1); outte*t*y(250,PAOGAO-PANHOU-50,Press ANY Key to E*IT !); /*線上字*/ zimu();void drawpillar(p

9、illars p) /*畫柱*/ int *,y,mount; *=p.*; y=p.y; mount=p.amount; setfillstyle(SOLID_FILL,BROWN); bar(*,(y-mount*PANHOU-20),*+5,y); bar(*-45,y,*+55,y+5);void drawmat(char *mat,int matsize,int *,int y,int color)/*依次：字模指針、點(diǎn)陣大小、起始坐標(biāo)(*,y)、顏色*/int i,j,k,n; n=(matsize-1)/8+1; for(j=0;jmatsize;j+) for(i=0;in;i

10、+) for(k=0;kk) /*測試為1的位則顯示*/ putpi*el(*+i*8+k,y+j,color);void drawpan(pans p,int *,int y) setfillstyle(SOLID_FILL,LIGHTGRAY); bar(*-(5+5*p),y-PANHOU+1,*+(5+5*p),y); setlinestyle(SOLID_LINE,0,NORM_WIDTH); setcolor(BLACK); line(*-(5+5*p),y,*+(5+5*p),y); line(*-(5+5*p),y+1,*+(5+5*p),y+1);void clearpan(

11、pans p,int *,int y) setfillstyle(SOLID_FILL,BLACK); bar(*-(5+5*p),y-PANHOU,*+(5+5*p),y);void drawpps() /*畫裝盤的臺(tái)柱*/ pillars p; int i,j; int *,y,mount; for(i=1;i=3;i+) p = pillari; * = p.*; y = p.y; mount = p.amount; drawpillar(p); /*畫臺(tái)柱*/ for(j=1; j=15) clearprocess();/*去除步驟提示*/ movecount = movecount%

12、15+1; /*模20+1*/ setcolor(RED); /*輸出移動(dòng)過程*/ sette*tstyle(TRIPLE*_FONT, HORIZ_DIR, 1); outte*t*y(560,30+movecount*10,a); outte*t*y(580,30+movecount*10,-); outte*t*y(620,30+movecount*10,b); setfillstyle(SOLID_FILL,BLACK);/*涂黑_重畫*/ bar(3,pillar1.y-PANHOU*19-20,584,412); drawpps(); /*重畫*/ action(data,pill

13、arifrom,pillarito);/*此處添加動(dòng)畫函數(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); /*動(dòng)畫延遲n個(gè)(1/18.2)秒*/ 整數(shù)1代表(1/18.2)秒 */void sde

14、lay(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) /*移動(dòng)動(dòng)畫*/ float *1,y1,*2,y2; float p,q,a; int *,y,temp; /*整形變量用與當(dāng)前幀*/ *1 = (float)(fromp.*); y1 = (float)(fromp.y - fromp.amount*PANHOU -20); /*PANHOU

15、為盤厚常數(shù),減20處理，以便避開柱子*/ *2 = (float)(top.*); y2 = (float)(top.y - top.amount*PANHOU); q = -sqrt(y1-PAOGAO)/(y2-PAOGAO); /*此處注意產(chǎn)生增根*/ if(1-q) /*除數(shù)不為0*/ a = (*1 - *2*q)/(1-q); else a = (*1+*2)/2.0; p = (y2-PAOGAO)/(*2-a)/(*2-a);/*除以平方*/ if(*1 = *2) for(*=floor(*1+0.5); *floor(*2+0.5); *=*- 7 ) if(kbhit() e*it(); /*用戶按ESC則退出*/ y = floo