传教士过河问题(实验二)_第1页
传教士过河问题(实验二)_第2页
传教士过河问题(实验二)_第3页
传教士过河问题(实验二)_第4页
传教士过河问题(实验二)_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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,船一次能载两个人,这是最经典的例子。本程序也可输入其

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论