当前位置：文档之家› 农夫过河报告(最终版)

农夫过河报告(最终版)

农夫过河算法实验报告

――数据结构项目课研究课题

组长：崔俊

组员：李琦、郑鸿飞、王琅辉、张育博

15.12.29

摘要

农夫过河问题是应用广度优先搜索和深度优先搜索的典型问题，但这里我们应用了简单

的数组，通过层层筛选的手段也解决了同样的问题，其中用到了部分广度优先搜索的思想。

、八■、-

前言

农夫过河问题描述：一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才

能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫

将所有的东西运过河的方案。

正文

1?问题抽象和数据组织

农夫过河问题应该应用图的广度优先遍历或者深度优先遍历，但这里我们仅使用简单的

线性表一一数组，通过多重的条件限制，达成目的。这里我们同样用O和1代表农夫、狼、

羊、白菜在左岸还是在右岸，并规定O在左，1在右，我们的目的便是从OOOO通过一系列变换到1111。

2.农夫过河算法源代码

#in elude VStdio.h>

#define MAX 16

typedef StrUCt FWSV

{

int farmer;

int wolf;

int sheep;

int vegetable;

}Item;

//函数原型

//操作：筛选符合条件的安全的数组成员

//操作前：无

//操作后：返回安全数组的指针

void SCree n( void);

//操作：判断下一个数应该取安全数组中那个数

//操作前：传递一个结构体数组成员

//操作后：返回另一个结构体数组指针

Item * judge(Item Fwsv);

Item safe[MAX];

int k = 0;

int main (Void)

{

SCree n();

Item * n ext;

Item first,sec On d,e nd;

first = safe[0];

end = safe[k];

Prin tf("first:0000\n"); n ext = judge(first);

void SCree n( void)

{

int f = 0,w = 0,s = 0,v = 0;

for(f = 0;f < 2;f++)

{

for(w = 0;W < 2;w++)

{

for(s = 0;S < 2;s++)

{

for(v = 0;V < 2;v++)

{

if (!(f != S && (S == W Il S == V)))

{

safe[k].farmer = f;

safe[k].wolf = w;

safe[k].sheep = s;

safe[k].vegetable = v;

k++;

// 用于计数safe[]中的总数

}

Item * judge(Item FWSV)

{

Item * n ext;

Item COmPare[4];

n ext = compare;

int x1 = 0;

int SUm = 0;

if (Fwsv.farmer == 0)

{

for (int X = 0;X < k;x++)

{

ZZ把出现过的置零操作

if(safe[x].farmer == Fwsv.farmer && safe[x].wolf == Fwsv.wolf &&

safe[x].sheep == Fwsv.sheep && safe[x].vegetable == Fwsv.vegetable )

{

safe[x].farmer = 0;

safe[x].wolf = 0;

safe[x].sheep = 0; safe[x].vegetable = 0;

}

ZZ筛选出农夫状态值与之前相反的1变0 0变1

if(safe[x].farmer == 1 && (safe[x].farmer + safe[x].wolf +

safe[x].sheep + safe[x].vegetable != 4 ))

{

COmPare[x1] = safe[x];

x1++;

}

for (int x2 = 0;x2 < 4;x2++)

//删除状态值与农夫不同但是改变了的

SUm = Fwsvfarmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable;

if ((FWSV.farmer != Fwsv.wolf && COmPare[x2].wolf != Fwsv.wolf)

||(Fwsv.farmer != Fwsv.sheep && COmPare[x2].SheeP !

= Fwsv.sheep)

{

Il (Fwsv.farmer != Fwsv.vegetable && COmPare[x2].VegetabIe !

= Fwsv.vegetable)

Il (Fwsv.farmer != Fwsv.vegetable && COmPare[x2].VegetabIe !

= Fwsv.vegetable))

{

COmPare[x2].farmer = 0;

COmPare[x2].wolf = 0;

COmPare[x2].SheeP = 0;

COmPare[x2].VegetabIe = 0;

}

sum+=2;

//对和的限制

if(compare[x2].farmer + COmPare[x2].wolf + COmPare[x2].SheeP +

COmPare[x2].VegetabIe != SUm)

{

COmPare[x2].farmer = 0;

COmPare[x2].wolf = 0;

COmPare[x2].SheeP = 0;

COmPare[x2].VegetabIe = 0;

}

Printf(" -------------------------------------- ?n");

for(i nt x3 = 0;x3 < 4;x3++)

{

if (COmPare[x3].farmer + COmPare[x3].wolf + COmPare[x3].SheeP +

COmPare[x3].VegetabIe != 0)

{

Printf(" 上数与：％d%d%d%d 连?n",

ComPare[x3].farmer,compare[x3].wolf,compare[x3].sheep,compare[x3].veget abl );

}

{

if (Fwsv.farmer == 1) {

for (int y = 0;y V k;y++) {

if(safe[y].farmer == Fwsv.farmer && safe[y].wolf == Fwsv.wolf && safe[y].sheep

== Fwsv.sheep && safe[y].vegetable == Fwsv.vegetable )

{

safe[y].farmer = 0; safe[y].wolf = 0;

safe[y].sheep = 0; safe[y].vegetable = 0; }

if(safe[y].farmer

== 0 && (safe[y].farmer + safe[y].wolf

safe[y].sheep + safe[y].vegetable != 0 ))

{

ComPare[x1] = safe[y]; x1++; } }

for (int x2 = 0;x2 < 4;x2++) {

SUm = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable; if ((FWSV.farmer != Fwsv.wolf && COmPare[x2].wolf != Fwsv.wolf)

Fwsv.sheep)

Fwsv.vegetable)

Fwsv.vegetable))

{

COmPare[x2].farmer = 0; COmPare[x2].wolf = 0; COmPare[x2].SheeP = 0; COmPare[x2].VegetabIe = 0; } }

Printf(" for(i nt x3 = 0;x3 < 4;x3++)

∣∣(Fwsv.farmer != Fwsv.sheep && COmPare[x2].SheeP

!= Il (Fwsv.farmer

!= Fwsv.vegetable && COmPare[x2].VegetabIe != Il (Fwsv.farmer

!= Fwsv.vegetable

&& COmPare[x2].VegetabIe

?n");

if (ComPare[x3].farmer + ComPare[x3].Wolf + ComPare[x3].SheeP + ComPare[x3].VegetabIe != 0)

{