修道士与野人问题

1、 3修道士与野人问题题目：这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。1. 需求分析题目要求：1) 用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0在目的岸，1在起始岸）。2) 采用广度搜索法，得到首先搜索到的边数最少的一条通路。3) 输出数据若问题有解（能渡过河去），则输出一

2、个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移： 初始状态中间状态目的状态4) 求出所有的解。5) 程序测试：用户输入修道士与野人个数以及一条船可容纳的人数，则程序输出可行的渡河状态图并输出最优解，程序最后给出可行解的个数。注意：1) 程序的输出格式严格按照三元组的形式，给出状态变迁图2) 必须采用广度搜索算法2. 设计2.1设计思想1) 存储结构a) 定义一个结构体，用于存放各个时刻的状态typedef struct int x1;/修道士int x2;/野蛮人int x3;/状态datatype;b) 用邻接表存储结构实现图的操作，其存储结构为：typedef s

3、truct nodeint dest;/邻接表的弧头结点序号struct node *next;edge;/邻接表单链表的结点结构体typedef structdatatype data;/结点数据元素int sorce;/邻接表的弧尾结点序号edge *adj;/邻接边的头指针int pre;/指向此点的点的序号adjlheight;/数组的数据元素类型结构体typedef structadjlheight a10000;/邻接表数组int numofverts;/结点个数int numofedges;/边个数adjlgraph;/邻接表结构体2) 基本思想由题意知，数据结构选用图较为合理，

4、题中图的结点数目较大且边的数目远小于相同结点的完全图的边数，因此采用图的邻接表存储结构效率较高根据给出的小船上的位置数量，生成小船上的安全状态，即在船上的时候修道士的人数也要比野人的数量要多（除非修道士人数为0）。让修道士跟野人上船后，检测当船到达对岸后，两岸修道士的安全状态，若修道士安全，则将此结点加入到邻接表中渡船优先规则：起始岸一次运走的人越多越好（即起始岸运多人优先），同时野人优先运走；目的岸一次运走的人越少越好（即目的岸运少人优先），同时修道士优先运走采用广度搜索法，得到首先搜索到的边数最少的一条通路3) 举例说明：当n=3;c=2时，可用树状图来表示运送过程并用广度搜索法来查找最佳

5、方案（f表示运过去之后右岸的总人数，p从始岸到对岸；0从对岸到始岸）f=3 q01f=2 p02f=1 q01f=1 q11f=1 p01f=2 p11（3，3，1）（3，2，0）（2，2，0）（3，1，0）（3，2，1）（3，0，0）f=3 p02（3，1，1）f=2 q01（1，1，0）f=4 p20（2，2，1）f=2 q11（1，1，0）f=4 p20（2，2，1）f=2 q111（0，2，0）f=4 p20（0，3，1）f=3 q01（0，1，1）f=5 p02（0，2，1）f=4 q01（0，0，0）f=3 q01（1，1，1）f=4 q102.2 设计表示法1) 过程或函数调用关

6、系图main work check print2) 基于数据结构的操作组该程序数据结构相对简单，只运用了邻接表结构的图，work()函数建立一个广度表，实现广度搜索算法；check()函数用于检查各个状态下修道士是否安全；print()函数打印安全渡河的过程3) 过程或函数接口规格说明void work(adjlgraph *p)/广搜建立表int check （datatype x) /检查当前情况下，修道士是否安全int print(adjlgraph *p,int g) /打印安全渡河的过程2.3函数详细设计1） 图的初始化void adjinitiate(adjlgraph *g)in

