數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)——農(nóng)夫過河

1、農(nóng)夫過河問題項(xiàng)目實(shí)訓(xùn)農(nóng)夫過河問題項(xiàng)目實(shí)訓(xùn)一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問題是他只有一條船，船小到只能容下他和一件物品，當(dāng)然，船只有農(nóng)夫能撐。另外，因?yàn)槔悄艹匝?，而羊愛吃白菜，所以農(nóng)夫不能留下羊和狼或者羊和白菜單獨(dú)在河的一邊，自己離開。好在狼屬于食肉動物，它不吃白菜。請問農(nóng)夫該采取什么方案，才能將所有的東西安全運(yùn)過河呢？一、算法與數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：要模擬農(nóng)夫過河的問題，用四位二進(jìn)制數(shù)順序分別

2、表示農(nóng)夫、狼、白菜和羊的位置。用0表示農(nóng)夫和或者某種東西在河的南岸，1表示在河的北岸。則問題的初始狀態(tài)是整數(shù)（其二進(jìn)制表示為0000）；而問題的終結(jié)狀態(tài)是整數(shù)15（其二進(jìn)制表示為1111）。用整數(shù)location表示用上述方法描述的狀態(tài)，函數(shù)返回值為真（1）表示所考察的人或物在河的北岸，否則在南岸。二、算法的精化：用一個整數(shù)隊(duì)列moveTo，把搜索過程中每一步所有可能達(dá)到的狀態(tài)都保存起來。隊(duì)列中每一個元素表示一個可以安全到達(dá)的中間狀態(tài)。

3、另外，用一個整數(shù)數(shù)組route，用于記錄已被訪問過的各個狀態(tài)，以及已被發(fā)現(xiàn)的能夠到達(dá)這些狀態(tài)的前驅(qū)狀態(tài)。route數(shù)組只需要使用16個元素。Route的每一個元素初始化值均設(shè)置為1，每當(dāng)在隊(duì)列加入一個新狀態(tài)時，就把route中以該狀態(tài)坐下標(biāo)的元素的值改為達(dá)到這個狀態(tài)的前一狀態(tài)的下標(biāo)值。所以，數(shù)組的第i個元素，不僅記錄狀態(tài)i是否已被訪問過，同時對已被訪問過的狀態(tài)，還保存了這個狀態(tài)的前驅(qū)狀態(tài)下標(biāo)。算法結(jié)束后，可以利用route數(shù)組元素的值生

4、成一個正確的狀態(tài)路徑。三、程序的實(shí)現(xiàn)：程序代碼如下:#include#include#defineMAXNUM20typedefintDataTypestructSeqQueue順序隊(duì)列類型定義intfrDataTypeq[MAXNUM]typedefstructSeqQueuePSeqQueue順序隊(duì)列類型的指針類型PSeqQueuecreateEmptyQueue_seq(void)intwolf(intlocation)判斷狼位置

5、return0!=(locationintcabbage(intlocation)判斷白菜位置return0!=(locationintgoat(intlocation)判斷羊的位置return0!=(locationintsafe(intlocation)若狀態(tài)安全則返回trueif((goat(location)==cabbage(location))if((goat(location)==wolf(location))return

6、1其他狀態(tài)是安全的voidfarmerProblem()intmoversilocationnewlocationintroute[16]記錄已考慮的狀態(tài)路徑PSeqQueuemoveTomoveTo=createEmptyQueue_seq()enQueue_seq(moveTo0x00)f(i=0i16i)route[i]=1route[0]=0while(!isEmptyQueue_seq(moveTo)deQueue_seq(m