内容发布更新时间 : 2024/6/16 17:27:43星期一 下面是文章的全部内容请认真阅读。

这最起码是一个报告，虽然我尽力的看，终究还是看不懂。

农夫过河算法实验报告

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

组长：崔俊

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

15.12.29

摘要

农夫过河问题是应用广度优先搜索和深度优先搜索的典型问题，但这里我们应用了简单的数组，通过层层筛选的手段也解决了同样的问题，其中用到了部分广度优先搜索的思想。

前言

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

正文

1.问题抽象和数据组织

农夫过河问题应该应用图的广度优先遍历或者深度优先遍历，但这里我们仅使用简单的线性表——数组，通过多重的条件限制，达成目的。这里我们同样用0和1代表农夫、狼、羊、白菜在左岸还是在右岸，并规定0在左，1在右，我们的目的便是从0000通过一系列变换到1111。 2.农夫过河算法源代码

#include #define MAX 16 typedef struct FWSV {

int farmer; int wolf; int sheep; int vegetable;

}Item; //函数原型

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

//操作后：返回安全数组的指针 void screen(void);

//操作： 判断下一个数应该取安全数组中那个数 //操作前: 传递一个结构体数组成员 //操作后：返回另一个结构体数组指针 Item * judge(Item Fwsv); Item safe[MAX];

int k = 0; //用于计数safe[]中的总数 int main (void) { }

void screen(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 || s == v))) {

safe[k].farmer = f;

screen(); Item * next;

Item first,second,end; first = safe[0]; end = safe[k];

printf(\next = judge(first); { } return 0;

if (next->farmer + next->wolf + next->sheep + next->vegetable != 0) { } else

next++; second = *next; next = judge(second);

for (int count = 0;count <= 6;count++)

printf(\

safe[k].wolf = w;