農(nóng)夫過(guò)河數(shù)據(jù)結(jié)構(gòu)

1、鄭州輕工業(yè)學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書(shū)題目 農(nóng)夫過(guò)河 專業(yè)、班級(jí) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)號(hào) 姓名 主要內(nèi)容：一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸，要把這些東西全部運(yùn)到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場(chǎng)，則狼不能吃羊，羊不能吃白菜；否則狼會(huì)吃羊，羊會(huì) 吃白菜。所以農(nóng)夫不能留下羊和白菜自己離開(kāi)，也不能留下狼和羊自己離開(kāi)，而 狼不能吃白菜。要求給出農(nóng)夫?qū)⑺械臇|西運(yùn)過(guò)河的方案。 基本要求: 編寫(xiě)求解該問(wèn)題的算法程序，并用此程序上機(jī)運(yùn)行、調(diào)試，屏幕顯示結(jié)果，能結(jié)合程序進(jìn)行分析。主要參考資料: 數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏完 成 期 限： 2012/6

2、/21 指導(dǎo)教師簽名： 課程負(fù)責(zé)人簽名： 年 月 日 鄭州輕工業(yè)學(xué)院本科數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告設(shè)計(jì)題目：農(nóng)夫過(guò)河學(xué)生姓名：系 別：計(jì)算機(jī)與通信工程學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué) 號(hào)：指導(dǎo)教師： 2012年 6 月 21 日一， 設(shè)計(jì)題目問(wèn)題描述：一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸，他要把這些東西全部運(yùn)到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場(chǎng)，則狼不能吃羊，羊不能吃白菜；否則狼會(huì)吃羊，羊會(huì)吃白菜。所以農(nóng)夫不能留下羊和白菜自己離開(kāi)，也不能留下狼和羊自己離開(kāi)，而狼不能吃白菜。要求給出農(nóng)夫?qū)⑺械臇|西運(yùn)過(guò)河的方案。

3、二， 運(yùn)行環(huán)境（軟、硬件環(huán)境）VC6.0 Windows7系統(tǒng)三， 算法設(shè)計(jì)的思想對(duì)于這個(gè)問(wèn)題，我們需要先自動(dòng)生成圖的鄰接矩陣來(lái)存儲(chǔ)，主要方法是先生成各種安全狀態(tài)結(jié)點(diǎn)，存放在頂點(diǎn)向量中；再根據(jù)判斷兩個(gè)結(jié)點(diǎn)間狀態(tài)是否可以轉(zhuǎn)換來(lái)形成頂點(diǎn)之間的所有邊，并把它們保存在鄰接矩陣中。在建立了圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)后，利用遞歸深度優(yōu)先搜索求出從頂點(diǎn)（0，0，0，0）到頂點(diǎn)（1，1，1，1）的一條簡(jiǎn)單路徑，這樣做只能搜到一種合理方法，因?yàn)樯疃葍?yōu)先搜索遍歷一個(gè)圖的時(shí)候每一個(gè)結(jié)點(diǎn)只能被訪問(wèn)一次。四， 算法的流程圖要寫(xiě)算法的流程圖，必須要先很了解自己的函數(shù)結(jié)構(gòu)，我先在紙上手動(dòng)的把整個(gè)過(guò)程在紙上畫(huà)一遍，了解它的大體流程

