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所示为递归函数流程图。数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。struct riverSides int churchL;/左岸传教士数int wildL;/左岸野人数int churchR; /右岸传教士数int wildR; /右岸野人数int boat;/船的位置，-1在左岸，1在右岸;图 1 传教士与野人过河递归函数流程图3 编程实现程序使用C+实现，具体代码如下：#include#include#includeusing namespace std;struct riverSidesint churchL;/左岸传教士数int wildL;/左岸野人数int churchR; /右岸传教士数int wildR; /右岸野人数int boat;/船的位置，-1在左岸，1在右岸;int mycount = 0;/统计成功过河次数int CvsWdfs(riverSides lastcurrentState, vector lastParameters, vector operation, int ifboacurrentStatety)if (lastcurrentState.churchR = 3 & lastcurrentState.wildR = 3)mycount+;cout 第 mycount 次成功过河 endl;cout 传教士 野人 | 移动方向 endl;for (int i = 0; i operation.size(); i+)cout operationi endl;cout endl;return 0;/判断过河操作否重复，去除死循环for (int i = 0; i lastParameters.size() - 1; i+)if (lastParametersi.wildL = lastcurrentState.wildL&lastParametersi.churchL = lastcurrentState.churchL)if (lastcurrentState.boat = lastParametersi.boat)return 0;/检验人数数据合法性if (lastcurrentState.churchL 0 | lastcurrentState.wildL 0 | lastcurrentState.churchR 0 | lastcurrentState.wildR 0)return 0;/传教士是否被吃if (lastcurrentState.churchL lastcurrentState.wildL&lastcurrentState.churchL != 0) | (lastcurrentState.churchR 右岸);elseoperation.push_back( 2 0 | 右岸-左岸);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( 0 2 | 左岸-右岸);elseoperation.push_back( 0 2 | 右岸-左岸);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( 1 1 | 左岸-右岸);elseoperation.push_back( 1 1 | 右岸-左岸);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( 1 0 | 左岸-右岸);elseoperation.push_back( 1 0 | 右岸-左岸);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( 0 1 | 左岸-右岸);elseoperation.push_back( 0 1 | 右岸-左岸);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();return 0;int main()int churchL = 3, wildL = 3, churchR = 0, wildR = 0;/分别用来计算左岸和右岸的传教士和野人vector lastParameters;/保存每一步移动操作的两岸传教士、野人人数vector operation;/保存当前操作的描述/初始化左岸参数，可以认为是从右岸移动至左岸的操作/boat=-1 表示船在左岸，boat=1表示船在右岸riverSides currentState;currentState.churchL = 3;currentState.wildL = 3;currentState.churchR