農夫過河報告(最終版)

1、農夫過河算法實驗報告數(shù)據結構項目課研究課題組長：崔俊組員：李琦、鄭鴻飛、王瑯輝、張育博這最起碼是一個報告，雖然我盡力的看，終究還是看不懂。摘要農夫過河問題是應用廣度優(yōu)先搜索和深度優(yōu)先搜索的典型問題， 但這里我們應用了簡單的數(shù)組，通過層層篩選的手段也解決了同樣的問題，其中用到了部分廣度優(yōu)先搜索的思想。前言農夫過河問題描述：一個農夫帶著只狼、一只羊和棵白菜，身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和件物品，另外只有農夫才能撐船。如果農夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農夫不能留下羊和白菜自己離開， 也不能留下狼和羊自己離開， 而狼不

2、吃白菜。 請求出農夫將所有的東西運過河的方案。正文1. 問題抽象和數(shù)據組織農夫過河問題應該應用圖的廣度優(yōu)先遍歷或者深度優(yōu)先遍歷， 但這里我們僅使用簡單的線性表數(shù)組，通過多重的條件限制，達成目的。這里我們同樣用 0 和 1 代表農夫、狼、羊、白菜在左岸還是在右岸，并規(guī)定 0 在左， 1 在右，我們的目的便是從 0000 通過一系列變換到 1111。2. 農夫過河算法源代碼#include <stdio.h>#define MAX 16typedef struct FWSVint farmer;int wolf;int sheep;int vegetable;Item;/ 函數(shù)原型/

3、操作： 篩選符合條件的安全的數(shù)組成員/ 操作前：無/ 操作后：返回安全數(shù)組的指針void screen(void);/ 操作：判斷下一個數(shù)應該取安全數(shù)組中那個數(shù)/ 操作前 : 傳遞一個結構體數(shù)組成員/ 操作后：返回另一個結構體數(shù)組指針I(yè)tem * judge(Item Fwsv);Item safeMAX;int k = 0; / 用于計數(shù) safe 中的總數(shù) int main (void)screen();Item * next;Item first,second,end;first = safe0;end = safek;printf("first:0000n");ne