4、，然后把各個(gè)函數(shù)給分開(kāi)，下面是我自己根據(jù)我的代碼中畫(huà)的各個(gè)函數(shù)畫(huà)的流程圖，希望老師滿意。主函數(shù)的流程圖：開(kāi)始結(jié)束初始化圖輸出路徑調(diào)用DFSpath初始化圖函數(shù)的流程圖：返回主函數(shù)開(kāi)始初始化鄰接矩陣讀取4個(gè)整型變量判斷它們是否連接判斷狀態(tài)是否安全讀入兩個(gè)頂點(diǎn)初始化圖的頂點(diǎn)DFSpath函數(shù)的流程圖：開(kāi)始入棧判斷是否被訪問(wèn)過(guò)退棧返回主函數(shù)調(diào)用DFSpath五， 算法設(shè)計(jì)分析我的第一感覺(jué)，它可能是一個(gè)含有三個(gè)結(jié)點(diǎn)的圖的問(wèn)題，但這樣做，我們沒(méi)法來(lái)表示這個(gè)過(guò)程。在這個(gè)問(wèn)題的解決過(guò)程中，農(nóng)夫需要多次架船往返于兩岸之間，每次可以帶一樣?xùn)|西或者自己?jiǎn)为?dú)過(guò)河，每一次過(guò)河都會(huì)使農(nóng)夫、狼、羊和菜所處的位置發(fā)生變化。

5、如果我們用一個(gè)四元組（Farmer,Wolf,Sheep,Veget）表示當(dāng)前農(nóng)夫、狼、羊和菜所處的位置，其中每個(gè)元素可以是0或1，0表示在左岸，1表示在右岸。這樣，對(duì)這四個(gè)元素的不同取值可以構(gòu)成16種不同的狀態(tài)，初始時(shí)的狀態(tài)則為（0，0，0，0），最終要達(dá)到的目標(biāo)為（1，1，1，1）。狀態(tài)之間的轉(zhuǎn)換可以有下面四種情況：（1）農(nóng)夫不帶任何東西過(guò)河，可表示為：(Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf,Sheep,Veget)我們需要把農(nóng)夫的狀態(tài)取反。（2）當(dāng)農(nóng)夫帶狼過(guò)河時(shí)，即當(dāng)Farmer=Wolf時(shí)：(Farmer,Wolf,Sheep,Veget) (!

6、Farmer,!Wolf,Sheep,Veget)我們要把農(nóng)夫和狼的狀態(tài)全部取反。（3）當(dāng)農(nóng)夫帶羊過(guò)河，即當(dāng)Farmer=Sheep時(shí)：(Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf,!Sheep,Veget)我們要把農(nóng)夫和羊的狀態(tài)進(jìn)行取反。（4）當(dāng)農(nóng)夫帶菜過(guò)河時(shí)，即當(dāng)Farmer=Veget時(shí)：(Farmer,Wolf,Sheep,Veget) (!Farmer,Wolf,Sheep,!Veget)我們要把農(nóng)夫和白菜的狀態(tài)取反。然后在這16種狀態(tài)中，有些狀態(tài)是不安全的，是不允許出現(xiàn)的，如（0，1，1，0）表示農(nóng)夫和菜在南岸，而狼和羊在北岸，這樣狼會(huì)吃掉羊。我們

7、需要從16種狀態(tài)中刪去這些不安全狀態(tài)，將剩余的安全狀態(tài)之間根據(jù)上面的轉(zhuǎn)換關(guān)系連接起來(lái)，就得到如下圖所示的兩圖。并且我們?cè)谶@采用鄰接矩陣的方法來(lái)實(shí)現(xiàn)這個(gè)問(wèn)題。下面將會(huì)給出解題過(guò)程的一些細(xì)節(jié)。圖1 為篩選后剩余的安全結(jié)點(diǎn)及其下標(biāo)號(hào)的表，圖2是 農(nóng)夫、狼、羊和菜安全轉(zhuǎn)移到對(duì)岸的過(guò)程及其它們的狀態(tài)圖。000010001200103010040101510106101171101811109111110圖1 篩選后剩余的安全結(jié)點(diǎn)及其下標(biāo)號(hào)(0,0,0,0)(1,1,1,1)(1,0,1,0)(1,0,1,1)(0,0,0,1)(0,1,0,1)(0,0,1,0)(1,1,1,0)(0,1,0,0)(1,

8、1,0,1)圖2 農(nóng)夫、狼、羊和菜問(wèn)題的狀態(tài)圖這樣，原始問(wèn)題就轉(zhuǎn)換為在這個(gè)圖中尋找一條從頂點(diǎn)（0，0，0，0）到頂點(diǎn)（1，1，1，1）的路徑的問(wèn)題，這就要選用深度優(yōu)先搜索的方法。六， 運(yùn)行結(jié)果分析結(jié)果分析：這四個(gè)數(shù)字依次代表農(nóng)夫，狼，羊，白菜，（0,0,0,0）表示四種生物都在南岸，也就是初始狀態(tài)，（1,0,1,0）代表農(nóng)夫帶著羊去了北岸，(0,0,1,0)代表農(nóng)夫空手從北岸回到南岸，(1,0,1,1)代表農(nóng)夫帶著白菜去了北岸，(0,0,0,1)代表農(nóng)夫帶著羊又回到了南岸，(1,1,0,1)代表農(nóng)夫帶著狼去了北岸，(0,1,0,1)代表農(nóng)夫空手回到了南岸，(1,1,1,1)農(nóng)夫帶著羊又來(lái)到了北

