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

传教士与野人过河问题实验报告1问题定义河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢？2算法分析首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。初始状态：（3,3,0,0,0，-1）目标状态：（0，0，3，3，1）然后，整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士根据船的位置，向左移或向右移通过递归依次执行5种算符，判断是否找到所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归函数流程图。数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。structriverSides{intchurchL;//左岸传教士数intwildL;//左岸野人数intchurchR;//右岸传教士数intwildR;//右岸野人数intboat;//船的位置，-1在左岸，1在右岸};图1传教士与野人过河递归函数流程图3编程实现程序使用C++实现，具体代码如下：#includeiostream#includevector#includestringusingnamespacestd;structriverSides{intchurchL;//左岸传教士数intwildL;//左岸野人数intchurchR;//右岸传教士数intwildR;//右岸野人数intboat;//船的位置，-1在左岸，1在右岸};intmycount=0;//统计成功过河次数intCvsWdfs(riverSideslastcurrentState,vectorriverSideslastParameters,vectorstringoperation,intifboacurrentStatety){if(lastcurrentState.churchR==3&&lastcurrentState.wildR==3){mycount++;cout第mycount次成功过河endl;cout传教士野人|移动方向endl;for(inti=0;ioperation.size();i++){coutoperation[i]endl;}coutendl;return0;}//判断过河操作否重复，去除死循环for(inti=0;ilastParameters.size()-1;i++){if(lastParameters[i].wildL==lastcurrentState.wildL&&lastParameters[i].churchL==lastcurrentState.churchL){if(lastcurrentState.boat==lastParameters[i].boat)return0;}}//检验人数数据合法性if(lastcurrentState.churchL0||lastcurrentState.wildL0||lastcurrentState.churchR0||lastcurrentState.wildR0)return0;//传教士是否被吃if((lastcurrentState.churchLlastcurrentState.wildL&&lastcurrentState.churchL!=0)||(lastcurrentState.churchRlastcurrentState.wildR&&lastcurrentState.churchR!=0))return0;//递归执行五类过河操作，boat=-1船在左岸，boat=1船在右岸，传入boat为上一次船位置//下次应当取反riverSidescurrentState;//两个传教士过河if(lastcurrentState.boat==1)operation.push_back(20|左岸-右岸);elseoperation.push_back(20|右岸-左岸);currentState.churchL=lastcurrentState.churchL-2*lastcurrentState.boat;currentState.wildL=lastcurrentState.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.pop_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.wildR=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(11|左岸-右岸);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=lastcurrentState.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|左岸-右岸);elseoperation.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.boat;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;currentState.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,lastParameters,operation,0);operation.pop_back();lastParameters.pop_back();return0;}intmain(){intchurchL=3,wildL=3,churchR=0,wildR=0;//分别用来计算左岸和右岸的传教士和野人vectorriverSideslastParameters;//保存每一步移动操作的两岸传教士、野人人数vectorstringoperation;//保存当前操作的描述//初始化左岸参数，可以认为是从右岸移动至左岸的操作//boat=-1表示船在左岸，boat=1表示船在右岸riverSidescurrentState;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