數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(農(nóng)夫過(guò)河)

1、<p><b>　　目錄</b></p><p><b>　　引言2</b></p><p><b>　　1 問(wèn)題描述3</b></p><p><b>　　基本要求3</b></p><p>　　2.1為農(nóng)夫過(guò)河問(wèn)題抽象數(shù)據(jù)模型體會(huì)數(shù)據(jù)模

2、型在問(wèn)題求解中的重要性；3</p><p>　　2.2設(shè)計(jì)一個(gè)算法求解農(nóng)夫過(guò)河問(wèn)題，并輸出過(guò)河方案；3</p><p><b>　　3 概要設(shè)計(jì)3</b></p><p>　　3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。3</p><p>　　3.1.1農(nóng)夫過(guò)河問(wèn)題的模型化3</p><p>　　3.1.2

3、 算法的設(shè)計(jì)4</p><p><b>　　4、運(yùn)行與測(cè)試6</b></p><p><b>　　5、總結(jié)與心得7</b></p><p><b>　　附錄7</b></p><p><b>　　參考文獻(xiàn)13</b></p><

4、;p><b>　　引言</b></p><p>　　所謂農(nóng)夫過(guò)河問(wèn)題是指農(nóng)夫帶一只狼、一只羊和一棵白菜在河南岸, 需要安全運(yùn)到北岸。一條小船只能容下他和一件物品, 只有農(nóng)夫能撐船。問(wèn)農(nóng)夫怎么能安全過(guò)河, 當(dāng)然狼吃羊, 羊吃白菜, 農(nóng)夫不能將這兩種或三種物品單獨(dú)放在河的一側(cè), 因?yàn)闆](méi)有農(nóng)夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 這類問(wèn)題的實(shí)質(zhì)是系統(tǒng)的狀態(tài)問(wèn)題, 要尋求的是從初始狀態(tài)經(jīng)

5、一系列的安全狀態(tài)到達(dá)系統(tǒng)的終止?fàn)顟B(tài)的一條路徑。</p><p><b>　　1 問(wèn)題描述</b></p><p>　　一個(gè)農(nóng)夫帶一只狼、一棵白菜和一只羊要從一條河的南岸過(guò)到北岸，農(nóng)夫每次只能帶一樣?xùn)|西過(guò)河，但是任意時(shí)刻如果農(nóng)夫不在場(chǎng)時(shí)，狼要吃羊、羊要吃白菜，請(qǐng)為農(nóng)夫設(shè)計(jì)過(guò)河方案。</p><p><b>　　基本要求</b>

6、;</p><p>　　2.1為農(nóng)夫過(guò)河問(wèn)題抽象數(shù)據(jù)模型體會(huì)數(shù)據(jù)模型在問(wèn)題求解中的重要性；</p><p>　　2.2設(shè)計(jì)一個(gè)算法求解農(nóng)夫過(guò)河問(wèn)題，并輸出過(guò)河方案；</p><p><b>　　3 概要設(shè)計(jì)</b></p><p>　　3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。</p><p>　　3.1.1農(nóng)夫過(guò)

7、河問(wèn)題的模型化</p><p>　　分析這類問(wèn)題會(huì)發(fā)現(xiàn)以下特征:</p><p>　　有一組狀態(tài)( 如農(nóng)夫和羊在南, 狼和白菜在北) ; 從一個(gè)狀態(tài)可合法地轉(zhuǎn)到另外幾個(gè)狀態(tài)( 如農(nóng)夫自己過(guò)河或農(nóng)夫帶著羊過(guò)河) ; 有些狀態(tài)不安全( 如農(nóng)夫在北, 其他東西在南) ; 有一個(gè)初始狀態(tài)( 都在南) ; 結(jié)束狀態(tài)集( 這里只有一個(gè), 都在北) 。</p><p>　　問(wèn)