9、岸。到此為止，農(nóng)夫把所有東西都帶到了北岸。七， 收獲及體會(huì)最開(kāi)始拿到這道題，我們都能用自己的語(yǔ)言來(lái)描述怎么做才能達(dá)到目的，但細(xì)細(xì)想來(lái)，我們?cè)鯓佑糜?jì)算機(jī)語(yǔ)言來(lái)實(shí)現(xiàn)這個(gè)過(guò)程呢，我最開(kāi)始想到的是用關(guān)節(jié)點(diǎn)和連通圖來(lái)做，但是這道題的過(guò)程卻沒(méi)法來(lái)實(shí)現(xiàn)，最后考慮到用這種四元組形式的結(jié)點(diǎn)來(lái)表示圖，0和1代表每種生物不同的狀態(tài)，它或者在北岸，或者在南岸，總共有16個(gè)結(jié)點(diǎn)，如果這樣保持16個(gè)結(jié)點(diǎn)，并在下面的函數(shù)中每次都判斷這個(gè)結(jié)點(diǎn)的狀態(tài)是不是安全的，這使其很麻煩，所以在開(kāi)始的時(shí)候直接篩選出安全狀態(tài)的結(jié)點(diǎn)，不再考慮不安全的，把圖的結(jié)點(diǎn)數(shù)直接降到10個(gè)，這樣思路會(huì)更清晰，這是做這道題時(shí)的一些問(wèn)題和解決方法。還有一點(diǎn)就

10、是如果用深度優(yōu)先搜索的話，只能輸出問(wèn)題的一種方法，如果采用隊(duì)列方法的話，應(yīng)該可以輸出全部方法，由于時(shí)間原因，我選擇的是深度優(yōu)先搜索，希望老師不要介意。另外就是做這種實(shí)際性的題目，要求我們把書(shū)本上學(xué)的內(nèi)容能合理的運(yùn)用，這其實(shí)是比較難的，通過(guò)自己寫(xiě)這個(gè)代碼，自己也更深刻的理解解決問(wèn)題的幾個(gè)大步驟，以前做題都是只要能夠完成題目的要求即可，有時(shí)就是代碼的累積，現(xiàn)在做數(shù)據(jù)結(jié)構(gòu)，他強(qiáng)調(diào)的就是結(jié)構(gòu)，針對(duì)一個(gè)題目，我們不再簡(jiǎn)單地只是要完成它，更重要的是選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，這才是最重要的，我這個(gè)題用的是圖的結(jié)構(gòu)，并用深度優(yōu)先搜索來(lái)搜索出一條從初始狀態(tài)到最后狀態(tài)的路徑，不管題目的簡(jiǎn)單與麻煩，我都是自己認(rèn)真的

