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

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

2、型在問題求解中的重要性；3</p><p>　　2.2設(shè)計(jì)一個(gè)算法求解農(nóng)夫過河問題，并輸出過河方案；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)夫過河問題的模型化3</p><p>　　3.1.2

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

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

6、;</p><p>　　2.1為農(nóng)夫過河問題抽象數(shù)據(jù)模型體會數(shù)據(jù)模型在問題求解中的重要性；</p><p>　　2.2設(shè)計(jì)一個(gè)算法求解農(nóng)夫過河問題，并輸出過河方案；</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)夫過

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

8、題表示: 需要表示問題中的狀態(tài), 農(nóng)夫等位于南P北( 每個(gè)有兩種可能) ?？梢圆捎梦幌蛄? 4 個(gè)二進(jìn)制位的0P1 情況表示狀態(tài), 顯而易見, 共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>　　圖1 系統(tǒng)狀態(tài)轉(zhuǎn)換圖</p><p>　　其中雙向的箭頭表示狀態(tài)可逆, 即農(nóng)夫可以帶</p><p>　　著某種東西過去, 也可以帶著該東西回來。箭頭上的字母表示農(nóng)夫所攜帶的東西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分別表示農(nóng)夫自己、農(nóng)夫攜帶狼、農(nóng)夫攜帶羊、農(nóng)夫攜帶

10、菜過河?，F(xiàn)在的問題轉(zhuǎn)化為: 找一條合法路徑( 相鄰狀態(tài)之間的轉(zhuǎn)移合法) , 從開始狀態(tài)到某個(gè)結(jié)束狀態(tài), 途中不經(jīng)過不安全狀態(tài)。</p><p>　　3.1.2 算法的設(shè)計(jì)</p><p>　　求農(nóng)夫、狼、白菜和羊的當(dāng)前狀態(tài)的函數(shù)為每一種狀態(tài)做測試, 狀態(tài)安全則返回0, 否則返回1。安全性判斷函數(shù), 若狀態(tài)安全則返回0</p><p>　　int farmer(int

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

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

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

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

15、t;/b></p><p>　　if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)) ) </p><p>　　return 0; </p><p>　　if ((goat(location) == wolf(location)) &a

16、mp;& (goat(location) != farmer(location))) </p><p><b>　　return 0;</b></p><p>　　return 1; //其他狀態(tài)是安全的</p><p>　　借助于位向量和按位運(yùn)算符, 很容易描述過河動作, 這種問題表示的設(shè)計(jì)使得程序的實(shí)現(xiàn)比較容易。算法的基本思想: 利

