農(nóng)夫過河99577

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

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

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

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

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