完整word版C實(shí)現(xiàn)傳教士與野人過河問題實(shí)驗(yàn)報(bào)告

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

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

3、 riversides intintintintint;3 編程實(shí)現(xiàn)程序使用C+實(shí)現(xiàn)，具體代碼如下:#inelude #inelude #inelude using namespacestd;structriversidesintehurehL;intint/左岸傳教士數(shù) 左岸野人數(shù)/右岸傳教士數(shù)intintwildL; /ehurehR;wildR; /右岸野人數(shù)boat; /船的位置，-1在左岸，1在右岸；myeount = 0;/統(tǒng)計(jì)成功過河次數(shù)CvsWdfs( riverSidesveetor operationintintlasteurre ntState, veetor last

4、Parameters ,int ifboaeurrentStatety )if(lasteurrentState.ehurehR = 3 &lasteurre ntState.wildR = 3)myeou nt+;第傳教士野人|i = 0; i eout eout for ( int |myeount 次成功過河 endl;移動(dòng)方向 endl;operation .size。； i+)eout operation i endl;eout en dl;return 0;|/判斷過河操作否重復(fù)，去除死循環(huán)for (int i = 0; i last Parameters .size() - 1;

5、 i+)if ( last Parameters i.wildL =.wildL& last Parameters i.ehurehL =lasteurre ntState.ehurehL)lasteurre ntStateif(lasteurre ntState.boat = last Parameters i.boat)return 0;|/檢驗(yàn)人數(shù)數(shù)據(jù)合法性(lastcurrentState.churchL 0 |lastcurrentState.wildL 0 |lastcurre ntState .churchR 0 |lastcurre ntState.wildR 0)return

6、 0; |傳教士是否被吃if/if0) 11 (lastcurrentState.churchL lastcurrentState .wildL& lastcurrentState.churchL !=lastcurrentState .churchR 右岸)；operation .push_back( 20 |curre ntState.churchL = lastcurre ntState右岸- 左岸);.churchL - 2 *lastcurre ntState.boat;curre ntState.wiIdL =lastcurre ntState.wiIdL;curre ntStat

7、e.churchR =lastcurre ntState.churchR + 2 *lastcurre ntState.boat;curre ntState.wildR =lastcurre ntState.wildR;curre ntState.boat =-lastcurre ntState.boat;last Parameters .p ush_back(curre ntState);CvsWdfs(curre ntState,last Parameters,operation , 0);operation .pop_back();last Parameters .po p_back()

8、;/兩個(gè)野人過河if ( lastcurrentState.boat = 1)operation .push_back( 02 |左岸- 右岸);elseoperation .push_back( 02 |lastcurre ntStatecurre ntState.churchL =右岸- 左岸);.churchL;curre ntState.wildL =lastcurre ntState.wildL - 2 *lastcurre ntState.boat;curre ntState.churchR =lastcurre ntState.churchR;curre ntState.wild

9、R =lastcurre ntState.wildR + 2 *lastcurre ntState.boat;curre ntState.boat =-lastcurre ntState.boat;last Parameters .p ush_back(curre ntState);operation , 0);CvsWdfs(curre ntState,last Parameters ,last Parameters .po p_back();operation .pop_back();/ 一個(gè)野人，一個(gè)傳教士if ( lastcurrentState.boat = 1)左岸- 右岸);op

10、eration .push_back( 11 |else右岸- 左岸)；operation .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.boat;curre ntS

11、tate.wildR =lastcurre ntState.wildR + 1 * lastcurre ntState .boat;curre ntState.boat =-lastcurre ntState.boat;last Parameters .p ush_back(curre ntState);CvsWdfs(curre ntState,last Parameters,operation , 0);operation .pop_back();last Parameters .po p_back();/ 一個(gè)傳教士過河if ( lastcurrentState.boat = 1)ope

12、ration .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 ntState.boat;curre ntState.wildR =lastcurre

13、ntState.wildR;curre ntState.boat =-lastcurre ntState.boat;last Parameters .p ush_back(curre ntState);CvsWdfs(curre ntState,last Parameters ,operation , 0);operation .pop_back();last Parameters .po p_back();/ 一個(gè)野人過河if ( lastcurrentState.boat = 1)operation .push_back( 01 |左岸- 右岸);elseoperation .push_b

14、ack( 01 |右岸- 左岸);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.wildR + 1 *lastcurre ntState.boat;curre ntState.boat =-lastcurre ntState.

15、boat;last Parameters .p ush_back(curre ntState);,operation , 0);CvsWdfs(curre ntState, last Parametersoperation .pop_back();last Parameters .po p_back(); return 0; | int mai n0/分別用來計(jì)算左岸和右岸的傳教士int churchL = 3, wildL = 3, churchR = 0, wildR = 0;和野人vector last Parameters; /保存每一步移動(dòng)操作的兩岸傳教士、野人人數(shù) vector o

16、peration; /保存當(dāng)前操作的描述/初始化左岸參數(shù)，可以認(rèn)為是從右岸移動(dòng)至左岸的操作/boat=-1表示船在左岸，boat=1表示船在右岸riverSides curre ntState;curre ntState.churchL = 3;curre ntState.wildL = 3;curre ntState.churchR = 0;curre ntState.wildR = 0;curre ntState.boat = 1;last Parameters .p ush_back(curre ntState);CvsWdfs(curre ntState, last Parameters, op erati on, 0);last Parameters .po p_back();system(pause); return 0;4程序結(jié)果最終得到如圖2、3所示的四種過河方式。t D:替習(xí)赍料個(gè)人C#工程療碼傳教士與野人過J氓De bu 9傳就士與野人遡可,EXE貳羣右左右左右左右左右 / 2右左右左右左右左右左 可 述人功野21210101201