農(nóng)夫過河99577

1、數(shù)學與計算機學院數(shù)學與計算機學院數(shù)據(jù)結構數(shù)據(jù)結構實驗報告實驗報告本實驗的目的是進一步理解順序表和隊列的邏輯結構和存儲結構，進一步提高使用理論知識指導解決實際問題的能力。一、【問題描述】一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留

2、下狼和羊自己離開，而狼不吃白菜。請求出農(nóng)夫將所有的東西運過河的方案。二、【數(shù)據(jù)結構設計】求解這個問題的簡單的方法是一步一步進行試探，每一步搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。要模擬農(nóng)夫過河問題，首先需要對問題中每個角色的位置進行描述。一個很方便的辦法是用四位二進制數(shù)順序分別表示農(nóng)夫、狼、白菜和羊的位置。用0表示農(nóng)夫或者某東西在河的南岸，1表示在河的北岸。例如整數(shù)5(其二進制表示為0101)表示農(nóng)夫和白菜在河的南

3、岸，而狼和羊在北岸?，F(xiàn)在問題變成：從初始狀態(tài)二進制0000(全部在河的南岸)出發(fā)，尋找一種全部由安全狀態(tài)構成的狀態(tài)序列，它以二進制1111(全部到達河的北岸)為最終目標，并且在序列中的每一個狀態(tài)都可以從前一狀態(tài)到達。為避免瞎費功夫，要求在序列中不出現(xiàn)重復的狀態(tài)。實現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：一種是廣度優(yōu)先(breadth_first)搜索，另一種是深度優(yōu)先(depth_first)搜索。本書只介紹在廣度優(yōu)先搜索方法中采用

4、的數(shù)據(jù)結構設計。廣度優(yōu)先就是在搜索過程中總是首先搜索下面一步的所有可能狀態(tài)，再進一步考慮更后面的各種情況。要實現(xiàn)廣度優(yōu)先搜索，可以使用隊列。把下一步所有可能的狀態(tài)都列舉出來，放在隊列中，再順序取出來分別進行處理，處理過程中把再下一步的狀態(tài)放在隊列里……。由于隊列的操作遵循先進先出的原則，在這個處理過程中，只有在前一步的所有情況都處理完后，才能開始后面一步各情況的處理。這樣，具體算法中就需要用一個整數(shù)隊列moveTo，它的每個元素表示一個

5、可以安全到達的中間狀態(tài)。另外還需要一個數(shù)據(jù)結構記錄已被訪問過的各個狀態(tài)，以及已被發(fā)現(xiàn)的能夠到達當前這個狀態(tài)的路徑。由于在這個問題的解決過程中需要列舉的所有狀態(tài)（二進制0000－1111）一共16種，所以可以構造一個包含16個元素的整數(shù)順序表來實現(xiàn)。順序表的第i個元素記錄狀態(tài)i是否已被訪問過，若已被訪問過則在這個順序表元素中記入前驅狀態(tài)南岸北岸狼白菜農(nóng)夫羊四、【界面設計】運行程序時，直接輸出過河的步驟，即結果。五、【編碼實現(xiàn)】#inclu

6、de“stdafx.h“#include“iostream“#include“stdio.h“#include“stdlib.h“#defineN100usingnamespacestdtypedefstructintdata[N]intfrontrearQueuevoidShow(introute[16])intfarmer(intlocation)return(0!=(locationintwolf(intlocation)retu