C++实现传教士与野人过河问题实验分析报告

1、C+模现传教士与野人过河问题 实验报告作者:日期:传教士与野人过河问题实验报告1问题定义河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢？2算法分析首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右 岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野 人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。初始状态：（3,3,0,0,0 ，-1）目标状态：（0，0，3，3，1）然后，整个问题就抽象成了怎样从初始状态经中间的

2、一系列状态达到目标状 态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下 5个算符（按照渡船方向的不同，也 可以理解为10个算符）：渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士根据船的位置，向左移或向右移通过递归依次执行 5种算符，判断是否找到 所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归 函数流程图。数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。struct riverSides int churchL; /左岸传教士数int wildL; /左岸野人数int churc

3、hR; /右岸传教士数int wildR; /右岸野人数int boat; /船的位置，-1在左岸，1在右岸;递归函数入口Cvsittdfss是否否旦反方向渡河2传教士过河2野人过范野人过汇1传教士过河结東4判断是否达 到目标状态当前状态人 数是否合理1传教士，野人过退季U断滾河也 件是否重复 邂免死循无图1传教士与野人过河递归函数流程图boat - -boat3 编程实现程序使用C+实现，具体代码如下：#inelude #inelude #inelude using namespaeestd;struct riverSidesint ehurehL; /左岸传教士数int wildL; /左

4、岸野人数int ehurehR; /右岸传教士数int wildR; /右岸野人数int boat; /船的位置，-1在左岸，1在右岸；int myeount = 0;/统计成功过河次数int CvsWdfs( riverSideslasteurrentState, veetor lastParametersveetor operation , int ifboaeurrentStatety )if ( lasteurrentState.ehurehR = 3 & lasteurrentState .wildR = 3)myeou nt+;eout 第 myeount 次成功过河 endl;e

5、out 传教士 野人| 移动方向 endl;for (int i = 0; i operation .size(); i+)eout operation i endl;eout en dl;return 0;/判断过河操作否重复，去除死循环for (int i = 0; i lastParameters .size() - 1; i+)i.ehurehLif (lastParameters i.wildL= lasteurrentState.wildL& lastParameters=lasteurre ntState .ehurehL)if ( lasteurrentState.boat =

6、 lastParameters i.boat)return 0;/检验人数数据合法性if ( lastcurrentState .churchL 0 |lastcurrentState.wildL 0 |lastcurre ntState .churchR 0 |lastcurre ntState.wildR 0)return 0;/传教士是否被吃if ( lastcurrentState .churchL lastcurrentState.wildL& lastcurrentState .churchL != 0)|( lastcurrentState .churchR 右岸”);elseo

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

8、lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(currentState, lastParameters , operation , 0);operation .pop_back();lastParameters .pop_back();/两个野人过河if ( lastcurrentState.boat = 1)operation .push_back(” 02 |左岸- 右岸”)；elseoperation .push_back(” 02 |右岸- 左岸”)；curre ntState.church

9、L = lastcurre ntState.churchL;curre ntState.wildL =lastcurre ntState.wildL - 2 *lastcurre ntState.boat;curre ntState.churchR = lastcurre ntState.churchR;curre ntState.wildR =lastcurre ntState.wildR + 2 *lastcurre ntState.boat;curre ntState.boat = -lastcurre ntState.boat;lastParameters .push_back(cur

10、rentState);CvsWdfs(currentState, lastParameters ,operation , 0);lastParameters .pop_back();operation .pop_back();/ 一个野人，一个传教士if ( lastcurrentState.boat = 1)operation .push_back( 11 |else左岸- 右岸);右岸- 左岸)；curre ntState.churchL =lastcurre ntState .churchL - 1 *lastcurre ntState.boat;curre ntState.wildL

11、=lastcurre ntState.wildL - 1 *lastcurre ntState.boat;curre ntState.churchR =lastcurre ntState .churchR + 1 *lastcurre ntState.boat;curre ntState.wildR =lastcurre ntState.wildR + 1 *lastcurre ntState.boat;curre ntState.boat =-lastcurre ntState.boat;operation .push_back( 11 |左岸- 右岸);右岸- 左岸);curre ntSt

12、ate.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.boat;CvsWdfs(curre ntState,

13、 operation .pop_back();lastParameters ,operation , 0);lastParameters .pop_back();/ 一个传教士过河if ( lastcurrentState.boat = 1)operation .push_back( 10 |左岸- 右岸)elseoperation .push_back( 10 |右岸- 左岸)curre ntState.churchL =lastcurre ntState.churchL - 1 *curre ntState.wildL =lastcurre ntState.wildL;curre ntSt

14、ate.churchR =lastcurre ntState.churchR + 1 *curre ntState.wildR =lastcurre ntState.wildR;curre ntState.boat =-lastcurre ntState.boat;lastParameters .push_back(currentState);CvsWdfs(curre ntState,lastParameters ,operation , 0);lastParameters .push_back(currentState);operation .pop_back();lastcurre nt

15、State.boat;lastcurre ntState.boat;lastParameters .pop_back();/ 一个野人过河if ( lastcurrentState.boat = 1)operation .push_back( 01 |elseoperation .push_back( 01 |lastParameters .push_back(currentState);CvsWdfs(currentState, lastParameters , operation , 0);operation .pop_back();lastParameters .pop_back();r

16、eturn 0;int mai n()/分别用来计算左岸和右岸的传教士int churchL = 3, wildL = 3, churchR = 0, wildR = 0;和野人vector lastParameters; /保存每一步移动操作的两岸传教士、野人人数 vector operation; /保存当前操作的描述/初始化左岸参数，可以认为是从右岸移动至左岸的操作/boat=-1表示船在左岸，boat=1表示船在右岸riverSides curre ntState;curre ntState.churchL = 3;curre ntState.wildL = 3;curre ntSta

17、te.churchR = 0;curre ntState.wildR = 0;curre ntState.boat = 1;lastParameters.push_back(curre ntState);CvsWdfs(curre ntState, lastParameters,operatio n, 0);lastParameters.pop_back();system( pause);return 0;最终得到如图2、3所示的四种过河方式D:学习资料个人O工程源码传教士与野人过冰De bu鼻传教士与野人过汨.*图2过河方式1、25抵ffi抵抵affIHt 贰事右左右左右左右左右 树ff-ff-$-ff-ff-ffi-ff-s-I-l: 丰左右左右左右左右左右左1010120102120011$r右左右左拿羣右左右树ff-ff-ff-s-I-lhs-s-I-k禾WW右左右左右WW可达人功野 21210101212