農(nóng)夫過(guò)河c語(yǔ)言詳細(xì)

本文格式為Word版，下載可任意編輯——農(nóng)夫過(guò)河c語(yǔ)言詳細(xì)一、問(wèn)題需求分析

一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問(wèn)題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。另外，由于狼能吃羊，而羊愛(ài)吃白菜，所以農(nóng)夫不能留下羊和白菜或者狼和羊單獨(dú)在河的一邊，自己離開(kāi)。請(qǐng)問(wèn)農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過(guò)河呢？二、算法選擇

求解這個(gè)問(wèn)題的最簡(jiǎn)單的方法是一步一步進(jìn)行試探，每一步都探尋所有可能的選擇，對(duì)前一步適合的選擇再考慮下一步的各種方案。

用計(jì)算機(jī)實(shí)現(xiàn)上述求解的探尋過(guò)程可以采用兩種不同的策略：一種是廣度優(yōu)先(breadth_first)探尋，另一種是深度優(yōu)先(depth_first)。廣度優(yōu)先：

u廣度優(yōu)先的含義就是在探尋過(guò)程中總是首先探尋下面一步的所有可能狀態(tài)，然后再進(jìn)一步考慮更后面的各種狀況。

u要實(shí)現(xiàn)廣度優(yōu)先探尋，一般都采用隊(duì)列作為輔助結(jié)構(gòu)。把下一步所有可能達(dá)到的狀態(tài)都列舉出來(lái)，放在這個(gè)隊(duì)列中，然后順序取出來(lái)分別進(jìn)行處理，處理過(guò)程中把再下一步的狀態(tài)放在隊(duì)列里……。

u由于隊(duì)列的操作遵循先進(jìn)先出的原則，在這個(gè)處理過(guò)程中，只有在前一步的所有狀況都處理完后，才能開(kāi)始后面一步各狀況的處理。三、算法的精化

要模擬農(nóng)夫過(guò)河問(wèn)題，首先需要選擇一個(gè)對(duì)問(wèn)題中每個(gè)角色的位置進(jìn)行描述的方法。一個(gè)很便利的方法是用四位二進(jìn)制數(shù)順序分別表示農(nóng)夫、狼、白菜和羊的位置。例如用0表示農(nóng)夫或者某東西在河的南岸，1表示在河的北岸。因此整數(shù)5(其二進(jìn)制表示為0101)表示農(nóng)夫和白菜在河的南岸，而狼和羊在北岸。

四、算法的實(shí)現(xiàn)

完成了上面的準(zhǔn)備工作，現(xiàn)在的問(wèn)題變成：

從初始狀態(tài)二進(jìn)制0000(全部在河的南岸)出發(fā)，尋覓一種全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，它以二進(jìn)制1111(全部到達(dá)河的北岸)為最終目標(biāo)，并且在序列中的每一個(gè)狀態(tài)都可以從前一狀態(tài)通過(guò)農(nóng)夫（可以帶一樣?xùn)|西）劃船過(guò)河的動(dòng)作到達(dá)。

為避免不必要的瞎費(fèi)功夫，要求在序列中不應(yīng)當(dāng)出現(xiàn)重復(fù)的狀態(tài)。為了實(shí)現(xiàn)廣度優(yōu)先探尋，算法中需要使用了一個(gè)整數(shù)隊(duì)列moveTo，它的每個(gè)元素表示一個(gè)可以安全到達(dá)的中間狀態(tài)。另外還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄已被訪問(wèn)過(guò)的各個(gè)狀態(tài)，以及已被發(fā)現(xiàn)的能夠到達(dá)當(dāng)前這個(gè)狀態(tài)的路徑。

由于在這個(gè)問(wèn)題的解決過(guò)程中需要列舉的所有狀態(tài)(二進(jìn)制0000~1111)一共16種，所以可以構(gòu)造一個(gè)包含16個(gè)元素的整數(shù)順序表來(lái)滿足以上的要求。用順序表的第i個(gè)元素記錄

狀態(tài)i是否已被訪問(wèn)過(guò)，若已被訪問(wèn)過(guò)則在這個(gè)順序表元素中記入前驅(qū)狀態(tài)值，算法中把這個(gè)順序表叫做route。route的每個(gè)分量初始化值均為-1，每當(dāng)我們?cè)陉?duì)列中參與一個(gè)新?tīng)顟B(tài)時(shí)，就把順序表中以該狀態(tài)作下標(biāo)的元素的值改為達(dá)到這個(gè)狀態(tài)的路徑上前一狀態(tài)的下標(biāo)值。route的一個(gè)元素具有非負(fù)值表示這個(gè)狀態(tài)已訪問(wèn)過(guò)，或是正被考慮。最終我們可以利用route順序表元素的值建立起正確的狀態(tài)路徑。五、程序代碼//farmerProblem.c//用隊(duì)列解決農(nóng)夫過(guò)河問(wèn)題

#include#includetypedefintDataType;

//順序隊(duì)列：類型和界面函數(shù)聲明

