1、精選優質文檔-傾情為你奉上合肥學院計算機科學與技術系課程設計報告2009 2010 學年第二學期課程 數據結構與算法課程設計名稱農夫攜物過河問題學生姓名程夢云學號專業班級08計科(2)指導教師王昆侖 張貫虹2010年5月題目：農夫攜物過河問題內容：有一農夫要將自己的兔子、蔬菜和狐貍等3件物品運過河。但農夫過河時所用的船每次最多只能裝其中的一件物品，而這3件物品之間又存在一定的制約關系：兔子不能單獨和狐貍以及不能和蔬菜在一起，因為狐貍要吃兔子，兔子也能吃蔬菜。試構造出問題模式以編程實現這一問題的求解。一、問題分析和任務定義根據對象的狀態分為過河（1）和不過河（0），此對象集合就構成了一個狀態空間

2、。問題就是在這個狀態空間內搜索一條從開始狀態到結束狀態的安全路徑。顯然，其初始狀態為四對象都不過河，結束狀態為四對象全部過河。這里利用圖的廣度優先算法思想處理，并采用隊列存儲，靈活運用二進制的特點完美解決問題。對于農夫，狐貍，兔子，蔬菜組成一個4位二進制代碼，即4位二進制數分別代表了農夫、狐貍、白菜和兔子，狀態空間為16，初始狀態為（0000），目標為（1111）。解決問題的方法是，首先將初始狀態（0000）入隊(第一層)，再將由初始狀態（0000）可達到的所有安全狀態入隊（第二層），能由已有的安全狀態到達的安全且不重復的所有狀態入隊（第三層），依次如此直到狀態（1111）為止。對當前對象是否

3、安全的判斷，若當農夫與兔子不在一起時，狐貍與兔子或兔子與蔬菜在一起是不安全的，其他情況是安全的。二、概要設計和數據結構的選擇求解這個問題的最簡單的方法是一步一步進行試探，每一步都搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。用計算機實現上述求解的搜索過程可以采用兩種不同的策略：一種是廣度優先(breadth_first) 搜索，另一種是深度優先(depth_first) 。此處采用廣度優先算法。廣度優先的含義就是在搜索過程中總是首先搜索下面一步的所有可能狀態，然后再進一步考慮更后面的各種情況。要實現廣度優先搜索，一般都采用隊列作為輔助結構。把下一步所有可能達到的狀態都列舉出來，

4、放在這個隊列中，然后順序取出來分別進行處理，處理過程中把再下一步的狀態放在隊列里。由于隊列的操作遵循先進先出的原則，在這個處理過程中，只有在前一步的所有情況都處理完后，才能開始后面一步各情況的處理。要模擬農夫過河問題，首先需要選擇一個對問題中每個角色的位置進行描述的方法。一個很方便的辦法是用四位二進制數順序分別表示農夫、狼、白菜和羊的位置。例如用0表示農夫或者某東西在河的南岸，1表示在河的北岸。因此整數5(其二進制表示為0101) 表示農夫和白菜在河的南岸，而狼和羊在北岸。表1 物品的所有位置狀態農夫、狐貍、白菜、兔子Location農夫、狐貍、白菜、兔子Location00000100080

5、001110019001021010100011310111101004110012010151101130110611101401117111115數據結構的選擇：本程序采用隊列處理。typedef struct node/ 順序隊列類型定義 int f, r;/定義頭尾指針 int datamaxlen; SeqQueue;為了實現上述程序的功能，需要：隊列的創建、判空、入隊、出隊、取隊首元素；判斷農夫、狐貍、白菜和兔子的位子，并以此來判斷該狀態是否安全；按位子輸出農夫、狐貍、；主函數，一個廣度優先的過程；各函數關系如下：mainCreateQenQueuesafeDFS_pathprin

6、tflocationclick圖1 各函數關系圖三、詳細設計和編碼完成了上面的準備工作，現在的問題變成：從初始狀態二進制0000(全部在河的南岸) 出發，尋找一種全部由安全狀態構成的狀態序列，它以二進制1111(全部到達河的北岸) 為最終目標，并且在序列中的每一個狀態都可以從前一狀態通過農夫（可以帶一樣東西）劃船過河的動作到達。并且要求在序列中不應該出現重復的狀態。算法分析如圖2。為了實現廣度優先搜索，算法中需要使用了一個整數隊列Q，它的每個元素表示一個可以安全到達的中間狀態。另外還需要一個數據結構記錄已被訪問過的各個狀態，以及已被發現的能夠到達當前這個狀態的路徑。由于在這個問題的解決過程中需

