农夫过河问题

农夫过河问题1．问题描述一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。要求：利用图的存储结构和图的搜索算法，求出农夫将所有的东西运过河的方案。2．需求分析2.1规定程序功能本题要解决的问题就是农夫如何带着狼、羊、白菜安全过河。要求是船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。2.2输入和输出形式本程序自动完成所有情况的输入，不需要人为的输入。然后根据程序里面调用相应函数模块可得到一种过河方案，然后自行输出。输出的是农夫过河每一步的方案，即每一步中农夫采取的行动。3．概要设计3.1数据结构的设计题目要求用图的存储结构，所以要想办法将农夫、狼、羊、白菜每一步的状态用结点表示，他们状态的改变到下一个结点可行，则在两条结点中加一条边。但是每个结点包含四个量，如果他们每个都各自用一个结构体表示，则图形就变得相当的繁琐，因此想到一个简单的结局办法。河的两岸是两个不同的变量，刚好可以用0和1表示，那么四个状态量都用0和1则可表示他们每一步所处的位置，也就能明白农夫每次是怎么过河的。3.2算法的设计本程序可以分成四个模块，分别是：找到所有情况的点、从中挑选出满足题意的点、创建满足题意的点之间的边、通过图的深度优先遍历找到过河方案。各模块之间的关系图如下：找到所有情况的点（即0000-1111共16种组合）挑出符合题意的点（即农夫不在时，狼不和羊、羊不和菜在一起）找到符合题意点之间边的关系通过图的深度优先遍历找到过河方案每个模块函数为：voidinput_vertex(DataType*vertex)//所有情况顶点的输入intright_vertex(DataType*vertex,DataType*vertex1)//选出满足题意的顶点intright_edge(DataType*vertex,RowCol*edge,intn)//选出满足题意的边voidDepthFSearch(AdjLGraphG,intv,intvisited[],DataTypevert[],int*a)//图的深度优先遍历3.3抽象数据类型的设计本题采用的是图，因此要用到定义图的结构体typedefstruct{intf;//农夫intw;//狼ints;//羊intc;//菜}DataType;//结点信息结构体定义typedefstruct{introw;intcol;}RowCol;//边信息结构体定义typedefstructNode{intdest;//邻接边的弧头结点序号structNode*next;}Edge;//邻接边单链表的结点结构体typedefstruct{DataTypedata;intsorce;//邻接边弧尾结点序号Edge*adj;//邻接边的头指针}AdjLHeight;//数组的数据元素类型结构体typedefstruct{AdjLHeighta[100];//邻接表数组intnumOfVerts;//结点个数intnumOfEdges;//边个数}AdjLGraph;//邻接表结构体4．详细设计4.1算法的主要思想为简化结点，将农夫、狼、羊、白菜用0和1两种状态量表示，0表示在河的南岸，也就是初始所在的河岸。1表示在河的北岸，即渡过河到达的对岸。那么初始状态即为0000，将其变为1111的中间状态量即为过河方案。那么就从16种所有情况的顶点中选择符合题意的结点，因为并不是所有点都满足题意，限制要求为农夫每次最多可带狼、羊、白菜中的一个过河，农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有满足题意的结点后，就要构造边，边即为符合题意两结点之间的连接。中间有边的两结点必须符合农夫的状态在变，并且农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有符合题意的结点和边后就构成了图，采用邻接表的存储结构，然后通过图的深度优先遍历，将所有满足题意的结点遍历一遍并输出，到1111时即输出了过河方案的全部步骤。4.2算法的实现①存储16种全部情况以供挑选。voidinputdian(DataType*d){intf,w,s,c,i=0;for(f=0;f=1;f++)for(w=0;w=1;w++)for(s=0;s=1;s++)for(c=0;c=1;c++){d[i].f=f;d[i].w=w;d[i].s=s;d[i].c=c;i++;}}②选出符合题意的所有结点intrdian(DataType*d,DataType*d2){inti;intnum=0;for(i=0;i16;i++){if(!(d[i].f!=d[i].s&&(d[i].w==d[i].s||d[i].s==d[i].c))){d2[num++]=d[i];}}returnnum;}③选出符合题意的结点之间的边intrbian(DataType*d,RowCol*edge,intn){intdf,dw,ds,dc;inti=0,j=0,num=0;for(i=0;in;i++)for(j=0;jn;j++){df=d[i].f-d[j].f;dw=abs(d[i].w-d[j].w);ds=abs(d[i].s-d[j].s);dc=abs(d[i].c-d[j].c);if(df!=0&&(dw+ds+dc)=1){edge[num].col=i;edge[num++].row=j;}}returnnum;}④图的深度优先遍历voidDepthFSearch(AdjLGraphG,intv,intvisited[],DataTyped1[],int*s){intw;d1[(*s)]=G.a[v].data;visited[v]=1;(*s)++;w=GetFirstVex(G,v);while(w!=-1){if(!visited[w])DepthFSearch(G,w,visited,d1,s);w=GetNextVex(G,v,w);}}4.3函数的调用关系图5.测试结果main()w=GetFirstVex(G,v);DepthFSearch(G,w,visited,d1,s);w=GetNextVex(G,v,w);inputdian(d);nd=rdian(d,rd);nb=rbian(rd,edge,nd);CreatGraph(&G,rd,nd,edge,nb);DepthFSearch(G,0,visited,d1,&s);