资源预览内容
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
第9页 / 共16页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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)函数接口规格说明void Linkinit(Link *head)void insertson(Link *head, DataType x)void insertbro(Link *head,DataType x)int boatcase(DataType x,int n) void guangdu(Link *p,int n,int c)int safe(DataType x,int n)void print(Link *q,Link *p)2.3 详细设计 生成模块int boatcase(DataType x,int n) int i=0,a,b,t=0; if(x.cw) a=0;b=n-a; while (a+b=1) t+; while (b=0) arrayi.xds=a; arrayi.yr=b; i+; a+; b-; a=0; b=n-a-t; else a=1;b=0;t=0; while (a+b=0) arrayi.xds=a*(-1); arrayi.yr=b*(-1); i+; a-; b+; a=array0.xds*(-1)+t; b=0; return i; 安全检测模块int safe(DataType x,int n) if (x.xds=x.yr|x.xds=0)&(n-x.xds)=(n-x.yr)|x.xds=n)&x.xds=0&x.xds=0&x.yrson; while (q!=NULL)/ flag1=0; j=boatcase(q-data,c); for (i=0;idata.xds-arrayi.xds; tem.yr=q-data.yr-arrayi.yr; tem.cw=1-q-data.cw; t=q; if (safe(tem,n) flag2=1;/1 while (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; else insertbro(q,tem); if (tem.xds=0&tem.yr=0&tem.cw=0) print(q,p); count+; q=q-next; if (count=0) printf(无法成功渡河!n); else printf(有%d种渡河方式。n,count); 输出模块void print(Link *q,Link *p) DataType a100; int i=1; a0.cw=0; a0.xds=0; a0.yr=0; while (q!=p) ai+=q-data; q=q-par; while (-i)-1) printf( %d %d %d ),ai.xds,ai.yr,ai.cw); if (!(ai.xds=0&ai.yr=0&ai.cw=0) if(ai.cw=1)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号