《修道士与野人问题.docx》由会员分享，可在线阅读，更多相关《修道士与野人问题.docx（15页珍藏版）》请在三一办公上搜索。
1、修道士与野人问题6修道士与野人问题 这是一个古典问题。假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数。如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。 要求： 用一个三元组表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置。例如表示起始岸上有两个修道士，一个野人，小船在起始岸一边。 采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。 采用广度搜索法，得到首先搜索到的边数最少的一条通路。 输出数据 若
2、问题有解，则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移： 目的状态中间状态初始状态。 若问题无解，则给出“渡河失败”的信息。 求出所有的解。 1需求分析 有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。用三元组来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置。若问题有解，则输出一个最佳方案。用三元组表示渡河过程中的状态，并
3、用箭头指出这些状态之间的迁移：目的状态中间状态初始状态，若问题无解，则给出“渡河失败”的信息。 2设计 2.1 设计思想 数据结构设计 逻辑结构设计: 图型结构 存储结构设计: 链式存储结构 采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。 算法设计 算法设计的总体设计思路为：在得到修道士人数和小船的容纳人数后，用boatcase得到所有情况，然后再进行安全性检查，以减去修道士少于野人的情况，接着用孩子兄弟结点表示法，将去对面的路作为孩子结点，路与路是兄弟关系，到达另一边时，同样以这种方法，直到找到。主要分为
4、4个模块:boatcase生成所有情况，BFS得到边数最少的最佳方案，safe安全性检测，print输出安全渡河的全过程。 各个模块要完成的主要功能分别为： 生成模块：生成所有的可能渡河情况 安全检测模块：对所有的可能渡河情况进行安全检测，以减去修道士少于野人的情况 广度搜索模块：采用广度搜索法，得到首先搜索到的边数最少的一条通路 输出模块：输出所有安全渡河的全过程 主程序的流程图: 建立邻接表 调用函数 Linkinit( )来进行初始化 把 初 始 状 态 插 调用函数Insertson( )来插入结点 入邻接表中 进行广搜找到成 调用函数guangdu( ) 功的方案 打印输出各种方 案
5、 调用函数print( ) 2.2 设计表示 函数调用关系图 guangdu boatcase safe insertson print insertbro 函数接口规格说明 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 *
6、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; 安全检测模块
7、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&t
8、em.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) DataTyp
9、e 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) printf(-(%d %d)-(%d %d 0)n,ai.xds-ai-1.xds,ai.yr-ai-1.yr,ai-1.xds,ai-1.yr); else printf( - ( %d %d ) - ( %d %d 1 )n,(ai.xds
10、-ai-1.xds)*(-1),(-1)*(ai.yr-ai-1.yr),ai-1.xds,ai-1.yr); printf(渡河成功!n); 3调试分析 本题是采用邻接表做为存储结构，将各种状态之间的迁移图保存下来，并用孩子兄弟表示法，以实现广度搜索；刚编好程序时出现死循环的现象，例如：带过去2个野人又带回来2个野人，在和其他同学讨论后，采用了2个标志位来避免出现死循环的现象，在进行运行的时候，曾出现了打印输出错误，经过一步一步调试，发现在插入结点的时候出现了插入错误，即没有考虑到pre的改变，通过改正，重新运行检测，运行结果正确，在排版时通过一步步调试，参考了课本和老师的课件，并与和其他同
11、学讨论后，终于通过调试和改正，能够使输出结果很明显的渡河方案。 可改进内容：显示表示哪些是渡河次数最短的，最佳渡河方案一共有几种，并输出每种最佳渡河方案，另外，可尝试用深度优先搜索算法来找最佳方案。 4用户手册 本程序在VC+6.0环境下运行，根据提示输入相应的渡河人数和小船能容纳的人数即可。 5测试数据及测试结果 测试用例1 测试输入： n=3,c=2 测试目的： 检验程序运行时是否会陷入死循环 正确输出： 见截屏1,2 实际输出： 见截屏 3,4 错误原因： 未正确设置标志位，出现死循环现象 当前状态： 已改正 截屏1 截屏2 截屏3 截屏4 6源程序清单 #include #includ
12、e #include typedef struct int xds; /修道士个数 int yr; /野人个数 int cw; /船的位置 DataType; DataType array50000; typedef struct node/结构体定义 DataType data; struct node *son;/儿子 struct node *bro;/兄弟 struct node *par;/双亲 struct node *next; Link; void Linkinit(Link *head) /初始化操作 *head=(Link *)malloc(sizeof (Link); /
13、申请动态空间 (*head)-son=NULL; (*head)-bro=NULL; (*head)-par=NULL; (*head)-next=NULL; void insertson(Link *head, DataType x) /在邻接表中插入儿子结点的操作 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;
14、q-next=NULL; void insertbro(Link *head,DataType x)/在邻接表中插入兄弟结点的操作， /所有的兄弟结点都指向他们右边的结点 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; int boatcase(DataType x,int n) /生成所有情况； int i=0,a,b
15、,t=0; if(x.cw) /在此岸,上船的人多优先 a=0;b=n-a; /a为修道士b为野人 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; /i为总数量 int saf
16、e(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.yrdata;/将一次过河的情况给bi 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) printf(-(%d %d)-(%d %d 0)n,ai.xds-ai-1.xds,ai.yr-ai-1.yr,ai-1.
17、xds,ai-1.yr); /ai.xds-ai-1.xds表示过河过程中船上的修道士数,ai.yr-ai-1.yr表示过河过程中船上的野人数 else printf( - ( %d %d ) son; while (q!=NULL)/逐个搜索儿子结点 flag1=0;/等于0表示插入儿子结点,1表示插入兄弟结点 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
18、;/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(无
19、法成功渡河!n); else printf(有%d种渡河方式。n,count); int main int n,c,back; Link *p; DataType tem; while (back) printf(请输入修道士与野人的人数n:n); scanf(%d,&n); if (n=0) break; printf(请输入船可容纳的人数c:n); scanf(%d,&c); tem.xds=n; tem.yr=n; tem.cw=1; Linkinit(&p); /初始化邻接表; insertson(p, tem); /将初始状态作为头结点的孩子结点； guangdu(p,n,c); /进行广度搜索； printf(是否继续?(继续 1 ,退出 0 )n); scanf(%d,&back);
