人工智能(梵塔問題)上課講義

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

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

3、到 B 座的問題，僧人 63 又想：如果能再有一個(gè)僧人 62 能將 62 個(gè)盤子移動(dòng)到另一座，我就能將 63 個(gè)盤子從 A 座移動(dòng)到 B 座。他是這樣做的：1. 命令僧人 62 將 62 個(gè)盤子從 A 移動(dòng)到 C2. 自己將一個(gè)盤子從 A 座移動(dòng)到 B 座3. 再命令僧人 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)步驟 主程序流程圖開始輸入盤子初始化過繪制初始圖漢諾

4、塔求結(jié)束主程序流程圖 梵塔求解流程圖精品資料學(xué)習(xí) 好資料開始盤子數(shù)為 n是n 為 1？否將盤子從 A 座移到遞歸調(diào)用，初始退出一級(jí)調(diào)用結(jié)束梵塔問題遞歸過程流程程序代碼#include <stdio.h>#include <graphics.h>#include <time.h>#include <dos.h>#include <math.h>#define PAOGAO 190 /*動(dòng)畫拋高，數(shù)值越小越高*/#define PANHOU 10/*#define PANAMOUNT 19 盤子數(shù) */int PANAMOUNT;type

5、def int pans;typedef struct s_pillarint amount;int x,y;pans pan20;/*存放每個(gè)盤的代號(hào) */pillars;pillars pillar4;/* 三個(gè)臺(tái)柱 */int movecount=0;/* 移動(dòng)計(jì)數(shù) */精品資料學(xué)習(xí) 好資料void drawpillar(pillars p);void init();/* 初始化函數(shù) */void drawmat(char *mat,int matsize,int x,int y,int color); /*點(diǎn)陳漢字 */void drawpan(pans p,int x,int y);

6、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<=19): ");/* 輸入要演示的盤子數(shù) */scanf("%d",&PANAMOUNT);if

7、(PANAMOUNT<1|PANAMOUNT>19)/*越界的話 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;精品資料學(xué)習(xí)

8、 好資料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);/*柱座標(biāo)記 */settextstyle(0,0,2);outtextxy(105,418,"A");outtextxy(320,418,&

9、quot;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,"Press A

10、NY Key to EXIT !");線上/*字 */zimu();void drawpillar(pillars p)/* 畫柱 */int x,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);精品資料學(xué)習(xí) 好資料void drawmat(char *mat,int matsize,int x,int y,int color)/* 依次：字模指針、點(diǎn)陣大小、起始坐標(biāo)(x,y)、顏色 */int

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

12、WIDTH);setcolor(BLACK);line(x-(5+5*p),y,x+(5+5*p),y);line(x-(5+5*p),y+1,x+(5+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()/* 畫裝盤的臺(tái)柱 */pillars p;int i,j;int x,y,mount;for(i=1;i<=3;i+)p = pillari;x = p.x;y = p.y;mount =

13、p.amount;drawpillar(p);/*畫臺(tái)柱 */精品資料學(xué)習(xí) 好資料for(j=1; j<=mount ;j+)drawpan(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);elsehanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);void move(char x,char y)void cl

14、earprocess(); /*申明函數(shù) */void action();/*申明移動(dòng)動(dòng)畫函數(shù) */int ifrom,ito;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-;/* 出棧 */精品資料/*重畫 *

15、/學(xué)習(xí) 好資料sdelay(6); /*暫停屏幕 */if(movecount>=15) clearprocess();/*清除步驟提示 */movecount = movecount%15+1; /*模 20+1*/setcolor(RED);/*輸出移動(dòng)過程 */settextstyle(TRIPLEX_FONT, HORIZ_DIR, 1);outtextxy(560,30+movecount*10,a);outtextxy(580,30+movecount*10,"->");outtextxy(620,30+movecount*10,b);setfill

16、style(SOLID_FILL,BLACK);/*涂黑 _重畫 */bar(3,pillar1.y-PANHOU*19-20,584,412);drawpps();action(data,pillarifrom,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

17、;i<=16;i+)bar(545,30+i*10,638,40+i*10);sdelay(1);/*動(dòng)畫延遲 n 個(gè)(1/18.2)秒 */精品資料學(xué)習(xí) 好資料整數(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)/* 移動(dòng)動(dòng)畫 */float x1,y1,x2,y2;float p

18、,q,a;int x,y,temp;/* 整形變量用與當(dāng)前幀 */x1 = (float)(fromp.x);y1 = (float)(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);elsea = (x1+x2)/2.0;p = (y2-PAOGAO)/(x2-