農(nóng)夫過河問題(c++編寫)(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1、問題描述從前，一個農(nóng)夫帶著一只狼，一只羊和一棵白菜要河（注意該狼被農(nóng)夫訓(xùn)服了，但還會吃羊）。他要將所有東西安全的帶到河的對岸，不幸的是河邊只有一條船，只能裝下農(nóng)夫和他的一樣?xùn)|西，并且農(nóng)夫必須每次都隨船過，因為只有他能撐船。在無人看管的情況下，狼要吃羊，羊要吃白菜，因此，農(nóng)夫不能在河的某邊岸上單獨留下狼和羊，也不能單獨留下羊和白菜。那么農(nóng)夫如何才能使三樣?xùn)|西平安過河呢？2、需求分析1）、農(nóng)夫必須把狼，羊，白菜全部都載過河，且一次只能載一個；2）、要求狼和羊不能單獨在一起，羊和白菜也不能單獨在一起，即要么羊單獨在河的一邊，要么羊和農(nóng)夫在一起。 3、系統(tǒng)概述設(shè)計對于上述

2、情況，可以將河的兩岸抽象成成數(shù)學(xué)問題，即將河的本岸抽象成數(shù)字0，將對岸抽象成1；且將狼，羊，白菜，農(nóng)夫，分別抽象成數(shù)字0，1，2，3。而用數(shù)組aij（取值只能為0和1）表示第i次運載是，j（j=0,1,2,3。分別表示狼，羊，白菜，農(nóng)夫）所在的位置。而用bi表示第i次運載時船上運載的東西（因為農(nóng)夫每次都必須在船上，所以不用記錄，除非穿上只有農(nóng)夫一人）。如此一來，是否全部過河的問題就轉(zhuǎn)化為判斷ai0，ai1，ai2，ai3是否全為1了，即相加之和是否為4的問題了；而四者中的兩者是否能在一起的問題就轉(zhuǎn)化它們各自的aij是否相等的問題了。4、系統(tǒng)詳細設(shè)計創(chuàng)建一個數(shù)組aMAXTIMES4用于存放農(nóng)夫，

3、狼，羊，白菜的位置，用0表示本岸，1表示對岸 ；bMAXTIMES用于存放狼，羊，白菜，農(nóng)夫的編號; 0: 狼，1:羊，2:白菜，3:農(nóng)夫；編寫一個遞歸函數(shù)Ferry(int ferryTimes)，其中ferryTimes為渡河次數(shù)，在函數(shù)中，應(yīng)考慮3個問題：1）、用aferryTimes0 + aferryTimes1 + aferryTimes2 + aferryTimes3 = 4語句判斷是否全部到達對岸，如果是，則直接輸出結(jié)果，否則，考慮第二個問題；2）、狼和羊是否單獨在一起，羊和白菜是否單獨在一起，用語句aferryTimes1 != aferryTimes3 &&

4、 (aferryTimes2 = aferryTimes1 | aferryTimes0 = aferryTimes1)來實現(xiàn)；3）、如果上兩個條件都不滿，則可執(zhí)行運輸?shù)膭幼?，但每次都?yīng)考慮，該運輸情況以前是否執(zhí)行過（即兩岸以及船上的東西以及各自位置和以前完全相同），如果沒被執(zhí)行過，則可以保存此時四者各自的狀態(tài)，并遞歸的進行下一次運載。5、系統(tǒng)測試6、經(jīng)驗總結(jié)解決實際問題時，應(yīng)先分析實際問題，找出實際問題的所有約束條件，然后對問題進行數(shù)學(xué)模型的抽象化，抓主要因素，省去一些不需要的因素，將其抽象為數(shù)學(xué)問題，然后再從整體上設(shè)計算法，搭建程序的框架，最后一步步完善細節(jié)，這樣做，會使本來毫無頭緒的問題

5、變得清晰起來。7、參考文獻C+程序設(shè)計 數(shù)據(jù)結(jié)構(gòu)算法設(shè)計與分析程序代碼如下：#include <iostream>#include <stdlib.h> #include <string.h> using namespace std;const int MAXTIMES = 20; int aMAXTIMES4;/存放農(nóng)夫，狼，羊，白菜的位置，用0表示本岸，1表示對岸 char *name = "狼", "羊", "白菜", "農(nóng)夫自己" int bMAXTIMES; /用于存放

6、狼，羊，白菜，農(nóng)夫的編號; 0: 狼，1:羊，2:白菜，3:農(nóng)夫 void Ferry(int ferryTimes) /ferryTimes為渡河次數(shù) int i;if (aferryTimes0 + aferryTimes1 + aferryTimes2 + aferryTimes3 = 4) /都到達對岸 for (i = 0; i < ferryTimes; i+) if (ai3 = 0) cout<<"ttt載"<<namebi<<"到對岸"<<endl; else cout<<

7、;"ttt載"<<namebi<<"回本岸"<<endl; cout<<endl; return; /狼單獨和羊在一起以及羊和白菜單獨在一起的情況if (aferryTimes1 != aferryTimes3 && (aferryTimes2 = aferryTimes1 | aferryTimes0 = aferryTimes1) return; /用于判斷此種情況在前searchTimes次運載過程中是否已經(jīng)出現(xiàn)過，若出現(xiàn)過則不用記錄for (i = 0; i < ferryTi

8、mes; i+) for(int j = 0; j < 4; j+)if(aferryTimesj != aij)break;if(j = 4)return; /若沒有出現(xiàn)，則將運載后抵達另一岸的結(jié)果記錄下來，并進行下一次運載for (i = 0; i <= 3; i+) bferryTimes = i; aferryTimes + 10 = aferryTimes0;aferryTimes + 11 = aferryTimes1;aferryTimes + 12 = aferryTimes2;aferryTimes + 13 = 1 - aferryTimes3; if (aferryTimesi = aferryTimes3) aferryTimes + 1i = aferryTimes + 13; Ferry(ferryTimes + 1); void main() cout<<"n *n"cout<<" * - *n"cout<<" * | 農(nóng)夫過河問題 | *n"cout&