传教士与野人过河问题.doc

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.25M 资料格式：doc 举报版权申诉

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第1页.png

第1页 / 共6页

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第2页.png

第2页 / 共6页

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第3页.png

第3页 / 共6页

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第4页.png

第4页 / 共6页

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第5页.png

第5页 / 共6页

9d4226bd-4ff6-4279-b168-d981a3b955a7.doc.pdf-第6页.png

第6页 / 共6页

文本预览

人工智能实验报告班级：计研-12 班学号：2012312120105 姓名：孔德星

实验二知识表示方法 1．实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2 个实验内容可以选择 1 个实现）（1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；（2）状态空间法实验。从前有一条河，河的左岸有 m 个传教士、m 个野人和一艘最多可乘 n 人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求（1）简述实验原理及方法，并请给出程序设计流程图。实验原理：假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论: A、n>m/2。此种情况下，先把所有的野人度过去，每次返回一个野人，当出现(m,0,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 个传教士和野人,每次返回一个野人和传教士,直到最终结果。程序流程图：

（2）源程序清单：本程序用 C++语言编写。 #include "iostream" using namespace std; bool flag = false; bool af = false; bool bf = false; bool ef = false; bool f = false; int m;//传教士野人的个数 int n;//船一次能装载的人数 void mc(int a,int b,int c); int main() { //标记是否有解 //标记a是否为0 //当b变为0后赋值为true; //当a==b后赋值为true //判断n是否大于m/2 cout<<"传教士与野人过河问题。\n假设最初时传教士与野人在河的右岸。\n"; cout<<"请输入传教士野人的个数：\n"; cin>>m; cout<<"请输入船一次能装载的人数: \n"; cin>>n; cout<<"右岸传教士人数\t"<<"右岸野人个数\t"<<"船的位置（1.右岸 0左岸）"< m/2) f = true; mc(m,m,1);

if(flag == true){ cout<<"Success!\n"; } else{ cout<<"No solution!\n"; } system("pause"); return 0; } { void mc(int a,int b,int c) if(flag==true) if(c == 1) { return; cout<<"\t"<m/2 if(bf!=true) //b未达到过0 { if(a+b<=n) //如果a+b<=n,完全渡过 mc(0,0,1-c); //递归 else { for(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==false) { if(a>=n) mc(a-n,b,1-c); //递归

else if(a+b=n) else mc(a,b-n,1-c); mc(a,0,1-c); } //递归 } else{ mc(a-n/2,b-n/2,1-c); //递归 } } if(c == 0) { cout<<"\t"<m/2 { } bf = true; if(m <= n) mc(a,b+1,1-c); //递归 else mc(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 mc(a+1,b+1,1-c); //递归 //k<=n/2&&k>3 } } （3）实验结果及分析。程序实验结果如下图。当然，传教士与野人个数为 3，船一次能载两个人，这是最经典的例子。本程序也可输入其它数据，同样可以得到正确结果。本程序主要采用状态空间法和递归调用来解决问题。程序在一开始就排除了不可能会成功的状态空间，也对剩下的状态空间也进行了分类，这样直接减少了问题的复杂程度。另外，本程序大量采用递归调用的思想，减少了编程代码的工作量，也增加了我对人工智能算法的熟悉度。本程序基本上达到了实验的最初要求。不仅如此，通过对本程序的编写，提高了我对人工智能思想的掌握程度和学习兴趣，相信在以后我更会经常地用人工智能的思想去研究算法，编写程序。

分享到：

赞收藏

资料库

传教士与野人过河问题.doc

相关推荐

课程资源

热门标签

最新资料