目录

题目：实验步骤：实现代码：

题目：

有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。

实验步骤：

输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。 输出：若问题无解，则显示Failed，否则，显示Successed输出所有可行方案，并标注哪一组是最佳方案。用三元组(X1, X2, X3)表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态->中间状态->目标状态。 例：当输入n=2，c=2时，输出：221->200->211->010->021->000； 其中：X1表示起始岸上的牧师人数；X2表示起始岸上的野人人数；X3表示小船现在位置(1表示起始岸，0表示目的岸)。 要求：写出算法的设计思想和源程序，并有用户界面实现人机交互（控制台或者窗口都可以），进行输入和输出结果，如： Please input n: 2 Please input c: 2 Optimal Procedure: 221->200->211->010->021->000 Successed or Failed?: Successed

实现代码：

#include<stdio.h> #include<iostream> #include<stdlib.h> using namespace std; struct State { int Lsavage; int Lgodfather; int Rsavage; int Rgodfather; int boat; //boat at left = 0 ; boat at right =1; }; struct State *States = new State[150]; struct routesave { int savage; int godfather; }; struct routesave* routesaves = new routesave[150]; int godfather, savage, boatnum; void init(State &m) { cout << "请输入野人和牧师的人数n， 以及船的最大载量c"<<endl; int n, c; cin >> n >> c; m.Rgodfather = n; m.Rsavage = n; godfather = n, savage = n; boatnum = c; m.Lgodfather = m.Lsavage = 0; m.boat = 1; } void boaloading(int i, int s, int g) { //s个野人和g个传教士 if (States[i].boat == 0) { routesaves[i].savage = s*-1; //左边到右边是负数个野人 routesaves[i].godfather = g * -1; //左边到右边负数个传教士 States[i + 1].Lsavage = States[i].Lsavage - s; States[i + 1].Lgodfather = States[i].Lgodfather - g; States[i + 1].Rsavage = States[i].Rsavage + s; States[i + 1].Rgodfather = States[i].Rgodfather + g; States[i + 1].boat = 1; } else { routesaves[i].savage = s; //右边到左边是正数个野人 routesaves[i].godfather = g; //右边到左边正数个传教士 States[i + 1].Rsavage = States[i].Rsavage-s; States[i + 1].Rgodfather = States[i].Rgodfather - g; States[i + 1].Lsavage = States[i].Lsavage + s; States[i + 1].Lgodfather = States[i].Lgodfather + g; States[i + 1].boat = 0; } } bool checkState(State m) { if (m.Rgodfather > 0 && m.Rgodfather < m.Rsavage) return false; if (m.Lgodfather > 0 && m.Lgodfather < m.Lsavage) return false; else return true; } void showSolution(int i) { cout << "问题解决，解决路径为："<<endl; for (int c = 0; c < i; c++) { if (routesaves[c].savage >= 0) cout << "第" << c+1 << "步，" << routesaves[c].savage << "个野人和" << routesaves[c].godfather << "个传教士乘船去左边" << endl; else cout << "第" << c+1 << "步，" << routesaves[c].savage * -1 << "个野人和" << routesaves[c].godfather * -1 << "个传教士乘船去有右边"<< endl; } } void nextstep(int i) { int c; if (i >= 150) { cout <<"试探路径过大，无法计算"; exit(0); } for (c = 0; c < i; c++) /*if the current state is same to previous,retrospect*/ { if (States[c].Lsavage == States[i].Lsavage && States[c].Lgodfather == States[i].Lgodfather && States[c].Rsavage == States[i].Rsavage && States[c].Rgodfather == States[i].Rgodfather && States[c].boat == States[i].boat) { goto a; } } if (States[i].Rsavage == 0 && States[i].Rgodfather == 0 && States[i].boat == 0) { showSolution(i); exit(0); } if (States[i].boat == 1) { //船在右边 for (int s = 1; s <= boatnum && s<=States[i].Rsavage; s++) {//g=0 int g = 0; boaloading(i, s, g); if (checkState(States[i+1])) { nextstep(i+1); } } for (int g = 1; g <= boatnum && g<=States[i].Rgodfather; g++) { //g!=0 for (int s = 0; s <= boatnum - g && s<=States[i].Rsavage && s<=g; s++) { boaloading(i, s, g); if (checkState(States[i + 1])) { nextstep(i + 1); } } } } if (States[i].boat == 0) { //船在左边 for (int s = 1; s <= boatnum && s <= States[i].Lsavage; s++) {//g=0 int g = 0; boaloading(i, s, g); if (checkState(States[i + 1])) { nextstep(i + 1); } } for (int g = 1; g <= boatnum && g <= States[i].Lgodfather; g++) { //g!=0 for (int s = 0; s <= boatnum - g && s <= States[i].Lsavage && s <= g; s++) { boaloading(i, s, g); if (checkState(States[i + 1])) { nextstep(i + 1); } } } } a:return; } void main() { init(States[0]); nextstep(0); }

实验结果展示：