修道士与野人问题Word下载.docx
- 文档编号:7082419
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:16
- 大小:89.50KB
修道士与野人问题Word下载.docx
《修道士与野人问题Word下载.docx》由会员分享,可在线阅读,更多相关《修道士与野人问题Word下载.docx(16页珍藏版)》请在冰点文库上搜索。
typedefstructNode
intdest;
//邻接表的弧头结点序号
structNode*next;
}Edge;
//邻接表单链表的结点结构体
typedefstruct
DataTypedata;
//结点数据元素
intsorce;
//邻接表的弧尾结点序号
Edge*adj;
//邻接边的头指针
intpre;
//指向此点的点的序号
}AdjLHeight;
//数组的数据元素类型结构体
AdjLHeighta[10000];
//邻接表数组
intnumOfVerts;
//结点个数
intnumOfEdges;
//边个数
}AdjLGraph;
//邻接表结构体
2)基本思想
由题意知,数据结构选用图较为合理,题中图的结点数目较大且边的数目远小于相同结点的完全图的边数,因此采用图的邻接表存储结构效率较高
根据给出的小船上的位置数量,生成小船上的安全状态,即在船上的时候修道士的人数也要比野人的数量要多(除非修道士人数为0)。
让修道士跟野人上船后,检测当船到达对岸后,两岸修道士的安全状态,若修道士安全,则将此结点加入到邻接表中
渡船优先规则:
起始岸一次运走的人越多越好(即起始岸运多人优先),同时野人优先运走;
目的岸一次运走的人越少越好(即目的岸运少人优先),同时修道士优先运走
采用广度搜索法,得到首先搜索到的边数最少的一条通路
3)举例说明:
当n=3;
c=2时,可用树状图来表示运送过程并用广度搜索法来查找最佳方案
(f表示运过去之后右岸的总人数,P从始岸到对岸;
0从对岸到始岸)
2.2设计表示法
1)过程或函数调用关系图
main→work→check→print
2)基于数据结构的操作组
该程序数据结构相对简单,只运用了邻接表结构的图,work()函数建立一个广度表,实现广度搜索算法;
check()函数用于检查各个状态下修道士是否安全;
print()函数打印安全渡河的过程
3)过程或函数接口规格说明
voidwork(AdjLGraph*p)//广搜建立表
intcheck(DataTypex)//检查当前情况下,修道士是否安全
intprint(AdjLGraph*p,intg)//打印安全渡河的过程
2.3函数详细设计
1)图的初始化
voidAdjInitiate(AdjLGraph*G)
inti;
G->
numOfEdges=0;
numOfVerts=0;
for(i=0;
i<
10000;
i++)
{
G->
a[i].sorce=i;
/*置邻接边的弧头结点序号*/
a[i].adj=NULL;
/*置邻接边单链表头指针初值*/
a[i].data.x3=-1;
a[i].pre=-1;
}
}
2)在G图中插入结点
voidInsertVertex(AdjLGraph*G,inti,DataTypevertex)
if(i>
=0&
&
i<
10000)
a[i].data.x1=vertex.x1;
a[i].data.x2=vertex.x2;
a[i].data.x3=vertex.x3;
numOfVerts++;
elseprintf("
结点越界!
\n"
);
3)在G图中插入边<
v1,v2>
voidInsertEdge(AdjLGraph*G,intv1,intv2)
Edge*p;
if(v1<
0||v1>
=G->
numOfVerts||v2<
0||v2>
G->
numOfVerts)
printf("
参数v1或v2越界出错!
"
exit(0);
p=(Edge*)malloc(sizeof(Edge));
/*申请邻接边单链表结点空间*/
p->
dest=v2;
/*置邻接边弧头序号*/
next=G->
a[v1].adj;
/*新结点插入单链表的表头*/
a[v1].adj=p;
/*头指针指向新的单链表表头*/
numOfEdges++;
/*边个数加1*/
4)G图的撤销
voidAdjDestroy(AdjLGraph*G)
Edge*p,*q;
numOfVerts;
p=G->
a[i].adj;
while(p!
=NULL)
{
q=p->
next;
free(p);
p=q;
}
5)检查当前情况下,修道士是否安全
intcheck(DataTypex)
if((x.x1>
=x.x2||x.x1==0)&
((n-x.x1)>
=(n-x.x2)||x.x1==n)&
x.x1>
=0&
x.x1<
=n&
x.x2>
x.x2<
=n)
return1;
else
return0;
6)生成在船上修道士仍安全的情况
intfindfa(DataTypex)
inti=0,a,b,t=0;
//从始案到末岸的状态
if(x.x3)
a=0;
b=c-a;
while(a+b>
=1)
t++;
while(b>
=0)
{
fa[i].x1=a;
fa[i].x2=b;
i++;
a++;
b--;
}
b=c-a-t;
else//从末岸到始岸的状态
a=1;
b=0;
t=0;
while(a+b<
=c)
while(a>
fa[i].x1=a*(-1);
fa[i].x2=b*(-1);
a--;
b++;
}
a=fa[0].x1*(-1)+t;
b=0;
returni;
7)打印安全渡河的过程
intprint(AdjLGraph*p,intg)
DataTypeb[1000];
inti=0;
while(g!
=-1)
b[i++]=p->
a[g].data;
g=p->
a[g].pre;
while((--i)>
-1)
(%d%d%d)"
b[i].x1,b[i].x2,b[i].x3);
if(!
(b[i].x1==0&
b[i].x2==0&
b[i].x3==0))
if(b[i].x3==1)
printf("
→(%d%d)→(%d%d0)\n"
b[i].x1-b[i-1].x1,b[i].x2-b[i-1].x2,b[i-1].x1,b[i-1].x2);
else
→(%d%d)→(%d%d1)\n"
(b[i].x1-b[i-1].x1)*(-1),(-1)*(b[i].x2-b[i-1].x2),b[i-1].x1,b[i-1].x2);
else
printf("
渡河成功!
8)广搜建立表
DataTypetem;
inti,flag1,g=0,j,count=0,k=0,t;
while(p->
a[k].data.x3!
j=findfa(p->
a[k].data);
for(i=0;
j;
tem.x1=p->
a[k].data.x1-fa[i].x1;
tem.x2=p->
a[k].data.x2-fa[i].x2;
tem.x3=1-p->
a[k].data.x3;
if(check(tem))
flag1=1;
t=k;
while(t!
{
if(tem.x1==p->
a[t].data.x1&
tem.x2==p->
a[t].data.x2&
tem.x3==p->
a[t].data.x3)
{
flag1=0;
break;
}
t--;
}
if(flag1==1)
g++;
p->
a[g].pre=k;
InsertVertex(p,g,tem);
InsertEdge(p,k,g);
if(tem.x1==0&
tem.x2==0&
tem.x3==0)
count++;
print(p,g);
k++;
}
if(count==0)
不能渡河!
有%d种渡河方式。
count);
9)主函数
voidmain()
AdjLGraphG;
DataTypefirst;
while
(1)
***********193112班张玉彬**********\n********修道士与野人问题**********\n"
请输入野人和修道士人数N:
scanf("
%d"
&
n);
请输入船可乘人数C:
c);
AdjInitiate(&
G);
first.x1=n;
first.x2=n;
first.x3=1;
InsertVertex(&
G,0,first);
work(&
AdjDestroy(&
charchoice;
for(;
;
)
是否继续?
(Y/N)\n"
scanf("
%s"
&
choice);
choice=toupper(choice);
//toupper可将小写字母转化成大写的
if(choice=='
Y'
)break;
N'
)exit(0);
3.调试分析:
1)刚始不知道从何下手,就先举了一个简单例子,看当野人与修道士都是两人,船最多只能容纳二人时该怎么渡,我在本上画出了所有的方案,然后去想怎样去用程序来实现上述过程。
再结合题目要求,根据课本上的邻接表存储结构的知识,再去限定规则来实现渡河方案,脑中大概有了编程方向和较明确的模块建立的思路。
2)较难的模块是考虑各种情况下保障修道士的安全,在此案,在彼岸,在船上,编写程序序来限定规则,虽然并不复杂,但我发现写得尽量完美并不容易。
而在写建立广搜表程序时,真的是难为坏了,刚开始没考虑到设立一个标志符来避免死循环,结果就怎么也输不出正确结果,后来与同学讨论时受到启发,最后得以成功完成
3)通过此次编程感觉收获了好多,首先不管自己感觉问题难易程度如何,都要按部就班,从最基本的做起,如没头绪时多试几组数据,然后回归课本知识来想解决方案,实在不会时不要轻言放弃,可以先与老师,同学多多交流,最后的方法才是上网查询参考,这样才能使自己编程能力得到真正的提高。
4.用户手册
1)本程序的运行环境为,MicrosoftVisualC++6.0.
2)程序运行过程及说明:
a)进入演示程序后,出现提示信息:
请输入野蛮人和修道士人数N:
b)用户输入相关数据后,程序输出结果,并在终端显示出来
5.测试结果
3
2
运行结果如下:
(331)→(02)→(310)
(310)→(01)→(321)
(321)→(02)→(300)
(300)→(01)→(311)
(311)→(20)→(110)
(110)→(11)→(221)
(221)→(20)→(020)
(020)→(01)→(031)
(031)→(02)→(010)
(010)→(10)→(111)
(111)→(11)→(000)
(000)
…………
有4种渡河方案。
调试图片
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 修道士 野人 问题