完整word版C实现传教士与野人过河问题实验报告

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

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

3、 riversides intintintintint;3 编程实现程序使用C+实现，具体代码如下:#inelude #inelude #inelude using namespacestd;structriversidesintehurehL;intint/左岸传教士数 左岸野人数/右岸传教士数intintwildL; /ehurehR;wildR; /右岸野人数boat; /船的位置，-1在左岸，1在右岸；myeount = 0;/统计成功过河次数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;|/判断过河操作否重复，去除死循环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;|/检验人数数据合法性(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; /保存每一步移动操作的两岸传教士、野人人数 vector o

16、peration; /保存当前操作的描述/初始化左岸参数，可以认为是从右岸移动至左岸的操作/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