8、題表示: 需要表示問(wèn)題中的狀態(tài), 農(nóng)夫等位于南P北( 每個(gè)有兩種可能) ?？梢圆捎梦幌蛄? 4 個(gè)二進(jìn)制位的0P1 情況表示狀態(tài), 顯而易見(jiàn), 共24= 16種可能狀態(tài)。從高位到低位分別表示農(nóng)夫、狼、白菜和羊。0000( 整數(shù)0) 表示都在南岸, 目標(biāo)狀態(tài)1111( 即整數(shù)15) 表示都到了北岸。有些狀態(tài)0011,0101, 0111, 0001, 1100, 1001 是不允許出現(xiàn)的, 因?yàn)檫@些狀態(tài)是不安全狀態(tài)。根據(jù)上述條件可以畫出系

9、統(tǒng)的狀態(tài)圖如圖1 所示。</p><p>　　其中雙向的箭頭表示狀態(tài)可逆, 即農(nóng)夫可以帶著某種東西過(guò)去, 也可以帶著該東西回來(lái)。箭頭上的字母表示農(nóng)夫所攜帶的東西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分別表示農(nóng)夫自己、農(nóng)夫攜帶狼、農(nóng)夫攜帶羊、農(nóng)夫攜帶菜過(guò)河。現(xiàn)在的問(wèn)題轉(zhuǎn)化為: 找一條合法路徑( 相鄰狀態(tài)之間的轉(zhuǎn)移合法) , 從開(kāi)始狀態(tài)到某個(gè)結(jié)束狀態(tài), 途中不經(jīng)

10、過(guò)不安全狀態(tài)。</p><p>　　3.1.2 算法的設(shè)計(jì)</p><p>　　求農(nóng)夫、狼、白菜和羊的當(dāng)前狀態(tài)的函數(shù)為每一種狀態(tài)做測(cè)試, 狀態(tài)安全則返回0, 否則返回1。安全性判斷函數(shù), 若狀態(tài)安全則返回0</p><p>　　int farmer(int location) //判斷農(nóng)夫位置對(duì)0做與運(yùn)算，還是原來(lái)的數(shù)字，用來(lái)判斷位置</p><

11、p><b>　　{</b></p><p>　　return 0 != (location & 0x08);</p><p><b>　　} </b></p><p>　　int wolf(int location) //判斷狼位置</p><p><b>　　{ </

12、b></p><p>　　return 0 != (location & 0x04);</p><p><b>　　}</b></p><p>　　int cabbage(int location) //判斷白菜位置 </p><p><b>　　{ </b></p>&

13、lt;p>　　return 0 != (location & 0x02);</p><p><b>　　} </b></p><p>　　int goat(int location) //判斷羊的位置</p><p><b>　　{</b></p><p>　　return 0 !=(

14、location & 0x01);</p><p><b>　　} </b></p><p>　　int safe(int location) // 若狀態(tài)安全則返回 true </p><p><b>　　{ </b></p><p>　　if ((goat(location) == ca

15、bbage(location)) && (goat(location) != farmer(location)) ) </p><p>　　return 0; </p><p>　　if ((goat(location) == wolf(location)) && (goat(location) != farmer(location))) </p>

16、;<p><b>　　return 0;</b></p><p>　　return 1; //其他狀態(tài)是安全的</p><p>　　借助于位向量和按位運(yùn)算符, 很容易描述過(guò)河動(dòng)作, 這種問(wèn)題表示的設(shè)計(jì)使得程序的實(shí)現(xiàn)比較容易。算法的基本思想: 利用隊(duì)列moveTo 記錄可到的尚未向前探試的狀態(tài), 數(shù)組元素route [ i] 記錄狀態(tài)i的路徑[ 前一狀態(tài)]