11、盡力去做，就像和做數(shù)據(jù)結(jié)構(gòu)的試驗(yàn)作業(yè)一樣，要的就是自己動(dòng)手，盡力去做到最好，這份報(bào)告是我花了很長(zhǎng)時(shí)間才整理好的，包括畫(huà)流程圖，算法分析過(guò)程等，我把代碼的每一步都寫(xiě)出了它的注釋，希望老師滿意，同時(shí)也感謝老師對(duì)我們的輔導(dǎo)，謝謝老師！八， 源代碼#include<stdio.h>#define VEX_NUM 10/聲明一個(gè)最大值為VEX_NUM#define FALSE 0/0代表為假#define TRUE 1/1代表為真typedef structint Farmer,Wolf,Sheep,Veget;VexType;/這個(gè)是圖中每個(gè)頂點(diǎn)類型，包括四個(gè)數(shù)，0代表在南岸，1代表北岸t

12、ypedef structint vexnum,e;/這個(gè)是圖的頂點(diǎn)個(gè)數(shù)VexType vexsVEX_NUM;/它是頂點(diǎn)向量，分別表示各個(gè)頂點(diǎn)的內(nèi)容int adjVEX_NUMVEX_NUM;/這個(gè)是鄰接矩陣，我用的是鄰接矩陣的方法AdjGraph;/這個(gè)是表示該圖的結(jié)構(gòu)體int visitedVEX_NUM;/這個(gè)是來(lái)表示是否訪問(wèn)過(guò)該頂點(diǎn),0代表沒(méi)有訪問(wèn)過(guò)，/1代表已經(jīng)訪問(wèn)過(guò)int pathVEX_NUM;/這個(gè)數(shù)組是用來(lái)存儲(chǔ)它的路徑的，用來(lái)輸出int safe(int F,int W,int S,int V)/這個(gè)函數(shù)來(lái)判斷這個(gè)結(jié)點(diǎn)狀態(tài)是否安全if(F!=S&&(W=S|

13、S=V)/這個(gè)狀態(tài)表示，農(nóng)夫和羊不在同一邊，沒(méi)有農(nóng)夫/保護(hù)羊，防止狼吃羊，return 0;/也沒(méi)有農(nóng)夫去管制羊，防止羊吃掉白菜elsereturn 1;/否則就是安全的。這時(shí)返回1int connected(AdjGraph & G,int i,int j)/這個(gè)函數(shù)用來(lái)判斷圖的第i個(gè)和/第j個(gè)頂點(diǎn)是否可以經(jīng)過(guò)一次過(guò)河來(lái)相互轉(zhuǎn)換 int k;k=0;/從整體來(lái)看，前三個(gè)if語(yǔ)句是計(jì)算除了人之外，其余有幾種東西狀/態(tài)發(fā)生了改變，這個(gè)計(jì)數(shù)要是小于1才有可能這兩個(gè)頂點(diǎn)可以轉(zhuǎn)換，因?yàn)槿艘?次只能帶一種東西if(G.vexsi.Wolf!=G.vexsj.Wolf)k+;/當(dāng)狼的狀態(tài)發(fā)生改變，

14、k+if(G.vexsi.Sheep!=G.vexsj.Sheep)k+;/當(dāng)羊的狀態(tài)發(fā)生改變，k+if(G.vexsi.Veget!=G.vexsj.Veget)k+;/當(dāng)白菜的狀態(tài)發(fā)生改變，k+if(G.vexsi.Farmer!=G.vexsj.Farmer&&k<=1)/要想這兩個(gè)頂點(diǎn)能發(fā)/生轉(zhuǎn)換，人的狀態(tài)必須發(fā)生改變，并且其余狀態(tài)改變的物品小于等于1return 1;/說(shuō)明可以經(jīng)過(guò)一次過(guò)河轉(zhuǎn)換elsereturn 0;/否則就是不可以發(fā)生轉(zhuǎn)換int locate(AdjGraph & G,int F,int W,int S,int V)/這個(gè)函數(shù)是用來(lái)求