4、xt = judge(first);for (int count = 0;count <= 6;count+)if (next->farmer + next->wolf + next->sheep + next->vegetable != 0)second = *next;next = judge(second);elsenext+;printf("end:1111n");return 0;void screen(void)int f = 0,w = 0,s = 0,v = 0;for(f = 0;f < 2;f+)for(w = 0;w

5、 < 2;w+)for(s = 0;s < 2;s+)for(v = 0;v < 2;v+)if (!(f != s && (s = w | s = v)safek.farmer = f;safek.wolf = w;safek.sheep = s;safek.vegetable = v;k+;Item * judge(Item Fwsv)Item * next;Item compare4;next = compare;int x1 = 0;int sum = 0;if (Fwsv.farmer = 0)for (int x = 0;x < k;x+)/

6、 把出現(xiàn)過的置零操作if(safex.farmer = Fwsv.farmer && safex.wolf = Fwsv.wolf && safex.sheep = Fwsv.sheep && safex.vegetable = Fwsv.vegetable )safex.farmer = 0;safex.wolf = 0;safex.sheep = 0;safex.vegetable = 0;/ 篩選出農夫狀態(tài)值與之前相反的1變 0 0變1if(safex.farmer=1&& (safex.farmer+safex.wolf+

7、safex.sheep + safex.vegetable != 4 )comparex1 = safex;x1+;for (int x2 = 0;x2 < 4;x2+)/ 刪除狀態(tài)值與農夫不同但是改變了的sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable; if (Fwsv.farmer != Fwsv.wolf && comparex2.wolf != Fwsv.wolf) |(Fwsv.farmer != Fwsv.sheep && comparex2.sheep!=Fwsv.she

8、ep)|(Fwsv.farmer!= Fwsv.vegetable&& comparex2.vegetable!=Fwsv.vegetable)|(Fwsv.farmer!= Fwsv.vegetable&& comparex2.vegetable!=Fwsv.vegetable)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;sum+=2;/ 對和的限制if(comparex2.farmer + comparex2.wolf + compar

9、ex2.sheep + comparex2.vegetable != sum)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;printf("-n");for(int x3 = 0;x3 < 4;x3+)if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf("上數(shù)與： %d%d%d%d相連 n",compa

10、rex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetabl） ;if (Fwsv.farmer = 1)for (int y = 0;y < k;y+)if(safey.farmer = Fwsv.farmer && safey.wolf = Fwsv.wolf && safey.sheep = Fwsv.sheep && safey.vegetable = Fwsv.vegetable )safey.farmer = 0;safey.wolf = 0;safey.sheep

11、= 0;safey.vegetable = 0;if(safey.farmer=0&& (safey.farmer+safey.wolf+safey.sheep + safey.vegetable != 0 )comparex1 = safey;x1+;for (int x2 = 0;x2 < 4;x2+)sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable; if (Fwsv.farmer != Fwsv.wolf && comparex2.wolf != Fwsv.wolf) |(Fws

12、v.farmer != Fwsv.sheep && comparex2.sheep!=Fwsv.sheep)|(Fwsv.farmer!= Fwsv.vegetable&& comparex2.vegetable!=Fwsv.vegetable)|(Fwsv.farmer!= Fwsv.vegetable&& comparex2.vegetable!=Fwsv.vegetable)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;

13、printf("-n");for(int x3 = 0;x3 < 4;x3+)if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf("上數(shù)與： %d%d%d%d相連 n",comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetable);return next;3. 算法功能說明和流程描述首先我們定義了一個結構體Itemtypedef struct FW

14、SVint farmer;int wolf;int sheep;int vegetable;Item;Item 中包含了農夫（farmer ），狼（ wolf ），羊（ sheep），白菜（ vegetable ）, 用來表示農夫、狼、羊、白菜的狀態(tài)，并作出規(guī)定當為0 的時候表示在左岸，當為1 的時候表示在右岸，我們的目標便是從接下來用一個調用函數(shù)0000 的狀態(tài)到screen （）1111 的狀態(tài)。void screen(void)int f = 0,w = 0,s = 0,v = 0;for(f = 0;f < 2;f+)for(w = 0;w < 2;w+)for(s = 0

15、;s < 2;s+)for(v = 0;v < 2;v+)if (!(f != s && (s = w | s = v)safek.farmer = f;safek.wolf = w;safek.sheep = s;safek.vegetable = v;k+;函數(shù)一連用了4 個for循環(huán)完成了對0000 到1111 之間每一位數(shù)字的所有排列組合的遍歷，雖然這里的時間復雜度直接躍至O(n4) 但卻是比較全面、寫法簡單的遍歷，而且n 僅為2，其中的if語句的判斷從所有的排列組合中（總計16 種）剔除了不會出現(xiàn)的組合，其中包括：農夫不在，羊吃白菜，狼吃羊等情況。并讓符合

16、條件的情況存入了全局變量數(shù)組safeMAX 中。Item * judge(Item Fwsv)函數(shù)是整個算法的核心，思想比較簡單但寫法繁瑣，目的是判斷safek數(shù)組中符合如題條件的數(shù)值，它的參數(shù)是上一次的狀態(tài)值，對于初始時便為0000，它的返回值是一個符合條件的數(shù)值的數(shù)組首地址 next 把符合條件的值存入了一個 compare4 數(shù)組，如果為單解則將，為了防止有多解的情況我們compare 中其他成員置零，接下來我們拆分著看看這個函數(shù)。if (Fwsv.farmer = 0)表示農夫現(xiàn)在在左岸接下來的for循環(huán)是對safek數(shù)組的遍歷，目的是第一輪找出符合條件的值for (int x = 0

17、;x < k;x+)/ 這里的 if 判斷是把出現(xiàn)過的值在 safek 中置零的操作，為了進一步方便判斷if(safex.farmer= Fwsv.farmer&& safex.wolf= Fwsv.wolf&& safex.sheep= Fwsv.sheep && safex.vegetable = Fwsv.vegetable )safex.farmer = 0; safex.wolf = 0; safex.sheep = 0; safex.vegetable = 0;/ 從safek中篩選出農夫狀態(tài)值與之前相反的并存入compare數(shù)

18、組中。 因為只有農夫會劃船， 所以來回農夫的狀態(tài)必定改變，比如傳進來的是0 打頭的傳輸出去的必定是1 打頭的。我們要做的就是從safek中找出農夫狀態(tài)值與之前相反的數(shù)值，總計5 個，其中我們把 1111 的情況也要剔除掉，現(xiàn)在總計4 個了，我們把符合要去的數(shù)值從16 個縮減到10 個現(xiàn)在又縮減到4 個，接下來我們還要縮減if(safex.farmer = 1 && (safex.farmer + safex.wolf + safex.sheep + safex.vegetable != 4 )comparex1 = safex;x1+;/ 這里的 for 便是對 compare

19、 的遍歷了for (int x2 = 0;x2 < 4;x2+)/ 上述縮減到 4 個但是范圍還是太大，現(xiàn)在置零狀態(tài)值與農夫不同但是改變了的。也就是說如果之前與農夫狀態(tài)值相同，說明和農夫在相同一側的岸， 這時它才有可能改變的機會， 要是與農夫之前與農夫狀態(tài)值不同，說明和農夫相處對岸，這時它改變了， 顯然是不符合邏輯的，狼，羊，白菜是不會自己游過河的。sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable; if (Fwsv.farmer != Fwsv.wolf && comparex2.wolf != Fw

20、sv.wolf) |(Fwsv.farmer != Fwsv.sheep && comparex2.sheep != Fwsv.sheep) | (Fwsv.farmer != Fwsv.vegetable && comparex2.vegetable | (Fwsv.farmer != Fwsv.vegetable && comparex2.vegetable != Fwsv.vegetable)!= Fwsv.vegetable)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep =

21、 0;comparex2.vegetable = 0;sum+=2;/ 由于船一次只能拉不超過兩個， 其中一個還要是農夫劃船， 所以這里我們對和有一個限制。當農夫拉著東西從左岸劃向右岸時，總的狀態(tài)值之和應該等于上一個狀態(tài)+現(xiàn)在的狀態(tài), 而現(xiàn)在的狀態(tài)和必定為2，所以sum+=2。這里我們舉個例子就明白了：0000開始，農夫拉著羊從左岸到右岸變成1010 （此時的狀態(tài)和為2），之后農夫劃船回來變成0010（此時狀態(tài)值為1），接著農夫劃船拉著狼從左至右變成1110（此時狀態(tài)和為3，3 = 1 + 2）.if(comparex2.farmer+comparex2.wolf+comparex2.shee

22、p+comparex2.vegetable != sum)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;printf("-n");/ 通過上述三種限制，我們已經可以判斷出safek中完全符合要求的數(shù)值了，可能有一個，可能有兩個，也可能多個，接下來的for遍歷compare 并打印我們需要的結果for(int x3 = 0;x3 < 4;x3+)if(comparex3.farmer+comparex3.wolf+comparex3.sheep+comparex3.vegetable != 0)printf("上數(shù)與： %d%d%d%d相連 n",comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetabl）if (Fwsv.farmer = 1)/* 表示農夫現(xiàn)在在右岸接下來的for循環(huán)是對safek數(shù)組的遍歷， 目的是第一輪找出符合條件的值，與Fwsv.farmer = 0的情況一樣，判斷方法與條件也完全相同，只不過對于 0 打頭的情況省去了對和的限制這一條件*/4.