7、t i;g-numofedges=0;g-numofverts=0;for(i=0;iai.sorce=i; /*置邻接边的弧头结点序号*/g-ai.adj=null; /*置邻接边单链表头指针初值*/g-ai.data.x3=-1;g-ai.pre=-1;2） 在g图中插入结点void insertvertex(adjlgraph *g, int i, datatype vertex)if( i=0 & iai.data.x1=vertex.x1;g-ai.data.x2=vertex.x2;g-ai.data.x3=vertex.x3;g-numofverts+;else printf(结

8、点越界!n);3） 在g图中插入边void insertedge(adjlgraph *g,int v1,int v2)edge *p;if(v1=g-numofverts|v2g-numofverts)printf(参数v1或v2越界出错!);exit(0);p=(edge *)malloc(sizeof(edge);/*申请邻接边单链表结点空间*/p-dest=v2;/*置邻接边弧头序号*/p-next=g-av1.adj;/*新结点插入单链表的表头*/g-av1.adj=p;/*头指针指向新的单链表表头*/g-numofedges+;/*边个数加1*/4） g图的撤销void adjde

9、stroy(adjlgraph *g)int i;edge *p,*q;for(i=0;inumofverts;i+)p=g-ai.adj;while(p!=null)q=p-next;free(p);p=q;5） 检查当前情况下，修道士是否安全int check(datatype x) if (x.x1=x.x2|x.x1=0)&(n-x.x1)=(n-x.x2)|x.x1=n)&x.x1=0&x.x1=0&x.x2=1)t+;while (b=0)fai.x1=a;fai.x2=b;i+;a+;b-;a=0;b=c-a-t;else/从末岸到始岸的状态a=1;b=0;t=0;while (

10、a+b=0)fai.x1=a*(-1);fai.x2=b*(-1);i+;a-;b+; a=fa0.x1*(-1)+t;b=0;return i; 7） 打印安全渡河的过程int print(adjlgraph *p,int g) datatype b1000; int i=0; while (g!=-1) bi+=p-ag.data; g=p-ag.pre; while (-i)-1) printf( %d %d %d ),bi.x1,bi.x2,bi.x3); if (!(bi.x1=0&bi.x2=0&bi.x3=0) if (bi.x3=1)printf( ( %d %d ) ( %d

11、 %d 0 )n,bi.x1-bi-1.x1,bi.x2-bi-1.x2,bi-1.x1,bi-1.x2);else printf( ( %d %d ) ( %d %d 1 )n,(bi.x1-bi-1.x1)*(-1),(-1)*(bi.x2-bi-1.x2),bi-1.x1,bi-1.x2); else printf(n); printf(渡河成功!n);return 1;8） 广搜建立表void work(adjlgraph *p)/广搜建立表datatype tem;int i,flag1,g=0,j,count=0,k=0,t;while (p-ak.data.x3!=-1)j=fi

12、ndfa(p-ak.data); for (i=0;iak.data.x1-fai.x1;tem.x2=p-ak.data.x2-fai.x2;tem.x3=1-p-ak.data.x3;if (check(tem)flag1=1;t=k; while (t!=-1)if(tem.x1=p-at.data.x1&tem.x2=p-at.data.x2&tem.x3=p-at.data.x3)flag1=0;break; t-; if(flag1=1)g+;p-ag.pre=k;insertvertex(p,g,tem);insertedge(p,k,g);if (tem.x1=0&tem.x2

13、=0&tem.x3=0)count+;print(p,g);k+; if (count=0)printf(不能渡河!n);elseprintf(有%d种渡河方式。n,count);9） 主函数void main()adjlgraph g;datatype first; while(1)printf(*193112班 张玉彬*n*修道士与野人问题*n);printf(请输入野人和修道士人数n:);scanf(%d,&n) ;printf(请输入船可乘人数c:);scanf(%d,&c) ; adjinitiate(&g);first.x1=n;first.x2=n;first.x3=1;inse

14、rtvertex(&g, 0, first);work(&g); adjdestroy(&g);char choice; for(;) printf(是否继续？(y/n)n); scanf (%s , &choice); choice=toupper(choice);/toupper可将小写字母转化成大写的 if(choice=y) break; if(choice=n)exit(0); 3. 调试分析： 1)刚始不知道从何下手，就先举了一个简单例子，看当野人与修道士都是两人，船最多只能容纳二人时该怎么渡，我在本上画出了所有的方案，然后去想怎样去用程序来实现上述过程。再结合题目要求，根据课本上

15、的邻接表存储结构的知识，再去限定规则来实现渡河方案，脑中大概有了编程方向和较明确的模块建立的思路。 2) 较难的模块是考虑各种情况下保障修道士的安全，在此案，在彼岸，在船上，编写程序序来限定规则，虽然并不复杂，但我发现写得尽量完美并不容易。而在写建立广搜表程序时，真的是难为坏了，刚开始没考虑到设立一个标志符来避免死循环，结果就怎么也输不出正确结果，后来与同学讨论时受到启发，最后得以成功完成 3) 通过此次编程感觉收获了好多，首先不管自己感觉问题难易程度如何，都要按部就班，从最基本的做起，如没头绪时多试几组数据，然后回归课本知识来想解决方案，实在不会时不要轻言放弃，可以先与老师，同学多多交流，最后的方法才是上网查询参考，这样才能使自己编程能力得到真正的提高。4. 用户手册1) 本程序的运行环境为，microsoft visual c+6.0.2) 程序运行过程及说明：a) 进入演示程序后，出现提示信息：请输入野蛮人和修道士人数n:请输入船可乘人数c:b) 用户输入相关数据后，程序输出结果，并在终端显示出来5. 测试结果请输入野蛮人和修道士人数n: 3请输入船可乘人数c: 2运行结果如下：( 3 3 1 ) ( 0 2 ) ( 3 1 0 )( 3 1 0 ) ( 0 1 ) ( 3 2 1 )( 3 2 1 ) ( 0 2 ) ( 3