农夫过河问题

农夫过河问题

1． 问题描述

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。

要求：利用图的存储结构和图的搜索算法，求出农夫将所有的东西运过河的方案。

2． 需求分析

2.1规定程序功能

本题要解决的问题就是农夫如何带着狼、羊、白菜安全过河。要求是船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。

2.2输入和输出形式

本程序自动完成所有情况的输入，不需要人为的输入。然后根据程序里面调用相应函数模块可得到一种过河方案，然后自行输出。输出的是农夫过河每一步的方案，即每一步中农夫采取的行动。

3． 概要设计

3.1数据结构的设计

题目要求用图的存储结构，所以要想办法将农夫、狼、羊、白菜每一步的状态用结点表示，他们状态的改变到下一个结点可行，则在两条结点中加一条边。但是每个结点包含四个量，如果他们每个都各自用一个结构体表示，则图形就变得相当的繁琐，因此想到一个简单的结局办法。河的两岸是两个不同的变量，刚好可以用0和1表示，那么四个状态量都用0和1则可表示他们每一步所处的位置，也就能明白农夫每次是怎么过河的。

3.2算法的设计

本程序可以分成四个模块，分别是：找到所有情况的点、从中挑选出满足题意的点、创建满足题意的点之间的边、通过图的深度优先遍历找到过河方案。

各模块之间的关系图如下：

每个模块函数为：

void input_vertex(DataType *vertex) //所有情况顶点的输入

int right_vertex(DataType *vertex,DataType *vertex1) //选出满足题意的顶点

int right_edge(DataType *vertex,RowCol *edge,int n) //选出满足题意的边

void DepthFSearch(AdjLGraph G,int v,int visited[],DataType vert[],int *a)

//图的深度优先遍历

3.3抽象数据类型的设计

本题采用的是图，因此要用到定义图的结构体

typedef struct

{

int f;//农夫

int w;//狼

int s;//羊

int c;//菜

}DataType;//结点信息结构体定义

typedef struct

{

int row;

int col;

}RowCol;//边信息结构体定义

typedef struct Node

{

int dest;//邻接边的弧头结点序号

struct Node *next;

}Edge;//邻接边单链表的结点结构体

typedef struct

{

DataType data;

int sorce;//邻接边弧尾结点序号

Edge *adj;//邻接边的头指针

}AdjLHeight;//数组的数据元素类型结构体

typedef struct

{

AdjLHeight a[100];//邻接表数组

int numOfVerts;//结点个数

int numOfEdges;//边个数

}AdjLGraph;//邻接表结构体

4． 详细设计

4.1算法的主要思想

为简化结点，将农夫、狼、羊、白菜用0和1两种状态量表示，0表示在河的南岸，也就是初始所在的河岸。1表示在河的北岸，即渡过河到达的对岸。那么初始状态即为0000，将其变为1111的中间状态量即为过河方案。那么就从16种所有情况的顶点中选择符合题意的结点，因为并不是所有点都满足题意，限制要求为农夫每次最多可带狼、羊、白菜中的一个过河，农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有满足题意的结点后，就要构造边，边即为符合题意两结点之间的连接。中间有边的两结点必须符合农夫的状态在变，并且农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。选出所有符合题意的结点和边后就构成了图，采用邻接表的存储结构，然后通过图的深度优先遍历，将所有满足题意的结点遍历一遍并输出，到1111时即输出了过河方案的全部步骤。

4.2算法的实现

①存储16种全部情况以供挑选。

void inputdian(DataType *d)

{

int f,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++;

}

}

②选出符合题意的所有结点

int rdian(DataType *d,DataType *d2)

{

int i;

int num=0;

for(i=0;i<16;i++)

{

if(!(d[i].f!=d[i].s&&(d[i].w==d[i].s||d[i].s==d[i].c)))

{

d2[num++]=d[i];

}

}

return num;

}

③选出符合题意的结点之间的边

int rbian(DataType *d,RowCol *edge,int n)

{

int df,dw,ds,dc;

int i=0,j=0,num=0;

for(i=0;i

for(j=0;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;

}

}

return num;

}

④图的深度优先遍历

void DepthFSearch(AdjLGraph G,int v,int visited[],DataType d1[],int *s)

{

int w;

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.测试结果

本文来源：https://www.2haoxitong.net/k/doc/67d4613343323968011c9220.html