structSeueue{

//順序隊(duì)列類型定義

intMAXNUM;//隊(duì)列中最大元素個(gè)數(shù)intf,r;DataType*q;};

typedefstructSeueue*PSeueue;//順序隊(duì)列類型的指針類型

PSeueuecreateEmptyQueue_seq(intm){

//創(chuàng)立一個(gè)空隊(duì)列

PSeueuequeue=(PSeueue)malloc(sizeof(structSeueue));if(queue!=NULL){

queue->q=(DataType*)malloc(sizeof(DataType)*m);if(queue->q){

queue->MAXNUM=m;

queue->f=0;queue->r=0;return(queue);}else

free(queue);}

printf(\存儲(chǔ)分派失敗returnNULL;}

intisEmptyQueue_seq(PSeueuequeue){

//判斷隊(duì)列是否為空

return(queue->f==queue->r);}

voidenQueue_seq(PSeueuequeue,DataTypex)//在隊(duì)尾插入元素x{

if((queue->r+1)%queue->MAXNUM==queue->f)printf(\else{

queue->q[queue->r]=x;

queue->r=(queue->r+1)%queue->MAXNUM;}}

voiddeQueue_seq(PSeueuequeue)//刪除隊(duì)列頭部元素{

if(queue->f==queue->r)printf(\else

queue->f=(queue->f+1)%queue->MAXNUM;}

DataTypefrontQueue_seq(PSeueuequeue){

if(queue->f==queue->r)printf(\else

return(queue->q[queue->f]);}

//個(gè)體狀態(tài)判斷函數(shù)intfarmer(intlocation){

//判斷農(nóng)夫的位置

return(0!=(location}

intwolf(intlocation){

//判斷狼的位置

return(0!=(location}

intcabbage(intlocation){

//判斷白菜的位置

return(0!=(location}

intgoat(intlocation){

//判斷羊的位置

return(0!=(location}

//安全狀態(tài)的判斷函數(shù)intsafe(intlocation){

//若狀態(tài)安全則返回true

if((goat(location)==cabbage(location))//羊吃白菜

if((goat(location)==wolf(location))//狼吃羊

return(1);//其他狀態(tài)是安全的}main(){

inti,movers,location,newlocation;introute[16];//用于記錄已考慮的狀態(tài)路徑

PSeueuemoveTo;//用于記錄可以安全到達(dá)的中間狀態(tài)moveTo=createEmptyQueue_seq(20);//創(chuàng)立空隊(duì)列enQueue_seq(moveTo,0x00);//初始狀態(tài)進(jìn)隊(duì)列for(i=0;i

{

newlocation=location^(0x08|movers);//計(jì)算新?tīng)顟B(tài)if(safe(newlocation)//記錄新?tīng)顟B(tài)的前驅(qū)enQueue_seq(moveTo,newlocation);//新?tīng)顟B(tài)入隊(duì)}}}

//打印出路徑if(route[15]!=-1)//到達(dá)最終狀態(tài){

printf(\

for(location=15;location>=0;location=route[location]){

printf(\if(location==0)exit(0);}}else

printf(\//問(wèn)題無(wú)解}

六、測(cè)試結(jié)果

程序輸出按相反的變化方向輸出的，真實(shí)的狀況應(yīng)當(dāng)是從0、9、……、15變化的。七、總結(jié)和體會(huì)

這個(gè)程序還有很大的改進(jìn)空間，首先是人性化方面的設(shè)計(jì)，這個(gè)程序最終的輸出結(jié)果是用10進(jìn)制的，而我們需要知道的應(yīng)當(dāng)是二進(jìn)制的結(jié)果，所以應(yīng)當(dāng)直接把結(jié)果輸出為二進(jìn)制，還要按開(kāi)始到最終狀態(tài)的排序輸出。還有一種更為人性化的設(shè)計(jì)，就是把對(duì)應(yīng)的每個(gè)二進(jìn)制代碼代表的含義直接用中文表示出來(lái)，這樣的結(jié)果更直觀，便利用戶使用。例如：0000時(shí)，

程序輸出：所有的物品都在南岸。后面的一個(gè)狀態(tài)是9（1001），程序輸出：農(nóng)夫和羊到了北岸。

通過(guò)這個(gè)程序的學(xué)習(xí)，很受啟發(fā)，明白了如何用計(jì)算機(jī)解決實(shí)際生活中的問(wèn)題。剛開(kāi)始接到這個(gè)題目時(shí)，感覺(jué)到相當(dāng)困難，由于這種題以前是考驗(yàn)我們的IQ用的，現(xiàn)在沒(méi)想到要用計(jì)算機(jī)來(lái)解決，而且計(jì)算機(jī)又沒(méi)有思想，怎樣讓它想問(wèn)題，實(shí)現(xiàn)我們需要的功能。原來(lái)，可以把實(shí)際的問(wèn)題轉(zhuǎn)變?yōu)閿?shù)學(xué)模型，通過(guò)計(jì)算機(jī)超強(qiáng)悍的循環(huán)功