C實(shí)現(xiàn)傳教士與野人過河問題試驗(yàn)報告

1、傳教士與野人過河問題實(shí)驗(yàn)報告1 問題定義河的兩岸有三個傳教士和三個野人需要過河，目前只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會被野人攻擊， 怎么找出一種安全的渡河方案呢？2 算法分析首先，先來看看問題的初始狀態(tài)和目標(biāo)狀態(tài)，定義河的兩岸分別為左岸和右岸，設(shè)定狀態(tài)集合為（左岸傳教士人數(shù)，右岸野人數(shù)，右岸傳教士人數(shù)，右岸野人數(shù)，船的位置）， 船的位置：-1表示船在左岸，1表示船在右岸。初始狀態(tài)：（3,3,0,0,0 ，-1）目標(biāo)狀態(tài)：（0，0，3，3，1）然后，整個問題就抽象成了怎樣從初始狀態(tài)經(jīng)中間的一系列狀態(tài)達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)的改變是通過劃

2、船渡河來引發(fā)的，所以合理的渡河操作就成了通常所說的算符，根 據(jù)題目要求，可以得出以下5個算符（按照渡船方向的不同，也可以理解為10個算符）： 渡1野人、渡1傳教士、渡1野人1傳教士、渡2野人、渡2傳教士根據(jù)船的位置，向左移或向右移通過遞歸依次執(zhí)行 5種算符，判斷是否找到所求，并 排除不符合實(shí)際的狀態(tài)，就可以找到所有可能的解，如圖1所示為遞歸函數(shù)流程圖。數(shù)據(jù)結(jié)構(gòu)方面采用如下所示的結(jié)構(gòu)體存儲當(dāng)前傳教士、野人、船三者的狀態(tài)。struct riverSides int churchL; /左岸傳教士數(shù)int wildL; /左岸野人數(shù)int churchR; /右岸傳教士數(shù)int wildR; /右岸

3、野人數(shù)int boat; /船的位置，-1在左岸，1在右岸;圖1傳教士與野人過河遞歸函數(shù)流程圖3 編程實(shí)現(xiàn)程序使用C+實(shí)現(xiàn)，具體代碼如下：#inelude <iostream>#inelude <vector>#inelude <string>using namespaeestd;struct riverSidesint ehurehL; /左岸傳教士數(shù)int wildL; /左岸野人數(shù)int ehurehR; /右岸傳教士數(shù)int wildR; /右岸野人數(shù)|int boat; /船的位置，-1在左岸，1在右岸；int myeount = 0; /統(tǒng)計(jì)成功

4、過河次數(shù)int CvsWdfs( riverSideslasteurrentState, veetor < riverSides > lastParameters , veetor <string >operation , int ifboaeurrentStatety )if ( lasteurrentState.ehurehR = 3 && lasteurrentState .wildR = 3)myeou nt+;eout << "第"<< myeount <<"次成功過河"

5、;<< endl;eout << "傳教士 野人| 移動方向"<< endl;for (int i = 0; i <operation .size(); i+)eout << operation i << endl;eout << en dl;return 0;/判斷過河操作否重復(fù)，去除死循環(huán)for (int i = 0; i < lastParameters .size() - 1; i+)if ( lastParameters i.wildL = lasteurrentState .wi

6、ldL&& lastParameters i.churchL =lasteurre ntState.ehurehL)if ( lasteurrentState.boat = lastParameters i.boat)return 0;/檢驗(yàn)人數(shù)數(shù)據(jù)合法性if ( lasteurrentState.ehurehL < 0 |lasteurrentState.wildL < 0 | lasteurrentState .ehurehR < 0| lasteurre ntState.wildR < 0)return 0;/傳教士是否被吃if ( lastcur

7、rentState.churchL < lastcurrentState.wildL&& lastcurrentState .churchL != 0) |(lastcurrentState .churchR <lastcurrentState.wildR&& lastcurrentState.churchR != 0)return 0;/遞歸執(zhí)行五類過河操作，boat=-1船在左岸，boat=1船在右岸，傳入boat為上一次船位置/下次應(yīng)當(dāng)取反riverSides curre ntState;/兩個傳教士過河|if ( lastcurrentSta

8、te.boat = 1)operation .push_back( " 20 |左岸->右岸");elseoperation .push_back( " 20 |右岸->左岸");curre ntState.churchL =lastcurre ntState .churchL - 2 *lastcurre ntState.boat;curre ntState.wildL =lastcurre ntState.wildL;curre ntState.churchR =lastcurre ntState.churchR + 2*lastcurr