17、用隊(duì)列moveTo 記錄可到的尚未向前探試的狀態(tài), 數(shù)組元素route [ i] 記錄狀態(tài)i的路徑[ 前一狀態(tài)] , - 1 表示尚未訪問。則算法的高級抽象可描速為:</p><p><b>　　{</b></p><p>　　初始狀態(tài)出發(fā)點(diǎn)入隊(duì)列;所有其他點(diǎn)狀態(tài)標(biāo)記為未訪問;</p><p>　　while ( ! isEmptyQueue

18、seq ( moveTo) &&( route[ 15] == - 1) )</p><p><b>　　{</b></p><p>　　從moveTo 取出一個(gè)狀態(tài);試探所有由這個(gè)狀態(tài)出發(fā)可能到達(dá)的狀態(tài);</p><p>　　if( 能到達(dá)的狀態(tài)安全且未訪問過)</p><p><b>　　{

19、</b></p><p><b>　　記錄到它的路徑;</b></p><p><b>　　壓入隊(duì)列;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b&

20、gt;　　}</b></p><p>　　精化上速算法得到問題的具體算法如下:</p><p>　　void farmerProblem( ) </p><p><b>　　{ </b></p><p>　　int movers, i, location, newlocation; </p>&

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

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

23、&(route[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ì)的刪除&

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

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

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

27、<p><b>　　4、運(yùn)行與測試</b></p><p><b>　　5、總結(jié)與心得</b></p><p>　　“紙上得來終覺淺，絕知此事要躬行?！蓖ㄟ^這兩周的課程設(shè)計(jì)，使我對書上的的理論知識有了更深的理解，也使我對于團(tuán)隊(duì)合作有了新的認(rèn)識，意識到團(tuán)隊(duì)的力量。課程設(shè)計(jì)是一個(gè)必須經(jīng)歷的過程，是我們理解書本知識、熟悉所學(xué)專業(yè)的一次很好實(shí)

28、踐。</p><p>　　在這次設(shè)計(jì)過程中，體現(xiàn)出自己單獨(dú)設(shè)計(jì)程序的能力以及綜合運(yùn)用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。</p><p><b>　　附錄</b></p><p>　　#include<iostream.h></p><p&g

29、t;　　#include<stdio.h></p><p>　　#define MAXNUM 20 </p><p>　　typedef struct //順序隊(duì)列類型定義 </p><p><b>　　{ </b></p><p>　　int f, r; //f表示頭，r 表示尾</p>&

30、lt;p>　　int q[MAXNUM];//順序隊(duì)</p><p>　　}SeqQueue ,*PSeqQueue;</p><p>　　PSeqQueue createEmptyQueue_seq( ) //創(chuàng)建隊(duì)列</p><p><b>　　{</b></p><p>　　PSeqQueue paqu =

31、new SeqQueue; </p><p>　　if (paqu == NULL) </p><p>　　cout<<"Out of space!"<<endl; </p><p><b>　　else</b></p><p>　　paqu->f=paqu->r=

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

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

34、>　　if ((paqu->r+1)%MAXNUM==paqu->f) </p><p>　　cout<<"隊(duì)列已滿."<<endl;</p><p><b>　　else </b></p><p><b>　　{</b></p><p>

35、;　　paqu->q[paqu->r]=x;</p><p>　　paqu->r=(paqu->r+1)%MAXNUM;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void deQueue_seq(PSeqQueue

36、paqu) //刪除隊(duì)列頭部元素 </p><p><b>　　{</b></p><p>　　if( paqu->f==paqu->r) </p><p>　　cout<<"隊(duì)列為空"<<endl;</p><p><b>　　else </b&g

37、t;</p><p>　　paqu->f=(paqu->f+1)%MAXNUM; </p><p><b>　　}</b></p><p>　　int frontQueue_seq( PSeqQueue paqu ) //對非空隊(duì)列,求隊(duì)列頭部元素</p><p><b>　　{</b>

38、</p><p>　　return (paqu->q[paqu->f]);</p><p><b>　　}</b></p><p>　　int farmer(int location) //判斷農(nóng)夫位置對0做與運(yùn)算，還是原來的數(shù)字，用來判斷位置</p><p><b>　　{</b>&l

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

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

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

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

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

44、 0;</b></p><p>　　return 1; //其他狀態(tài)是安全的 </p><p><b>　　}</b></p><p>　　void farmerProblem( ) </p><p><b>　　{ </b></p><p>　　int move

45、rs, i, location, newlocation; </p><p>　　int route[16]; //記錄已考慮的狀態(tài)路徑</p><p>　　int print[MAXNUM];</p><p>　　PSeqQueue moveTo; </p><p>　　moveTo = createEmptyQueue_seq( );//

46、新的隊(duì)列判斷路徑</p><p>　　enQueue_seq(moveTo, 0x00); //初始狀態(tài)為0</p><p>　　for (i = 0; i < 16; i++) </p><p>　　route[i] = -1; //-1表示沒有記錄過路徑</p><p>　　route[0]=0; </p><p

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

48、;<p>　　deQueue_seq(moveTo);//已出隊(duì)的刪除</p><p>　　for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分別0001，0010，0100，1000,也就是依次判斷過河的可行性</p><p><b>　　{ </b></p>

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

50、;p>　　if (safe(newlocation) && (route[newlocation] == -1))//判斷是否安全，以及路徑是否可用</p><p><b>　　{</b></p><p>　　route[newlocation] = location; </p><p>　　enQueue_seq(mov

51、eTo, newlocation);//記錄路徑并入隊(duì)，位置改變</p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><

52、;p>　　/* 打印出路徑 */ </p><p>　　if(route[15] != -1)</p><p><b>　　{ </b></p><p>　　cout<<"過河步驟是 : "<<endl; </p><p><b>　　i=0;</b>

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

54、</p><p>　　if (location == 0) </p><p><b>　　break;</b></p><p><b>　　} </b></p><p>　　int num=i-1;</p><p>　　int temp[20][4]; </

55、p><p><b>　　int j;</b></p><p>　　for(i=num;i>=0;i--)</p><p><b>　　{</b></p><p>　　for(j=3;j>=0;j--)</p><p><b>　　{</b><

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

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

58、uot;;</p><p>　　cout<<endl;</p><p><b>　　}*/</b></p><p>　　for(i=1;i<=num;i++)</p><p><b>　　{</b></p><p>　　cout<<"\

59、t\t\tNO . "<<i<<"\t";</p><p>　　if(i%2==1)</p><p><b>　　{</b></p><p>　　if(temp[i][3]!=temp[i-1][3])</p><p>　　cout<<"農(nóng)夫帶羊

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

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

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

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

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

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

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