7、要列舉的所有狀態(二進制0000 1111)一共16種，所以可以構造一個包含16個元素的整數順序表來滿足以上的要求。用順序表的第i個元素記錄狀態i是否已被訪問過，若已被訪問過則在這個順序表元素中記入前驅狀態值，算法中把這個順序表叫做visited。visited的每個分量初始化值均為-1，每當我們在隊列中加入一個新狀態時，就把順序表中以該狀態作下標的元素的值改為達到這個狀態的路徑上前一狀態的下標值。visited的一個元素具有非負值表示這個狀態已訪問過，或是正被考慮。最后我們可以利用visited順序表元素的值建立起正確的狀態路徑。實現概要設計中定義的所有數據類型，對每個操作作出偽碼算法。1、

8、定義一個隊列的結構體，包含頭尾指針和組data。2、子函數：置空隊列Q->r=Q->f=03、子函數：判斷隊列是否為空return (Q->f = Q->r)4、子函數：入隊5、子函數：出隊6、子函數：取隊頭元素return (Q->dataQ->f)7、四個子函數，分別判斷農夫、狐貍、白菜、兔子的位置。具體利用二進制數的按位取與法來完成，其中農夫ox08對應的二進制為0000 1000，狐貍ox04對應的二進制為0000 0100，白菜ox02對應的二進制為0000 0010，兔子ox01對應的二進制為0000 0001。不難看出，1所在的位置即要判斷的物

9、品所在的位置。例如狀態1011，1011&&1000=1000，即判斷出農夫的位置為1，1011&&0100=0000，即判斷狐貍的位置為0。8、子函數：判斷狀態是否安全。通過調用上述7的四個子函數可分別判斷四個物品的位置，由此可知當兔子和白菜在一起且農夫不在以及狐貍和兔子在一起且農夫不在的時候為不安全狀態，返回0，其他狀態均是安全的，返回1。初始狀態 00001001安全1010不安全1000不安全1100不安全0000重復0001安全1011安全1101安全1001安全0010安全0001重復0011不安全0100安全0001重復0101不安全0000重復0

10、001重復1011重復1110安全1010不安全1101重復1110安全1100不安全1111過河成功0110安全0110安全圖2 算法分析9、點擊函數：先將visited全部賦值為-1，創建隊列，將初值0000入隊，location為每次取的隊頭元素，從第一位兔子開始循環至農夫，利用的是<<左移符號，然后將所有與農夫在同一側的物品（包括農夫自己，即不帶物品移動）均帶到河的另一側，實現語句為newlocation = location (0x08 | movers);其中括號里的ox08|movers意思是帶著物品或農夫獨自移動，按位取異或所得的結果正好能達到此效果。newloca

11、tion即為新狀態，判斷其狀態是否安全或是否重復，如果是則入隊，且將visited里下標為newlocation的位置賦值為location。確定完location的數值后，判斷鼠標點擊是什么按鈕，如果點的是開始鍵，則把location和newlocation賦值為15作為初始狀態，并顯示點擊下一步開始過河，如果開始點的就是下一步，且點下一步前未點開始即沒有賦值，則提示點開始。若已賦值，則在各個物品相應的位置輸出。10、輸出函數：根據location的值分別輸出四個物體的位置。由表1可知，當location得值小于8時，農夫均為0，則在左岸輸出農夫，否則在右岸輸出。當location的值小于4

12、或在712之間，狐貍均為0，則在左岸輸出狐貍，否則在右岸輸出。當location的值對4求模的值為0或1時，白菜均為0，則在左岸輸出白菜，否則在右岸輸出。當location的值為偶數時，兔子均為0，則在左岸輸出兔子，否則在右岸輸出。（注：在每次輸出前進行一次清屏處理。）11、釋放函數，釋放由此句柄控制的所有控件。YYNNYYNNNY開始創建隊列Ox00入隊隊空？訪問結束？取隊頭賦給locationfor (1 8; movers 左移)movers與農夫同側帶著movers移位Safe？未訪問？newlocation入隊visitednewlocation= locationID=開始newl