9、e ntState.boat;curre ntState.wildR =lastcurre ntState.wildR;curre ntState.boat =-lastcurre ntState.boat;lastParameters .push back(currentState);CvsWdfs(curre ntState, operation .pop_back();lastParameters ,operation , 0);lastParameters .pop_back();/兩個野人過河if ( lastcurrentState.boat = 1)operation .push

10、_back( " 02 |左岸-> 右岸'');elseoperation .push_back( " 02 |右岸-> 左岸'');curre ntState.churchL =lastcurre ntState.churchL;curre ntState.wildL =lastcurre ntState.wildL - 2 *lastcurre ntState.boat;curre ntState.churchR =lastcurre ntState.churchR;curre ntState.wildR =lastcurre

11、 ntState.wildR + 2 *lastcurre ntState.boat;curre ntState.boat =-lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(currentState,lastParameters , operation , 0);lastParameters .pop_back();operation .pop_back();/ 一個野人，一個傳教士if ( lastcurrentState .boat = 1)operation .push_back( "

12、; 11 |左岸-> 右岸");elseoperation .push_back( " 11 |右岸-> 左岸");curre ntState.churchL =lastcurre ntState.churchL - 1 *lastcurre ntState.boat;curre ntState.wildL =lastcurre ntState.wildL - 1 *lastcurre ntState.boat;curre ntState.churchR =lastcurre ntState.churchR + 1 *lastcurre ntState

13、.boat;curre ntState.wildR =lastcurre ntState.wildR + 1 *lastcurre ntState.boat;curre ntState.boat = -lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(currentState,lastParameters , operation , 0);operation .pop_back();lastParameters .pop_back();/ 一個傳教士過河if ( lastcurrentState.boa

14、t = 1)operation .push_back( " 10 |左岸->右岸");elseoperation .push_back( " 10 |右岸->左岸");curre ntState.churchL = lastcurre ntState.churchL - 1 *lastcurre ntState.boat;curre ntState.wildL =lastcurre ntState.wildL;curre ntState.churchR = lastcurre ntState.churchR + 1 *lastcurre nt

15、State.boat;curre ntState.wildR =lastcurre ntState.wildR;curre ntState.boat = -lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(currentState,lastParameters ,operation , 0);operation .pop_back();lastParameters .pop back();/ 一個野人過河if ( lastcurrentState .boat = 1)operati onelse.pus

16、h_back( " 01 1左岸-> 右岸");operati on.push back( " 01 1右岸-> 左岸");curre ntState.churchL =lastcurre ntState.churchL;curre ntState.wildL =lastcurre ntState.wildL - 1 *lastcurre ntState.boat;curre ntState.churchR =lastcurre ntState.churchR;curre ntState.wildR =lastcurre ntState.wi

17、ldR + 1 *lastcurre ntState.boat;curre ntState.boat = -lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(currentState,lastParameters , operation , 0);operation .pop_back();lastParameters .pop_back();return 0;int mai n()int churchL = 3, wildL = 3, churchR = 0, wildR = 0;/分別用來計(jì)算左岸和右岸的傳教士和野人vector < riverSides > lastParameters; /保存每一步移動操作的兩岸傳教士、野人人數(shù)vector < string > operation;/保存當(dāng)前操作的描述/初始化左岸參數(shù)，可以認(rèn)為是從右岸移動至左岸的操作/boat=-1表示船在左岸，boat=1表示船在右岸riverSides curre ntState;curre ntState.churchL = 3;curre ntState.wil