资源描述：
《修道士与野人问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实用文档6．修道士与野人问题这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸
2、一边。采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。（2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。（3）输出数据若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态。若问题无解，则给出“渡河失败”的信息。（4）求出所有的解。1．需求分析大全实用文档有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能
3、，则给出一个小船来回次数最少的最佳方案。用三元组（x1,x2,x3）来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态，若问题无解，则给出“渡河失败”的信息。2．设计2.1设计思想（1）数据结构设计逻辑结构设计:图型结构存储结构设计:链式存储结构采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条通路
4、，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。（2）算法设计算法设计的总体设计思路为：大全实用文档在得到修道士人数和小船的容纳人数后，用boatcase得到所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表示法，将去对面的路作为孩子结点，路与路是兄弟关系，到达另一边时，同样以这种方法，直到找到（0，0,0）。主要分为4个模块:boatcase生成所有情况，BFS得到边数最少的最佳方案，safe安全性检测，print输出安全渡河的全过程。各个模块要完成的主要功能分别为：生成模块：生成所有的可能渡河情况安全检测
5、模块：对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况广度搜索模块：采用广度搜索法，得到首先搜索到的边数最少的一条通路输出模块：输出所有安全渡河的全过程主程序的流程图:建立邻接表调用函数Linkinit()来进行初始化大全实用文档把初始状态插入邻接表中进行广搜找到成功的方案调用函数Insertson()来插入结点调用函数guangdu()打印输出各种方案调用函数print()2.2设计表示（1）函数调用关系图guangduboatcasesafeinsertsoninsertbroprint大全实用文档（2）函数接口规格说明void
6、Linkinit(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>=
7、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
8、
9、x.xds
10、==0)&&((n-x.xds)>=(n-x.yr)
11、
12、x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&
