農(nóng)夫過河99602

1、姓名:劉運(yùn)可學(xué)號(hào):3109001160班級(jí):09電子(1)班上機(jī)實(shí)驗(yàn)報(bào)告上機(jī)實(shí)驗(yàn)報(bào)告農(nóng)夫過河問題:一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問題是他只有一條船，船小到只能容下他和一件物品，當(dāng)然，船只有農(nóng)夫能撐。另外，因?yàn)槔悄艹匝?，而羊愛吃白菜，所以農(nóng)夫不能留下羊和狼或者羊和白菜單獨(dú)在河的一邊，自己離開。好在狼屬于食肉動(dòng)物，它不吃白菜。請(qǐng)問農(nóng)夫該采取什么方案，才能將所有的東西安全運(yùn)過河呢？一、算法與數(shù)

2、據(jù)結(jié)構(gòu)的設(shè)計(jì)：要模擬農(nóng)夫過河的問題，用四位二進(jìn)制數(shù)順序分別表示農(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）表示所考察的人或物在河的北岸，否則在南岸。二、算法的精化：用一個(gè)整數(shù)隊(duì)列moveTo，把搜索過程中每一步所有可能達(dá)到的狀態(tài)都

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

4、前驅(qū)狀態(tài)下標(biāo)。算法結(jié)束后，可以利用route數(shù)組元素的值生成一個(gè)正確的狀態(tài)路徑。三、程序的實(shí)現(xiàn)：程序代碼如下:#include#include#defineMAXNUM20typedefintDataTypestructSeqQueue順序隊(duì)列類型定義intfrDataTypeq[MAXNUM]typedefstructSeqQueuePSeqQueue順序隊(duì)列類型的指針類型return0!=(locationintwolf(intlo

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

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