17、 , - 1 表示尚未訪問(wèn)。則算法的高級(jí)抽象可描速為:</p><p><b>　　{</b></p><p>　　初始狀態(tài)出發(fā)點(diǎn)入隊(duì)列;所有其他點(diǎn)狀態(tài)標(biāo)記為未訪問(wèn);</p><p>　　while ( ! isEmptyQueue seq ( moveTo) &&( route[ 15] == - 1) )</p>

18、<p><b>　　{</b></p><p>　　從moveTo 取出一個(gè)狀態(tài);試探所有由這個(gè)狀態(tài)出發(fā)可能到達(dá)的狀態(tài);</p><p>　　if( 能到達(dá)的狀態(tài)安全且未訪問(wèn)過(guò))</p><p><b>　　{</b></p><p><b>　　記錄到它的路徑;</b

19、></p><p><b>　　壓入隊(duì)列;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　精化上速算法得到問(wèn)題的具體算法如下

20、:</p><p>　　void farmerProblem( ) </p><p><b>　　{ </b></p><p>　　int movers, i, location, newlocation; </p><p>　　int route[16]; //記錄已考慮的狀態(tài)路徑</p><p&g

21、t;　　int print[MAXNUM];</p><p>　　PSeqQueue moveTo; </p><p>　　moveTo = createEmptyQueue_seq( );//新的隊(duì)列判斷路徑</p><p>　　enQueue_seq(moveTo, 0x00); //初始狀態(tài)為0</p><p>　　for (i = 0

22、; i < 16; i++) </p><p>　　route[i] = -1; //-1表示沒(méi)有記錄過(guò)路徑</p><p>　　route[0]=0; </p><p>　　while (!isEmptyQueue_seq(moveTo)&&(route[15]== -1))//隊(duì)列不為空，路徑未滿時(shí)循環(huán)</p><p&g

23、t;<b>　　{</b></p><p>　　location = frontQueue_seq(moveTo); //從隊(duì)頭出隊(duì)，location表示位置，0為北岸，1為南岸</p><p>　　deQueue_seq(moveTo);//已出隊(duì)的刪除</p><p>　　for (movers = 1; movers <= 8; m

24、overs<<= 1) //向左移位，movers分別0001，0010，0100，1000,也就是依次判斷過(guò)河的可行性</p><p><b>　　{ </b></p><p>　　if ((0 != (location & 0x08)) == (0 != (location & movers)))//判斷農(nóng)夫和要移動(dòng)的物品是否在同岸&l

25、t;/p><p><b>　　{ </b></p><p>　　newlocation = location^(0x08|movers);//過(guò)岸</p><p>　　if (safe(newlocation) && (route[newlocation] == -1))//判斷是否安全，以及路徑是否可用</p>&l

26、t;p><b>　　{</b></p><p>　　route[newlocation] = location; </p><p>　　enQueue_seq(moveTo, newlocation);//記錄路徑并入隊(duì)，位置改變</p><p><b>　　4、運(yùn)行與測(cè)試</b></p><p&

27、gt;<b>　　5、總結(jié)與心得</b></p><p>　　“紙上得來(lái)終覺(jué)淺，絕知此事要躬行?！蓖ㄟ^(guò)這兩周的課程設(shè)計(jì)，使我對(duì)書上的的理論知識(shí)有了更深的理解，也使我對(duì)于團(tuán)隊(duì)合作有了新的認(rèn)識(shí)，意識(shí)到團(tuán)隊(duì)的力量。課程設(shè)計(jì)是一個(gè)必須經(jīng)歷的過(guò)程，是我們理解書本知識(shí)、熟悉所學(xué)專業(yè)的一次很好實(shí)踐。</p><p>　　在這次設(shè)計(jì)過(guò)程中，體現(xiàn)出自己?jiǎn)为?dú)設(shè)計(jì)程序的能力以及綜合運(yùn)用知識(shí)

28、的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。</p><p><b>　　附錄</b></p><p>　　#include<iostream.h></p><p>　　#include<stdio.h></p><p>　　#defin

29、e MAXNUM 20 </p><p>　　typedef struct //順序隊(duì)列類型定義 </p><p><b>　　{ </b></p><p>　　int f, r; //f表示頭，r 表示尾</p><p>　　int q[MAXNUM];//順序隊(duì)</p><p>　　}Seq

30、Queue ,*PSeqQueue;</p><p>　　PSeqQueue createEmptyQueue_seq( ) //創(chuàng)建隊(duì)列</p><p><b>　　{</b></p><p>　　PSeqQueue paqu = new SeqQueue; </p><p>　　if (paqu == NULL) &

31、lt;/p><p>　　cout<<"Out of space!"<<endl; </p><p><b>　　else</b></p><p>　　paqu->f=paqu->r=0; </p><p>　　return (paqu);</p><

32、;p><b>　　} </b></p><p>　　int isEmptyQueue_seq( PSeqQueue paqu ) //判斷 paqu 所指是否是空隊(duì)列</p><p><b>　　{ </b></p><p>　　return paqu->f==paqu->r;</p>&l

33、t;p><b>　　} </b></p><p>　　void enQueue_seq(PSeqQueue paqu,int x) //在隊(duì)列中插入一元素 x</p><p><b>　　{</b></p><p>　　if ((paqu->r+1)%MAXNUM==paqu->f) </p>

34、<p>　　cout<<"隊(duì)列已滿."<<endl;</p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　paqu->q[paqu->r]=x;</p><p>　　paqu

35、->r=(paqu->r+1)%MAXNUM;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void deQueue_seq(PSeqQueue paqu) //刪除隊(duì)列頭部元素 </p><p><b>　　{</

36、b></p><p>　　if( paqu->f==paqu->r) </p><p>　　cout<<"隊(duì)列為空"<<endl;</p><p><b>　　else </b></p><p>　　paqu->f=(paqu->f+1)%MAXN

37、UM; </p><p><b>　　}</b></p><p>　　int frontQueue_seq( PSeqQueue paqu ) //對(duì)非空隊(duì)列,求隊(duì)列頭部元素</p><p><b>　　{</b></p><p>　　return (paqu->q[paqu->f]);

