農(nóng)夫過(guò)河問(wèn)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上農(nóng)夫過(guò)河問(wèn)題1 問(wèn)題描述一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場(chǎng)，則狼不能吃羊，羊不能吃白菜，否則狼會(huì)吃羊，羊會(huì)吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。要求：利用圖的存儲(chǔ)結(jié)構(gòu)和圖的搜索算法，求出農(nóng)夫?qū)⑺械臇|西運(yùn)過(guò)河的方案。2 需求分析2.1規(guī)定程序功能本題要解決的問(wèn)題就是農(nóng)夫如何帶著狼、羊、白菜安全過(guò)河。要求是船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場(chǎng)，則狼不能吃羊，羊不能吃白菜，否則狼會(huì)吃羊

2、，羊會(huì)吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。2.2輸入和輸出形式本程序自動(dòng)完成所有情況的輸入，不需要人為的輸入。然后根據(jù)程序里面調(diào)用相應(yīng)函數(shù)模塊可得到一種過(guò)河方案，然后自行輸出。輸出的是農(nóng)夫過(guò)河每一步的方案，即每一步中農(nóng)夫采取的行動(dòng)。 3 概要設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)題目要求用圖的存儲(chǔ)結(jié)構(gòu)，所以要想辦法將農(nóng)夫、狼、羊、白菜每一步的狀態(tài)用結(jié)點(diǎn)表示，他們狀態(tài)的改變到下一個(gè)結(jié)點(diǎn)可行，則在兩條結(jié)點(diǎn)中加一條邊。但是每個(gè)結(jié)點(diǎn)包含四個(gè)量，如果他們每個(gè)都各自用一個(gè)結(jié)構(gòu)體表示，則圖形就變得相當(dāng)?shù)姆爆崳虼讼氲揭粋€(gè)簡(jiǎn)單的結(jié)局辦法。河的兩岸是兩個(gè)不同的變量，剛好可以用0和

3、1表示，那么四個(gè)狀態(tài)量都用0和1則可表示他們每一步所處的位置，也就能明白農(nóng)夫每次是怎么過(guò)河的。3.2算法的設(shè)計(jì)本程序可以分成四個(gè)模塊，分別是：找到所有情況的點(diǎn)、從中挑選出滿足題意的點(diǎn)、創(chuàng)建滿足題意的點(diǎn)之間的邊、通過(guò)圖的深度優(yōu)先遍歷找到過(guò)河方案。各模塊之間的關(guān)系圖如下：找到所有情況的點(diǎn)（即0000-1111共16種組合）挑出符合題意的點(diǎn)（即農(nóng)夫不在時(shí)，狼不和羊、羊不和菜在一起）找到符合題意點(diǎn)之間邊的關(guān)系通過(guò)圖的深度優(yōu)先遍歷找到過(guò)河方案每個(gè)模塊函數(shù)為：void input_vertex(DataType *vertex) /所有情況頂點(diǎn)的輸入int right_vertex(DataType *v

4、ertex,DataType *vertex1) /選出滿足題意的頂點(diǎn)int right_edge(DataType *vertex,RowCol *edge,int n) /選出滿足題意的邊void DepthFSearch(AdjLGraph G,int v,int visited,DataType vert,int *a)/圖的深度優(yōu)先遍歷3.3抽象數(shù)據(jù)類型的設(shè)計(jì) 本題采用的是圖，因此要用到定義圖的結(jié)構(gòu)體 typedef structint f;/農(nóng)夫int w;/狼int s;/羊int c;/菜DataType;/結(jié)點(diǎn)信息結(jié)構(gòu)體定義typedef structint row;int

5、col;RowCol;/邊信息結(jié)構(gòu)體定義typedef struct Nodeint dest;/鄰接邊的弧頭結(jié)點(diǎn)序號(hào)struct Node *next;Edge;/鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體typedef struct DataType data; int sorce;/鄰接邊弧尾結(jié)點(diǎn)序號(hào) Edge *adj;/鄰接邊的頭指針AdjLHeight;/數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體typedef struct AdjLHeight a100;/鄰接表數(shù)組 int numOfVerts;/結(jié)點(diǎn)個(gè)數(shù) int numOfEdges;/邊個(gè)數(shù)AdjLGraph;/鄰接表結(jié)構(gòu)體4 詳細(xì)設(shè)計(jì)4.1算法的主要思想為

6、簡(jiǎn)化結(jié)點(diǎn)，將農(nóng)夫、狼、羊、白菜用0和1兩種狀態(tài)量表示，0表示在河的南岸，也就是初始所在的河岸。1表示在河的北岸，即渡過(guò)河到達(dá)的對(duì)岸。那么初始狀態(tài)即為0000，將其變?yōu)?111的中間狀態(tài)量即為過(guò)河方案。那么就從16種所有情況的頂點(diǎn)中選擇符合題意的結(jié)點(diǎn)，因?yàn)椴⒉皇撬悬c(diǎn)都滿足題意，限制要求為農(nóng)夫每次最多可帶狼、羊、白菜中的一個(gè)過(guò)河，農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開。選出所有滿足題意的結(jié)點(diǎn)后，就要構(gòu)造邊，邊即為符合題意兩結(jié)點(diǎn)之間的連接。中間有邊的兩結(jié)點(diǎn)必須符合農(nóng)夫的狀態(tài)在變，并且農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開。選出所有符合題意的結(jié)點(diǎn)和邊后就構(gòu)成了圖，采用

7、鄰接表的存儲(chǔ)結(jié)構(gòu)，然后通過(guò)圖的深度優(yōu)先遍歷，將所有滿足題意的結(jié)點(diǎn)遍歷一遍并輸出，到1111時(shí)即輸出了過(guò)河方案的全部步驟。4.2算法的實(shí)現(xiàn) 存儲(chǔ)16種全部情況以供挑選。 void inputdian(DataType *d) int f,w,s,c,i=0; for(f=0;f<=1;f+) for(w=0;w<=1;w+) for(s=0;s<=1;s+) for(c=0;c<=1;c+) di.f=f; di.w=w; di.s=s; di.c=c; i+; 選出符合題意的所有結(jié)點(diǎn)int rdian(DataType *d,DataType *d2) int i; i

8、nt num=0; for(i=0;i<16;i+) if(!(di.f!=di.s&&(di.w=di.s|di.s=di.c)d2num+=di; return num; 選出符合題意的結(jié)點(diǎn)之間的邊int rbian(DataType *d,RowCol *edge,int n) int df,dw,ds,dc; int i=0,j=0,num=0; for(i=0;i<n;i+) for(j=0;j<n;j+) df=di.f-dj.f;dw=abs(di.w-dj.w);ds=abs(di.s-dj.s);dc=abs(di.c-dj.c);if(df

9、!=0&&(dw+ds+dc)<=1)edgenum.col=i;edgenum+.row=j; return num; 圖的深度優(yōu)先遍歷void DepthFSearch(AdjLGraph G,int v,int visited,DataType d1,int *s) int w; d1(*s)=G.av.data; visitedv=1; (*s)+; w=GetFirstVex(G,v); while(w!=-1) if(!visitedw)DepthFSearch(G,w,visited,d1,s);w=GetNextVex(G,v,w); 4.3函數(shù)的調(diào)用關(guān)系圖inputdian(d);nd=rdian(d,rd);nb=rbian(rd,edge,nd);CreatGraph(&am