修道士与野人问题.docx
《修道士与野人问题.docx》由会员分享，可在线阅读，更多相关《修道士与野人问题.docx（20页珍藏版）》请在冰点文库上搜索。
修道士与野人问题
．修道士与野人问题
这是一个古典问题。
假设有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）函数调用关系图
（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;
else
return0;
}
Ø广度搜索模块
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;item.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;//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）;
}
Ø输出模块
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）;
else
printf（"<--（%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
截屏4
6．源程序清单
#include
#include
#include
typedefstruct
{
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;//船上修道士
else
return0;
}
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;//将一次过河的情况给b[i]
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）;
//a[i].xds-a[i-1].xds表示过河过程中船上的修道士数,a[i].yr-a[i-1].yr表示过河过程中船上的野人数
else
printf（"<--（%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"）;
}
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;//等于0表示插入儿子结点,1表示插入兄弟结点
j=boatcase（q->data,c）;//可能过河的情况
for（i=0;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;//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）;
}
intmain（）
{
intn,c,back;
Link*p;
DataTypetem;
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）;
}
}
升级会员 