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

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

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

3、 riversides intintintintint;3 編程實現(xiàn)程序使用C+實現(xiàn)，具體代碼如下:#inelude #inelude #inelude using namespacestd;structriversidesintehurehL;intint/左岸傳教士數(shù) 左岸野人數(shù)/右岸傳教士數(shù)intintwildL; /ehurehR;wildR; /右岸野人數(shù)boat; /船的位置，-1在左岸，1在右岸；myeount = 0;/統(tǒng)計成功過河次數(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;移動方向 endl;operation .size。； i+)eout operation i endl;eout en dl;return 0;|/判斷過河操作否重復，去除死循環(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;|/檢驗人數(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、;/兩個野人過河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();/ 一個野人，一個傳教士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();/ 一個傳教士過河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();/ 一個野人過河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/分別用來計算左岸和右岸的傳教士int churchL = 3, wildL = 3, churchR = 0, wildR = 0;和野人vector last Parameters; /保存每一步移動操作的兩岸傳教士、野人人數(shù) vector o

16、peration; /保存當前操作的描述/初始化左岸參數(shù)，可以認為是從右岸移動至左岸的操作/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程序結果最終得到如圖2、3所示的四種過河方式。t D:替習赍料個人C#工程療碼傳教士與野人過J氓De bu 9傳就士與野人遡可,EXE貳羣右左右左右左右左右 / 2右左右左右左右左右左 可 述人功野21210101201