13、ocation=location=15ID=下一步已點開始？根據location的值按位置分別輸出四物Location=0?過河成功location = visitedlocation結束圖3 流程圖四、上機調試經分析可知，該問題總共有2種路徑可行，分別是：帶兔子到對岸 ，空手回本岸 ，帶狐貍到對岸 ，帶兔子回本岸 ，帶菜到對岸 ，空手回本岸 ，帶兔子到對岸；帶兔子到對岸，空手回本岸，帶菜到對岸 ，帶兔子回本岸 ，帶狐貍到對岸 ，空手回本岸 ，帶兔子到對岸。本程序輸出的路徑是前一種方案，具體見測試結果截圖部分。本來應該把2種方案都輸出的，要想第二種方法能夠輸出，比較是否重復的時候必須和除本層外

14、的層次比較，此處還未解決這一問題。另外本程序在搜索路徑是采用的是BFS即廣度優先搜索，還可用DFS即深度優先搜索。深度優先: 每個時刻探索一條路徑，并記錄訪問過的合法狀態，一直向前探視，直到走不通時回溯。顯然，應該用堆棧來保存訪問過的狀態，以便回溯。廣度優先：在所有可能的路徑上齊頭并進，同時探索可能性。這樣，在某個位置會有多個分支，他們都要進行處理，因此需要一個緩沖隊列，把他們進對保存，在依次出對處理。這樣才能應付所有的狀態。五、用戶使用說明在vc+6.0下運行程序即可得到解決問題的方案，不需要其他操作六、測試結果圖4 初始狀態圖5 如果第一步未按開始鍵圖6 點擊下一步過河圖7 過河步驟圖8

15、過河步驟圖9 過河步驟圖10 過河步驟圖11 過河步驟圖12 過河步驟圖13 過河步驟圖14 過河成功圖15 為location賦初值5圖16 程序錯誤七、參考文獻1 王昆侖，李紅. 數據結構與算法. 北京：中國鐵道出版社，2007年6月。2 嚴蔚敏，吳偉民. 數據結構（C語言版）. 清華大學出版社。3 網站CSDN 八、 附錄#include "stdafx.h"#include <windows.h>#include <windowsx.h>#include "resource.h"#include "MainDlg

16、.h"#include <stdio.h>#include <stdlib.h>BOOL WINAPI Main_Proc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam) switch(uMsg) HANDLE_MSG(hWnd, WM_INITDIALOG, Main_OnInitDialog); HANDLE_MSG(hWnd, WM_COMMAND, Main_OnCommand);HANDLE_MSG(hWnd,WM_CLOSE, Main_OnClose); return FALSE;BOOL

17、Main_OnInitDialog(HWND hwnd, HWND hwndFocus, LPARAM lParam) return TRUE;const int maxlen=20;/定義maxlen的長度typedef struct node/ 順序隊列類型定義 int f, r;/定義頭尾指針 int datamaxlen;SeqQueue;void InitQueue(SeqQueue *Q)/置空隊列Q->r=0;Q->f=0;int isEmptyQueue_seq(SeqQueue *Q)/判斷隊列是否為空 return (Q->f = Q->r);voi

18、d enQueue_seq(HWND hwnd,SeqQueue *Q, int x) / 入隊 if (Q->r + 1) % maxlen = Q->f)MessageBox(hwnd,TEXT("隊列已滿!"),TEXT("警告"),MB_OK); else Q->dataQ->r = x; Q->r = (Q->r + 1) % maxlen; void deQueue_seq(HWND hwnd,SeqQueue *Q)/出隊 if (Q->f = Q->r)MessageBox(hwnd,TEX

19、T("隊列已空!"),TEXT("警告"),MB_OK); else Q->f = (Q->f + 1) % maxlen;int frontQueue_seq(HWND hwnd,SeqQueue *Q)/取隊頭元素 if (Q->f = Q->r)MessageBox(hwnd,TEXT("隊列已空!"),TEXT("警告"),MB_OK);return 0;else return (Q->dataQ->f);/ox01: 0000 0001 rabbit/ox02: 000