15、四種/東西的某種狀態(tài)在圖中是第幾個(gè)頂點(diǎn)int i;for(i=0;i<G.vexnum;i+)/判斷給定的這個(gè)狀態(tài)和圖中的某個(gè)頂點(diǎn)狀態(tài)是/否完全一致if(G.vexsi.Farmer=F&&G.vexsi.Wolf=W&&G.vexsi.Sheep=S&&G.vexsi.Veget=V)return i;/如果一致就把這個(gè)頂點(diǎn)的下標(biāo)返回return -1;/其余的返回-1，表示不存在void Create(AdjGraph & G)/這個(gè)是用來(lái)創(chuàng)造圖，包括處于安全狀態(tài)結(jié)點(diǎn)的篩/選和鄰接矩陣的初始化。int i,j,F,W,S,V;i

16、=0;for(F=0;F<=1;F+)/一種東西有南北岸之分，總共分為十六種狀態(tài)，for(W=0;W<=1;W+)/但只有部分是安全的，這做的就是選出安全狀態(tài)for(S=0;S<=1;S+)/安全的條件就是不能讓其形成生物鏈for(V=0;V<=1;V+)if(safe(F,W,S,V)=1)/判斷該種狀態(tài)是否安全，會(huì)不會(huì)出/現(xiàn)誰(shuí)吃誰(shuí)的情況G.vexsi.Farmer=F;/如果這種狀態(tài)安全，就把這種狀/態(tài)記錄下來(lái)G.vexsi.Wolf=W;G.vexsi.Sheep=S;G.vexsi.Veget=V;i+;/進(jìn)行下一個(gè)狀態(tài)判斷G.vexnum=i;/把最后的安全狀

17、態(tài)的頂點(diǎn)數(shù)記錄下來(lái)for(i=0;i<G.vexnum;i+)/接下來(lái)是對(duì)鄰接矩陣的初始化for(j=0;j<G.vexnum;j+)if(connected(G,i,j)=1)/connected函數(shù)是用來(lái)/判斷這兩個(gè)頂點(diǎn)是否可以經(jīng)過(guò)一次過(guò)河可以相互達(dá)到G.adjij=G.adjij=1;/如果經(jīng)過(guò)一次/過(guò)河可以相互轉(zhuǎn)換，把鄰接矩陣的該位置賦值為1elseG.adjij=G.adjji=0;/否則就把鄰接/矩陣該點(diǎn)位置賦值為0return;void printpath(AdjGraph & G,int u,int v)/這個(gè)是用來(lái)輸出該圖從第u個(gè)頂/點(diǎn)到第v個(gè)頂點(diǎn)上的路徑

18、int k=u;while(k!=v)/依次循環(huán)向后，直到第v個(gè)結(jié)點(diǎn)，跳出循環(huán) printf("(%d,%d,%d,%d)n",G.vexsk.Farmer,G.vexsk.Wolf,G.vexsk.Sheep,G.vexsk.Veget);/輸出路徑上各個(gè)頂點(diǎn)的內(nèi)容k=pathk;/依次向后移動(dòng)printf("(%d,%d,%d,%d)n",G.vexsk.Farmer,G.vexsk.Wolf,G.vexsk.Sheep,G.vexsk.Veget);/輸出最后一個(gè)頂點(diǎn)的內(nèi)容void DFSpath(AdjGraph & G,int u,int v)/這個(gè)函數(shù)利用遞歸形式圖的深度遍/歷來(lái)找到從第u個(gè)頂點(diǎn)到第v個(gè)頂點(diǎn)的路徑int j;visitedu=1;/把第u個(gè)頂點(diǎn)的visited賦值為1，說(shuō)明已經(jīng)訪問(wèn)過(guò)了for(j=0;j<G.vexnum;j+)/從鄰接矩陣中