38、</p><p><b>　　}</b></p><p>　　int farmer(int location) //判斷農(nóng)夫位置對(duì)0做與運(yùn)算，還是原來(lái)的數(shù)字，用來(lái)判斷位置</p><p><b>　　{</b></p><p>　　return 0 != (location & 0x08);

39、</p><p><b>　　} </b></p><p>　　int wolf(int location) //判斷狼位置</p><p><b>　　{ </b></p><p>　　return 0 != (location & 0x04);</p><p>&

40、lt;b>　　}</b></p><p>　　int cabbage(int location) //判斷白菜位置 </p><p><b>　　{ </b></p><p>　　return 0 != (location & 0x02);</p><p><b>　　} </b

41、></p><p>　　int goat(int location) //判斷羊的位置</p><p><b>　　{</b></p><p>　　return 0 !=(location & 0x01);</p><p><b>　　} </b></p><p&g

42、t;　　int safe(int location) // 若狀態(tài)安全則返回 true </p><p><b>　　{ </b></p><p>　　if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)) ) </p><p

43、>　　return 0; </p><p>　　if ((goat(location) == wolf(location)) && (goat(location) != farmer(location))) </p><p><b>　　return 0;</b></p><p>　　return 1; //其他狀態(tài)是安全

44、的 </p><p><b>　　}</b></p><p>　　void farmerProblem( ) </p><p><b>　　{ </b></p><p>　　int movers, i, location, newlocation; </p><p>　　in

45、t route[16]; //記錄已考慮的狀態(tài)路徑</p><p>　　int print[MAXNUM];</p><p>　　PSeqQueue moveTo; </p><p>　　moveTo = createEmptyQueue_seq( );//新的隊(duì)列判斷路徑</p><p>　　enQueue_seq(moveTo, 0x00

46、); //初始狀態(tài)為0</p><p>　　for (i = 0; i < 16; i++) </p><p>　　route[i] = -1; //-1表示沒(méi)有記錄過(guò)路徑</p><p>　　route[0]=0; </p><p>　　while (!isEmptyQueue_seq(moveTo)&&(route[

47、15]== -1))//隊(duì)列不為空，路徑未滿時(shí)循環(huán)</p><p><b>　　{</b></p><p>　　location = frontQueue_seq(moveTo); //從隊(duì)頭出隊(duì)，location表示位置，0為北岸，1為南岸</p><p>　　deQueue_seq(moveTo);//已出隊(duì)的刪除</p>&