20、0 0010 cabbage/ox04: 0000 0100 fox/ox08: 0000 1000 farmerint farmer(int location)/判斷農夫的位置 return (0 != (location &0x08);int fox(int location)/判斷狐貍的位置 return (0 != (location &0x04);int cabbage(int location)/判斷白菜的位置 return (0 != (location &0x02);int rabbit(int location)/判斷兔子的位置 return (0 !

21、= (location &0x01);int safe(int location)/安全狀態的判斷函數 if (rabbit(location) = cabbage(location) && (rabbit(location) != farmer(location) return (0);/ 兔子吃白菜 if (rabbit(location) = fox(location) && (rabbit(location) != farmer(location) return (0);/ 狐貍吃兔子 return (1);/ 其他狀態是安全的void prin

22、tfarmer(HWND hwnd,int location)/輸出農夫的位置if(location<8)SetDlgItemText(hwnd,IDC_ETA2,TEXT("農夫");/在hwnd控制下的窗口的IDC_ETA2控件中輸出農夫elseSetDlgItemText(hwnd,IDC_ETA1,TEXT("農夫");/在hwnd控制下的窗口的IDC_ETA1控件中輸出農夫void printfox(HWND hwnd,int location)/輸出狐貍的位置if(location<12)&&(location&g

23、t;7)|(location<4)SetDlgItemText(hwnd,IDC_ETB2,TEXT("狐貍");/在hwnd控制下的窗口的IDC_ETB2控件中輸出狐貍elseSetDlgItemText(hwnd,IDC_ETB1,TEXT("狐貍");/在hwnd控制下的窗口的IDC_ETB1控件中輸出狐貍void printcabbage(HWND hwnd,int location)/輸出白菜的位置if(location%4=0|location%4=1)SetDlgItemText(hwnd,IDC_ETC2,TEXT("白菜

24、");/在hwnd控制下的窗口的IDC_ETC2控件中輸出白菜elseSetDlgItemText(hwnd,IDC_ETC1,TEXT("白菜");/在hwnd控制下的窗口的IDC_ETC1控件中輸出白菜void printrabbit(HWND hwnd,int location)/輸出兔子的位置if(location%2=0)SetDlgItemText(hwnd,IDC_ETD2,TEXT("兔子");/在hwnd控制下的窗口的IDC_ETD2控件中輸出兔子elseSetDlgItemText(hwnd,IDC_ETD1,TEXT(&q

25、uot;兔子");/在hwnd控制下的窗口的IDC_ETD1控件中輸出兔子void empty(HWND hwnd)/清屏SetDlgItemText(hwnd,IDC_ETA1,TEXT("");SetDlgItemText(hwnd,IDC_ETA2,TEXT("");SetDlgItemText(hwnd,IDC_ETB1,TEXT("");SetDlgItemText(hwnd,IDC_ETB2,TEXT("");SetDlgItemText(hwnd,IDC_ETC1,TEXT("&q

26、uot;);SetDlgItemText(hwnd,IDC_ETC2,TEXT("");SetDlgItemText(hwnd,IDC_ETD1,TEXT("");SetDlgItemText(hwnd,IDC_ETD2,TEXT("");void Main_OnCommand(HWND hwnd, int id, HWND hwndCtl, UINT codeNotify)/點擊函數int i, movers, newlocation,location,visited20;/movers:正在移動的物品;visited:用于記錄已考

27、慮的狀態路徑TCHAR strlo256;/用于存放location轉換的字符 SeqQueue *Q;/用于記錄可以安全到達的中間狀態SeqQueue movet; Q = &movet;/取movet的地址InitQueue(Q);/建空隊 enQueue_seq(hwnd,Q, 0x00);/初始狀態0000進隊列 for (i = 1; i < 16; i+)/定義數組visited初值 visitedi = -1; visited0 = 0;/初始化visited0while (!isEmptyQueue_seq(Q) && (visited15 = -

28、1)/Q非空或已全部被訪問過 location = frontQueue_seq(hwnd,Q);/取隊頭狀態為當前狀態 deQueue_seq(hwnd,Q);/隊頭元素出隊 for (movers = 1; movers <= 8; movers <<= 1)/考慮各種物品移動,<<為左移運算符 if (0 != (location &0x08) = (0 != (location & movers)/農夫與移動的物品在同一側newlocation = location (0x08 | movers); /計算新狀態，為按位異或，|為按位或if (safe(newlocation) && (visitednewlocation = -1)/新狀態安全且未處理visitednewlocation = location;/記錄新狀態的前驅enQueue_seq(hwnd,Q, newlocation);/新狀態入隊static int k1=0;/靜態變量 switch(id) case IDC_begin:/如果點擊開始鍵k1=1;SetDlgItemText(hwnd,IDC_LO,"15");/在IDC_LO中顯示15SetDlgItemText(hwnd,IDC_NL