传教士过河问题(实验二)

1、精选优质文档-倾情为你奉上传教士过河问题实验报告计研-12 15 宋玲玲1实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。2实验内容从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。3实验原理及方法假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论:A、n>m/2。此种情况下，先把所有的野人度过去，每次返回一个野人，当出现(m,0

2、,0)情况时，返回m-n个野人(若m=n,返回1个野人)。然后渡n个传教士，此时野人=传教士，然后返回一个野人和传教士，再开始最大限度的渡传教士，每次返回一个野人,最终直到a=b=c=0；B、n<=3&&n<=m/2 | n=1，显然此时无解；C、n>=4&&n<=m/2，此时只能每次传n/2个传教士和野人,每次返回一个野人和传教士,直到最终结果。程序流程图如下：4、源程序清单：本程序用C+语言编写。#include "iostream"using namespace std;bool flag = false;/标记

3、是否有解bool af = false;/标记a是否为0bool bf = false;/当b变为0后赋值为true;bool ef = false;/当a=b后赋值为truebool f = false;/判断n是否大于m/2int m;/传教士野人的个数int n;/船一次能装载的人数void mc(int a,int b,int c);int main()cout<<"传教士与野人过河问题。n假设最初时传教士与野人在河的右岸。n"cout<<"请输入传教士野人的个数：n"cin>>m;cout<<&q

4、uot;请输入船一次能装载的人数: n"cin>>n;cout<<"右岸传教士人数t"<<"右岸野人个数t"<<"船的位置（1.右岸 0左岸）"<<endl;if(m<=3 && n<=m/2) | n=1)/此种情况无解cout<<"No solution!n"system("pause");return 0;if(n > m/2)f = true;mc(m,m,1);if(fl

5、ag = true)cout<<"Success!n"elsecout<<"No solution!n"system("pause");return 0; void mc(int a,int b,int c)if(flag=true) return;if(c = 1)cout<<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(f=t

6、rue)/如果n>m/2if(bf!=true)/b未达到过0if(a+b<=n)/如果a+b<=n,完全渡过mc(0,0,1-c);/递归elsefor(int j = n;j >= 0;j-)if(b >= j)mc(a,b-j,1-c);/递归if(flag=true) return;else if(ef!=true&& af=false)for(int i = n;i>=0;i-)if(a>=i)mc(a-i,b,1-c);/递归if(flag=true) return;if(ef = true && af=fa

7、lse)if(a>=n)mc(a-n,b,1-c);/递归else if(a+b<n)mc(0,0,1-c);elsemc(0,b-(n-a),1-c);if(af=true)if(b>=n)mc(a,b-n,1-c);/递归elsemc(a,0,1-c);else mc(a-n/2,b-n/2,1-c); /递归if(c = 0)cout<<"t"<<a<<"tt"<<b<<"tt"<<c<<"tn"if(a =

8、 b && b = c && a = 0)flag = true;return;if(f=true)/如果n>m/2if(b=0)bf = true;if(m <= n)mc(a,b+1,1-c);/递归elsemc(a,b+m-n,1-c);if(a=b)ef = true;mc(a+1,b+1,1-c);/递归if(a = 0)af = true;mc(a,b+1,1-c);/递归while(bf!=true)mc(a,b+1,1-c);/递归else/k<=n/2&&k>3mc(a+1,b+1,1-c);/递归 5、实验结果及分析。程序实验结果如下图。当然，传教士与野人个数为3，船一次能载两个人，这是最经典的例子。本程序也可输入其