《C实现传教士与野人过河问题实验报告》由会员分享，可在线阅读，更多相关《C实现传教士与野人过河问题实验报告（5页珍藏版）》请在装配图网上搜索。
1、传教士与野人过河问题实验报告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 所示为递归函数流程图。数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。structriverSidesintchurchL;/ 左岸传教士数intwildL;/ 左岸野人数intchurch
3、R;/右岸传教士数intwildR;/ 右岸野人数intboat;/ 船的位置， -1 在左岸， 1在右岸;图 1传教士与野人过河递归函数流程图3 编程实现程序使用 C+ 实现，具体代码如下：#include #include #include using namespace std;structriverSidesintchurchL;/ 左岸传教士数intwildL;/ 左岸野人数intchurchR;/ 右岸传教士数intwildR;/ 右岸野人数intboat;/船的位置， -1 在左岸， 1在右岸;intmycount = 0;/ 统计成功过河次数intCvsWdfs( riverS
4、ideslastcurrentState,vector lastParameters,vector operation,intifboacurrentStatety)if( lastcurrentState.churchR = 3 &lastcurrentState.wildR = 3)mycount+;cout 第 mycount 次成功过河 endl;cout 传教士野人 |移动方向 endl;for ( inti = 0; i operation.size(); i+)cout operationi endl;cout endl;return0;/ 判断过河操作否重复，去除死循环for
5、( int i = 0; i lastParameters .size() - 1; i+)if( lastParametersi.wildL =lastcurrentState.wildL& lastParametersi.churchL =lastcurrentState.churchL)if( lastcurrentState.boat =lastParametersi.boat)return0;/ 检验人数数据合法性if( lastcurrentState.churchL 0 |lastcurrentState.wildL 0 |lastcurrentState.churchR 0|l
6、astcurrentState.wildR 0)return0;/ 传教士是否被吃if(lastcurrentState.churchL lastcurrentState.wildL& lastcurrentState.churchL != 0) |( lastcurrentState.churchR 右岸 );elseoperation .push_back( 20|右岸-左岸 );currentState.churchL =lastcurrentState.churchL - 2 *lastcurrentState.boat;currentState.wildL =lastcurrentS
7、tate.wildL;currentState.churchR =lastcurrentState.churchR + 2 *lastcurrentState.boat;currentState.wildR =lastcurrentState.wildR;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState,lastParameters, operation , 0);operation .pop_back();lastParameters.p
8、op_back();/ 两个野人过河if ( lastcurrentState.boat = 1)operation .push_back( 02|左岸-右岸 );elseoperation .push_back( 02|右岸-左岸 );currentState.churchL =lastcurrentState.churchL;currentState.wildL =lastcurrentState.wildL - 2 *lastcurrentState.boat;currentState.churchR =lastcurrentState.churchR;currentState.wild
9、R =lastcurrentState.wildR + 2 *lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState,lastParameters ,operation, 0);lastParameters.pop_back();operation .pop_back();/ 一个野人，一个传教士if ( lastcurrentState.boat = 1)operation .push_back( 1
10、1|左岸-右岸 );elseoperation .push_back( 11|右岸-左岸 );currentState.churchL =lastcurrentState.churchL - 1 *lastcurrentState.boat;currentState.wildL =lastcurrentState.wildL - 1 *lastcurrentState.boat;currentState.churchR =lastcurrentState.churchR + 1 *lastcurrentState.boat;currentState.wildR =lastcurrentStat
11、e.wildR + 1 *lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState,lastParameters, operation , 0);operation .pop_back();lastParameters.pop_back();/ 一个传教士过河if ( lastcurrentState.boat = 1)operation .push_back( 10|左岸-右岸 );elseoperat
12、ion .push_back( 10|右岸-左岸 );currentState.churchL =lastcurrentState.churchL - 1 *lastcurrentState.boat;currentState.wildL =lastcurrentState.wildL;currentState.churchR =lastcurrentState.churchR + 1 *lastcurrentState.boat;currentState.wildR =lastcurrentState.wildR;currentState.boat = -lastcurrentState.b
13、oat;lastParameters.push_back(currentState);CvsWdfs(currentState,lastParameters ,operation , 0);operation .pop_back();lastParameters.pop_back();/ 一个野人过河if ( lastcurrentState.boat = 1)operation .push_back( 01|左岸-右岸 );elseoperation .push_back( 01|右岸-左岸 );currentState.churchL =lastcurrentState.churchL;c
14、urrentState.wildL =lastcurrentState.wildL - 1 *lastcurrentState.boat;currentState.churchR =lastcurrentState.churchR;currentState.wildR =lastcurrentState.wildR + 1 *lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState,lastParamet
15、ers,operation, 0);operation .pop_back();lastParameters.pop_back();return0;int main()int churchL = 3, wildL = 3, churchR = 0, wildR = 0;/ 分别用来计算左岸和右岸的传教士和野人vector lastParameters;/保存每一步移动操作的两岸传教士、野人人数vector operation;/保存当前操作的描述/ 初始化左岸参数，可以认为是从右岸移动至左岸的操作/boat=-1表示船在左岸， boat=1 表示船在右岸riverSidescurrentSta
16、te;currentState.churchL = 3;currentState.wildL = 3;currentState.churchR = 0;currentState.wildR = 0;currentState.boat = 1;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters,operation, 0);lastParameters.pop_back();system( pause );return0;4 程序结果最终得到如图 2、 3 所示的四种过河方式。图 2过河方式 1、2图 3过河方式 3、4
C实现传教士与野人过河问题实验报告
