传教士与野人过河问题实验报告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 { int churchL;// 左岸传教士数int wildL;// 左岸野人数int churchR; // 右岸传教士数int wildR; //右岸野人数int boat; // 船的位置， -1 在左岸， 1在右岸};图 1 传教士与野人过河递归函数流程图3 编程实现程序使用 C++ 实现，具体代码如下：#include #include #include usingnamespace std; structriverSides{ int churchL;// 左岸传教士数int wildL;// 左岸野人数int churchR; // 右岸传教士数int wildR; //右岸野人数int boat; // 船的位置， -1 在左岸， 1在右岸}; int mycount = 0;// 统计成功过河次数int CvsWdfs( riverSideslastcurrentState, vector < riverSides> lastParameters, vector operation, intifboacurrentStatety) { if ( lastcurrentState.churchR == 3 && lastcurrentState.wildR == 3) { mycount++; cout << " 第" << mycount << "次成功过河 " << endl; cout << " 传教士 野人 | 移动方向 " << endl; for ( int i = 0; i < operation .size(); i++...
