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

传教士过河问题实验报告计研-122012312120115宋玲玲1．实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。2．实验内容从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。3．实验原理及方法假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论:A、nm/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个传教士和野人,每次返回一个野人和传教士,直到最终结果。程序流程图如下：是否(m=3&&n=m/2)||n==1失败结束输入传教士和野人的个数m输入船一次能载的人数n船是否在右岸YNNN是否已经成功是否nm/2成功结束Y是否nm/2NY递归执行NY右岸野人个数是否为0船是否能一次把右岸的人载完成功结束NY递归执行Y是否右岸传教士和接人个数不相等并且不为0递归执行YN是否右岸传教士和接人个数相等并且不为0N递归执行Y是否右岸传教士人数为0NY递归执行右岸传教士个数是否为0NY开始分情况递归执行递归执行NYN4、源程序清单：本程序用C++语言编写。#includeiostreamusingnamespacestd;boolflag=false;//标记是否有解boolaf=false;//标记a是否为0boolbf=false;//当b变为0后赋值为true;boolef=false;//当a==b后赋值为trueboolf=false;//判断n是否大于m/2intm;//传教士野人的个数intn;//船一次能装载的人数voidmc(inta,intb,intc);intmain(){cout传教士与野人过河问题。\n假设最初时传教士与野人在河的右岸。\n;cout请输入传教士野人的个数：\n;cinm;cout请输入船一次能装载的人数:\n;cinn;cout右岸传教士人数\t右岸野人个数\t船的位置（1.右岸0左岸）endl;if((m=3&&n=m/2)||n==1)//此种情况无解{coutNosolution!\n;system(pause);return0;}if(nm/2)f=true;mc(m,m,1);if(flag==true){coutSuccess!\n;}else{coutNosolution!\n;}system(pause);return0;}voidmc(inta,intb,intc){if(flag==true)return;if(c==1){cout\ta\t\tb\t\tc\t\n;if(f==true)//如果nm/2{if(bf!=true)//b未达到过0{if(a+b=n)//如果a+b=n,完全渡过mc(0,0,1-c);//递归else{for(intj=n;j=0;j--){if(b=j){mc(a,b-j,1-c);//递归if(flag==true)return;}}}}elseif(ef!=true&&af==false){for(inti=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);//递归elseif(a+bn)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\ta\t\tb\t\tc\t\n;if(a==b&&b==c&&a==0){flag=true;return;}if(f==true)//如果nm/2{if(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&&k3mc(a+1,b+1,1-c);//递归}}5、实验结果及分析。程序实验结果如下图。当然，传教士与野人个数为3，船一次能载两个人，这是最经典的例子。本程序也可输入其它数据，同样可以得到正确结果。本程序主要采用状态空间法和递归调用来解决问题。程序在一开始就排除了不可能会成功的状态空间，也对剩下的状态空间也进行了分类，这样直接减少了问题的复杂程度。另外，本程序大量采用递归调用的思想，减少了编程代码的工作量。