修道士与野人问题

6．修道士与野人问题这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸一边。采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。（2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。（3）输出数据若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态。若问题无解，则给出“渡河失败”的信息。（4）求出所有的解。1．需求分析有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。用三元组（x1,x2,x3）来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态，若问题无解，则给出“渡河失败”的信息。2．设计2.1设计思想（1）数据结构设计逻辑结构设计:图型结构存储结构设计:链式存储结构采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。（2）算法设计算法设计的总体设计思路为：在得到修道士人数和小船的容纳人数后，用boatcase得到所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表示法，将去对面的路作为孩子结点，路与路是兄弟关系，到达另一边时，同样以这种方法，直到找到（0，0,0）。主要分为4个模块:boatcase生成所有情况，BFS得到边数最少的最佳方案，safe安全性检测，print输出安全渡河的全过程。各个模块要完成的主要功能分别为：生成模块：生成所有的可能渡河情况安全检测模块：对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况广度搜索模块：采用广度搜索法，得到首先搜索到的边数最少的一条通路输出模块：输出所有安全渡河的全过程主程序的流程图:调用函数Linkinit()来进行初始化调用函数Insertson()来插入结点调用函数guangdu()调用函数print()2.2设计表示（1）函数调用关系图guangduboatcasesafeinsertsoninsertbroprint建立邻接表把初始状态插入邻接表中进行广搜找到成功的方案打印输出各种方案（2）函数接口规格说明voidLinkinit(Link**head)voidinsertson(Link*head,DataTypex)voidinsertbro(Link*head,DataTypex)intboatcase(DataTypex,intn)voidguangdu(Link*p,intn,intc)intsafe(DataTypex,intn)voidprint(Link*q,Link*p)2.3详细设计生成模块intboatcase(DataTypex,intn){inti=0,a,b,t=0;if(x.cw){a=0;b=n-a;while(a+b=1){t++;while(b=0){array[i].xds=a;array[i].yr=b;i++;a++;b--;}a=0;b=n-a-t;}}else{a=1;b=0;t=0;while(a+b=n){t++;while(a=0){array[i].xds=a*(-1);array[i].yr=b*(-1);i++;a--;b++;}a=array[0].xds*(-1)+t;b=0;}}returni;}安全检测模块intsafe(DataTypex,intn){if((x.xds=x.yr||x.xds==0)&&((n-x.xds)=(n-x.yr)||x.xds==n)&&x.xds=0&&x.xds=n&&x.yr=0&&x.yr=n)return1;elsereturn0;}广度搜索模块voidguangdu(Link*p,intn,intc){Link*q,*t;DataTypetem;inti,flag1,flag2,g=0,j,count=0;q=p-son;while(q!=NULL)/{flag1=0;j=boatcase(q-data,c);for(i=0;ij;i++){tem.xds=q-data.xds-array[i].xds;tem.yr=q-data.yr-array[i].yr;tem.cw=1-q-data.cw;t=q;if(safe(tem,n)){flag2=1;//1while(t!=p){if(tem.xds==t-data.xds&&tem.yr==t-data.yr&&tem.cw==t-data.cw){flag2=0;break;}t=t-par;}if(flag2==1){if(flag1==0){insertson(q,tem);flag1=1;}elseinsertbro(q,tem);if(tem.xds==0&&tem.yr==0&&tem.cw==0){print(q,p);count++;}}}}q=q-next;}if(count==0)printf(无法成功渡河!\n);elseprintf(有%d种渡河方式。\n,count);}输出模块voidprint(Link*q,Link*p){DataTypea[100];inti=1;a[0].cw=0;a[0].xds=0;a[0].yr=0;while(q!=p){a[i++]=q-data;q=q-par;}while((--i)-1){printf((%d%d%d),a[i].xds,a[i].yr,a[i].cw);if(!(a[i].xds==0&&a[i].yr==0&&a[i].cw==0)){if(a[i].cw==1)printf(--(%d%d)--(%d%d0)\n,a[i].xds-a[i-1].xds,a[i].yr-a[i-1].yr,a[i-1].xds,a[i-1].yr);elseprintf(--(%d%d)--(%d%d1)\n,(a[i].xds-a[i-1].xds)*(-1),(-1)*(a[i].yr-a[i-1].yr),a[i-1].xds,a[i-1].yr);}}printf(渡河成功!\n);}3．调试分析（1）本题是采用邻接表做为存储结构，将各种状态之间的迁移图保存下来，并用孩子兄弟表示法，以实现广度搜索；刚编好程序时出现死循环的现象，例如：带过去2个野人又带回来2个野人，在和其他同学讨论后，采用了2个标志位来避免出现死循环的现象，在进行运行的时候，曾出现了打印输出错误，经过一步一步调试，发现在插入结点的时候出现了插入错误，即没有考虑到pre的改变，通过改正，重新运行检测，运行结果正确，在排版时通过一步步调试，参考了课本和老师的课件，并与和其他同学讨论后，终于通过调试和改正，，能够使输出结果很明显的渡河方案。（2）可改进内容：显示表示哪些是渡河次数最短的，最佳渡河方案一共有几种，并输出每种最佳渡河方案，另外，可尝试用深度优先搜索算法来找最佳方案。4．用户手册本程序在VC++6.0环境下运行，根据提示输入相应的渡河人数和小船能容纳的人数即可。5．测试数据及测试结果测试用例1测试输入：n=3,c=2测试目的：检验程序运行时是否会陷入死循环正确输出：见截屏1,2实际输出：见截屏3,4错误原因：未正确设置标志位，出现死循环现象当前状态：已改正截屏1截屏2截屏3截屏46．源程序清单#includestdio.h#includemalloc.h#includestdlib.htypedefstruct{intxds;//修道士个数intyr;//野人个数intcw;//船的位置}DataType;DataTypearray[50000];typedefstructnode//结构体定义{DataTypedata;structnode*son;//儿子structnode*bro;//兄弟structnode*par;//双亲structnode*next;}Link;voidLinkinit(Link**head)//初始化操作{*head=(Link*)malloc(sizeof(Link));//申请动态空间(*head)-son=NULL;(*head)-bro=NULL;(*head)-par=NULL;(*head)-next=NULL;}voidinsertson(Link*head,DataTypex)//在邻接表中插入儿子结点的操作{Link*q,*s;q=(Link*)malloc(sizeof(Link));q-data=x;head-son=q;//将x插入给头结点的儿子指针s=head;while(s-next!=NULL)s=s-next;q-par=head;q-son=NULL;q-bro=NULL;s-next=q;q-next=NULL;}voidinsertbro(Link*head,DataTypex)//在邻接表中插入兄弟结点的操作，//所有的兄弟结点都指向他们右边的结点{Link*q,*s;q=(Link*)malloc(sizeof(Link));s=head-son;q-data=x;while(s-bro!=NULL)s=s-bro;s-bro=q;s-next=q;q-next=NULL;q-bro=NULL;q-par=head;q-son=NULL;}intboatcase(DataTypex,intn)//生成所有情况；{inti=0,a,b,t=0;if(x.cw)//在此岸,上船的人多优先{a=0;b=n-a;//a为修道士b为野人while(a+b=1)//当船上有人时{t++;while(b=0)//当野人个数不为负数{array[i].xds=a;array[i].yr=b;i++;a++;b--;}a=0;//船上空位个数b=n-a-t;}}else//在对岸,上船的人少优先{a=1;b=0;t=0;while(a+b=n){t++;//船上的人数while(a=0){array[i].xds=a*(-1);array[i].yr=b*(-1);i++;a--;b++;}a=array[0].xds*(-1)+t;b=0;}}returni;//i为总数量}intsafe(DataTypex,intn)//安全性检测{//起始目的if((x.xds=x.yr||x.xds==0)&&((n-x.xds)=(n-x.yr)||x.xds==n)&&x.xds=0&&x.xds=n&&x.yr=0&&x.yr=n)return1;//船上修道士elsereturn0;}voidprint(Link*q,Link*p)//打印安全渡河的过程,当船到对岸时,把对岸当作其始岸,此岸当作彼岸{DataTypea[100];inti=1;a[0].cw=