48、lt;p>　　for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分別0001，0010，0100，1000,也就是依次判斷過(guò)河的可行性</p><p><b>　　{ </b></p><p>　　if ((0 != (location & 0x08)) == (0 != (

49、location & movers)))//判斷農(nóng)夫和要移動(dòng)的物品是否在同岸</p><p><b>　　{ </b></p><p>　　newlocation = location^(0x08|movers);//過(guò)岸</p><p>　　if (safe(newlocation) && (route[newloca

50、tion] == -1))//判斷是否安全，以及路徑是否可用</p><p><b>　　{</b></p><p>　　route[newlocation] = location; </p><p>　　enQueue_seq(moveTo, newlocation);//記錄路徑并入隊(duì)，位置改變</p><p>&l

51、t;b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/* 打印出路徑 */ </p><p>　　if(route[15]

52、 != -1)</p><p><b>　　{ </b></p><p>　　cout<<"過(guò)河步驟是 : "<<endl; </p><p><b>　　i=0;</b></p><p>　　for(location = 15; location >

53、;= 0; location = route[location]) </p><p><b>　　{ </b></p><p>　　print[i]=location;</p><p><b>　　i++;</b></p><p>　　if (location == 0) </p>&

54、lt;p><b>　　break;</b></p><p><b>　　} </b></p><p>　　int num=i-1;</p><p>　　int temp[20][4]; </p><p><b>　　int j;</b></p>

55、<p>　　for(i=num;i>=0;i--)</p><p><b>　　{</b></p><p>　　for(j=3;j>=0;j--)</p><p><b>　　{</b></p><p>　　temp[num-i][j]=print[i]%2;</p>

56、;<p>　　print[i]/=2;</p><p>　　temp[0][j]=0;</p><p>　　temp[num+1][j]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/* for(

57、i=0;i<=num;i++)</p><p><b>　　{</b></p><p>　　for(j=0;j<4;j++)</p><p>　　cout<<temp[i][j]<<" ";</p><p>　　cout<<endl;</p>

58、<p><b>　　}*/</b></p><p>　　for(i=1;i<=num;i++)</p><p><b>　　{</b></p><p>　　cout<<"\t\t\tNO . "<<i<<"\t";</p&

59、gt;<p>　　if(i%2==1)</p><p><b>　　{</b></p><p>　　if(temp[i][3]!=temp[i-1][3])</p><p>　　cout<<"農(nóng)夫帶羊過(guò)南岸"; </p><p>　　if(temp[i][2]!=tem

60、p[i-1][2])</p><p>　　cout<<"農(nóng)夫帶白菜過(guò)南岸";</p><p>　　if(temp[i][1]!=temp[i-1][1])</p><p>　　cout<<"農(nóng)夫帶狼過(guò)南岸";</p><p>　　if(temp[i][3]==temp[i-1]

61、[3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])</p><p>　　cout<<"農(nóng)夫自己過(guò)南岸";</p><p><b>　　}</b></p><p>　　else if(i%2==0)</p>

62、<p><b>　　{</b></p><p>　　if(temp[i][3]!=temp[i-1][3])</p><p>　　cout<<"農(nóng)夫帶羊回北岸"; </p><p>　　if(temp[i][2]!=temp[i-1][2])</p><p>　　cout&

63、lt;<"農(nóng)夫帶白菜回北岸";</p><p>　　if(temp[i][1]!=temp[i-1][1])</p><p>　　cout<<"農(nóng)夫帶狼回北岸";</p><p>　　if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&

64、amp;&temp[i][1]==temp[i-1][1])</p><p>　　cout<<"農(nóng)夫自己回北岸";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></

65、p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　cout<<"No solution."<<endl; </p><p><b>　　}</b></p><p>

66、;　　int main() /*主函數(shù)*/ </p><p><b>　　{</b></p><p>　　farmerProblem(); </p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>