數(shù)據(jù)結構課程設計報告(農(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設計一個算法求解農(nóng)夫過河問題，并輸出過河方案；3</p><p><b>　　3 概要設計3</b></p><p>　　3.1 數(shù)據(jù)結構的設計。3</p><p>　　3.1.1農(nóng)夫過河問題的模型化3</p><p>　　3.1.2

3、 算法的設計4</p><p><b>　　4、運行與測試6</b></p><p><b>　　5、總結與心得7</b></p><p><b>　　附錄7</b></p><p><b>　　參考文獻13</b></p><

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

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

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

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

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

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

10、過不安全狀態(tài)。</p><p>　　3.1.2 算法的設計</p><p>　　求農(nóng)夫、狼、白菜和羊的當前狀態(tài)的函數(shù)為每一種狀態(tài)做測試, 狀態(tài)安全則返回0, 否則返回1。安全性判斷函數(shù), 若狀態(tài)安全則返回0</p><p>　　int farmer(int location) //判斷農(nóng)夫位置對0做與運算，還是原來的數(shù)字，用來判斷位置</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>　　借助于位向量和按位運算符, 很容易描述過河動作, 這種問題表示的設計使得程序的實現(xiàn)比較容易。算法的基本思想: 利用隊列moveTo 記錄可到的尚未向前探試的狀態(tài), 數(shù)組元素route [ i] 記錄狀態(tài)i的路徑[ 前一狀態(tài)]

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

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

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

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( );//新的隊列判斷路徑</p><p>　　enQueue_seq(moveTo, 0x00); //初始狀態(tài)為0</p><p>　　for (i = 0

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

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

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

25、t;/p><p><b>　　{ </b></p><p>　　newlocation = location^(0x08|movers);//過岸</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);//記錄路徑并入隊，位置改變</p><p><b>　　4、運行與測試</b></p><p&

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

28、的能力，體會了學以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。</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 //順序隊列類型定義 </p><p><b>　　{ </b></p><p>　　int f, r; //f表示頭，r 表示尾</p><p>　　int q[MAXNUM];//順序隊</p><p>　　}Seq

30、Queue ,*PSeqQueue;</p><p>　　PSeqQueue createEmptyQueue_seq( ) //創(chuàng)建隊列</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 所指是否是空隊列</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) //在隊列中插入一元素 x</p><p><b>　　{</b></p><p>　　if ((paqu->r+1)%MAXNUM==paqu->f) </p>

34、<p>　　cout<<"隊列已滿."<<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) //刪除隊列頭部元素 </p><p><b>　　{</

36、b></p><p>　　if( paqu->f==paqu->r) </p><p>　　cout<<"隊列為空"<<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 ) //對非空隊列,求隊列頭部元素</p><p><b>　　{</b></p><p>　　return (paqu->q[paqu->f]);

38、</p><p><b>　　}</b></p><p>　　int farmer(int location) //判斷農(nóng)夫位置對0做與運算，還是原來的數(shù)字，用來判斷位置</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( );//新的隊列判斷路徑</p><p>　　enQueue_seq(moveTo, 0x00

46、); //初始狀態(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)&&(route[

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

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

49、location & movers)))//判斷農(nóng)夫和要移動的物品是否在同岸</p><p><b>　　{ </b></p><p>　　newlocation = location^(0x08|movers);//過岸</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);//記錄路徑并入隊，位置改變</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<<"過河步驟是 : "<<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)夫帶羊過南岸"; </p><p>　　if(temp[i][2]!=tem

60、p[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[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)夫自己過南岸";</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>