下载文档原格式
数据结构课程设计报告（农夫过河）第一篇：数据结构课程设计报告(农夫过河)目录引言...................................................2 问题描述..............................................3 基本要求 (3)2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；........3 2.2设计一个算法求解农夫过河问题，并输出过河方案；......................3 3 概要设计 (3)3.1 数据结构的设计。
....................................................3 3.1.1农夫过河问题的模型化.............................................3 3.1.2 算法的设计 (4)4、运行与测试 (6)5、总结与心得..........................................7 附录...................................................7 参考文献. (13)引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。
一条小船只能容下他和一件物品, 只有农夫能撑船。
问农夫怎么能安全过河, 当然狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品单独放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。
1 问题描述一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫设计过河方案。
基本要求2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；2.2设计一个算法求解农夫过河问题，并输出过河方案；概要设计3.1 数据结构的设计。
农夫过河问题一、实验目的掌握广度优先搜索策略，并用队列求解农夫过河问题二、实验内容问题描述：一农夫带着一只狼，一只羊和一颗白菜，身处河的南岸，他要把这些东西全部运到北岸，遗憾的是他只有一只小船，小船只能容下他和一件物品。
这里只能是农夫来撑船，同时因为狼吃羊、羊吃白菜、所以农夫不能留下羊和狼或羊和白菜在河的一边，而自己离开；好在狼属肉食动物，不吃白菜。
农夫怎么才能把所有的东西安全运过河呢？实验要求如下：（1）设计物品位置的表示方法和安全判断算法；（2）设计队列的存储结构并实现队列的基本操作（建立空队列、判空、入队、出队、取对头元素），也可以使用STL中的队列进行代码的编写；（3）采用广度优先策略设计可行的过河算法；（4）输出要求：按照顺序输出一种可行的过河方案；提示：可以使用STL中的队列进行代码编写。
程序运行结果：二进制表示：1111011011100010101100011001，0000三、农夫过河算法流程⏹Step1：初始状态0000入队⏹Step2：当队列不空且没有到达结束状态1111时，循环以下操作：⏹队头状态出队⏹按照农夫一个人走、农夫分别带上三个物品走，循环以下操作：⏹农夫和物品如果在同一岸，则计算新的状态⏹如果新状态是安全的并且是没有处理过的，则更新path[ ]，并将新状态入队⏹当状态为1111时，逆向输出path[ ]数组附录一：STL中队列的使用注：队列，可直接用标准模板库（STL）中的队列。
需要#include<queue>STL中的queue，里面的一些成员函数如下（具体可以查找msdn，搜索queue class）：front：Returns a reference to the first element at the front of the queue.pop：Removes an element from the front of the queuepush：Adds an element to the back of the queueempty：Tests if the queue is empty三、实验代码FarmerRiver.H#ifndef FARMERRIVER_H#define FARMERRIVER_Hint FarmerOnRight(int status); //农夫，在北岸返回1，否则返回0int WorfOnRight(int status); //狼int CabbageOnRight(int status); //白菜int GoatOnRight(int status); //羊int IsSafe(int status); //判断状态是否安全，安全返回1，否则返回0void FarmerRiver();#endifSeqQueue.h#ifndef SEQQUEUE_H#define SEQQUEUE_Htypedef int DataType;struct Queue{int Max;int f;int r;DataType *elem;};typedef struct Queue *SeqQueue;SeqQueue SetNullQueue_seq(int m);int IsNullQueue_seq(SeqQueue squeue);void EnQueue_seq(SeqQueue squeue, DataType x);void DeQueue_seq(SeqQueue);DataType FrontQueue_seq(SeqQueue);#endifFarmerRiver.c#include <stdio.h>#include <stdlib.h>#include "SeqQueue.h"#include "FarmerRiver.h"int FarmerOnRight(int status) //判断当前状态下农夫是否在北岸{return (0!=(status & 0x08));}int WorfOnRight(int status){return (0!=(status & 0x04));}int CabbageOnRight(int status){return (0!=(status & 0x02));}int GoatOnRight(int status){return (0!=(status & 0x01));}int IsSafe(int status) //判断当前状态是否安全{if ((GoatOnRight(status)==CabbageOnRight(status)) &&(GoatOnRight(status)!=FarmerOnRight(status)))return (0); //羊吃白菜if ((GoatOnRight(status)==WorfOnRight(status)) && (GoatOnRight(status)!=FarmerOnRight(status))) return 0; //狼吃羊return 1; //其他状态是安全的}void FarmerRiver(){int i, movers, nowstatus, newstatus;int status[16]; //用于记录已考虑的状态路径SeqQueue moveTo;moveTo = SetNullQueue_seq(20); //创建空列队EnQueue_seq(moveTo, 0x00); //初始状态时所有物品在北岸，初始状态入队for (i=0; i<16; i++) //数组status初始化为-1{status[i] = -1;}status[0] = 0;//队列非空且没有到达结束状态while (!IsNullQueue_seq(moveTo) && (status[15]==-1)){nowstatus = FrontQueue_seq(moveTo); //取队头DeQueue_seq(moveTo);for (movers=1; movers<=8; movers<<=1)//考虑各种物品在同一侧if ((0!=(nowstatus & 0x08)) == (0!=(nowstatus & movers)))//农夫与移动的物品在同一侧{newstatus = nowstatus ^ (0x08 | movers); //计算新状态//如果新状态是安全的且之前没有出现过if (IsSafe(newstatus)&&(status[newstatus] == -1)){status[newstatus] = nowstatus; //记录新状态EnQueue_seq(moveTo, newstatus); //新状态入队}}}//输出经过的状态路径if (status[15]!=-1){printf("The reverse path is: \n");for (nowstatus=15; nowstatus>=0; nowstatus=status[nowstatus]){printf("The nowstatus is: %d\n", nowstatus);if (nowstatus == 0)return;}}elseprintf("No solution.\n");}Sequeue.c#include <stdio.h>#include <stdlib.h>#include "SeqQueue.h"SeqQueue SetNullQueue_seq(int m){SeqQueue squeue;squeue = (SeqQueue)malloc(sizeof(struct Queue));if (squeue==NULL){printf("Alloc failure\n");return NULL;}squeue->elem = (int *)malloc(sizeof(DataType) * m);if (squeue->elem!=NULL){squeue->Max = m;squeue->f = 0;squeue->r = 0;return squeue;}else free(squeue);}int IsNullQueue_seq(SeqQueue squeue){return (squeue->f==squeue->r);}void EnQueue_seq(SeqQueue squeue, DataType x) //入队{if ((squeue->r+1) % squeue->Max==squeue->f) //是否满printf("It is FULL Queue!");else{squeue->elem[squeue->r] = x;squeue->r = (squeue->r+1) % (squeue->Max);}}void DeQueue_seq(SeqQueue squeue) //出队{if (IsNullQueue_seq(squeue))printf("It is empty queue!\n");elsesqueue->f = (squeue->f+1) % (squeue->Max); }DataType FrontQueue_seq(SeqQueue squeue) //求队列元素{if (squeue->f==squeue->r)printf("It is empty queue!\n");elsereturn (squeue->elem[squeue->f]);}main.c#include <stdio.h>#include <stdlib.h>#include "FarmerRiver.h"int main(void){FarmerRiver();return 0;}实验结果：四、实验总结。
课程设计题目：农夫过河一．问题描述一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。
他要把这些东西全部运到北岸。
他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。
过河有以下规则：(1)农夫一次最多能带一样东西（或者是狼、或者是羊、或者是白菜）过河；(2)当农夫不在场是狼会吃羊；(3)当农夫不在场是羊会吃掉白菜。
现在要求为农夫想一个方案，能将3样东西顺利地带过河。
从出事状态开始，农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。
二．基本要求(1)为农夫过河问题抽象数据类型，体会数据模型在问题求解中的重要性；(2)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设计；(3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态；(4)设计一个算法求解农夫过河问题，并输出过河方案；(5)分析算法的时间复杂度。
三．概要设计(1)数据结构的设计typedef struct // 图的顶点{int farmer; // 农夫int wolf; // 狼int sheep; // 羊int veget; // 白菜}Vertex;设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在河的南岸。
t ypedef struct{int vertexNum; // 图的当前顶点数Vertex vertex[VertexNum]; // 顶点向量（代表顶点）bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关}AdjGraph; // 定义图的邻接矩阵存储结构存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。
农夫过河问题一、实验目的掌握广度优先搜索策略，并用队列求解农夫过河问题二、实验内容问题描述：一农夫带着一只狼，一只羊和一颗白菜，身处河的南岸，他要把这些东西全部运到北岸，遗憾的是他只有一只小船，小船只能容下他和一件物品。
这里只能是农夫来撑船，同时因为狼吃羊、羊吃白菜、所以农夫不能留下羊和狼或羊和白菜在河的一边，而自己离开；好在狼属肉食动物，不吃白菜。
农夫怎么才能把所有的东西安全运过河呢？实验要求如下：（1）设计物品位置的表示方法和安全判断算法；（2）设计队列的存储结构并实现队列的基本操作（建立空队列、判空、入队、出队、取对头元素），也可以使用STL中的队列进行代码的编写；（3）采用广度优先策略设计可行的过河算法；（4）输出要求：按照顺序输出一种可行的过河方案；提示：可以使用STL中的队列进行代码编写。
程序运行结果：二进制表示：1111011011100010101100011001，0000三、农夫过河算法流程⏹Step1：初始状态0000入队⏹Step2：当队列不空且没有到达结束状态1111时，循环以下操作：⏹队头状态出队⏹按照农夫一个人走、农夫分别带上三个物品走，循环以下操作：⏹农夫和物品如果在同一岸，则计算新的状态⏹如果新状态是安全的并且是没有处理过的，则更新path[ ]，并将新状态入队⏹当状态为1111时，逆向输出path[ ]数组附录一：STL中队列的使用注：队列，可直接用标准模板库（STL）中的队列。
需要#include<queue>STL中的queue，里面的一些成员函数如下（具体可以查找msdn，搜索queue class）：front：Returns a reference to the first element at the front of the queue.pop：Removes an element from the front of the queuepush：Adds an element to the back of the queueempty：Tests if the queue is empty三、实验代码FarmerRiver.H#ifndef FARMERRIVER_H#define FARMERRIVER_Hint FarmerOnRight(int status); //农夫，在北岸返回1，否则返回0int WorfOnRight(int status); //狼int CabbageOnRight(int status); //白菜int GoatOnRight(int status); //羊int IsSafe(int status); //判断状态是否安全，安全返回1，否则返回0void FarmerRiver();#endifSeqQueue.h#ifndef SEQQUEUE_H#define SEQQUEUE_Htypedef int DataType;struct Queue{int Max;int f;int r;DataType *elem;};typedef struct Queue *SeqQueue;SeqQueue SetNullQueue_seq(int m);int IsNullQueue_seq(SeqQueue squeue);void EnQueue_seq(SeqQueue squeue, DataType x);void DeQueue_seq(SeqQueue);DataType FrontQueue_seq(SeqQueue);#endifFarmerRiver.c#include <stdio.h>#include <stdlib.h>#include "SeqQueue.h"#include "FarmerRiver.h"int FarmerOnRight(int status) //判断当前状态下农夫是否在北岸{return (0!=(status & 0x08));}int WorfOnRight(int status){return (0!=(status & 0x04));}int CabbageOnRight(int status){return (0!=(status & 0x02));}int GoatOnRight(int status){return (0!=(status & 0x01));}int IsSafe(int status) //判断当前状态是否安全{if ((GoatOnRight(status)==CabbageOnRight(status)) && (GoatOnRight(status)!=FarmerOnRight(status)))return (0); //羊吃白菜if ((GoatOnRight(status)==WorfOnRight(status)) && (GoatOnRight(status)!=FarmerOnRight(status))) return 0; //狼吃羊return 1; //其他状态是安全的}void FarmerRiver(){int i, movers, nowstatus, newstatus;int status[16]; //用于记录已考虑的状态路径SeqQueue moveTo;moveTo = SetNullQueue_seq(20); //创建空列队EnQueue_seq(moveTo, 0x00); //初始状态时所有物品在北岸，初始状态入队for (i=0; i<16; i++) //数组status初始化为-1{status[i] = -1;}status[0] = 0;//队列非空且没有到达结束状态while (!IsNullQueue_seq(moveTo) && (status[15]==-1)){nowstatus = FrontQueue_seq(moveTo); //取队头DeQueue_seq(moveTo);for (movers=1; movers<=8; movers<<=1)//考虑各种物品在同一侧if ((0!=(nowstatus & 0x08)) == (0!=(nowstatus & movers)))//农夫与移动的物品在同一侧{newstatus = nowstatus ^ (0x08 | movers); //计算新状态//如果新状态是安全的且之前没有出现过if (IsSafe(newstatus)&&(status[newstatus] == -1)){status[newstatus] = nowstatus; //记录新状态EnQueue_seq(moveTo, newstatus); //新状态入队}}}//输出经过的状态路径if (status[15]!=-1){printf("The reverse path is: \n");for (nowstatus=15; nowstatus>=0; nowstatus=status[nowstatus]){printf("The nowstatus is: %d\n", nowstatus);if (nowstatus == 0)return;}}elseprintf("No solution.\n");}Sequeue.c#include <stdio.h>#include <stdlib.h>#include "SeqQueue.h"SeqQueue SetNullQueue_seq(int m){SeqQueue squeue;squeue = (SeqQueue)malloc(sizeof(struct Queue));if (squeue==NULL){printf("Alloc failure\n");return NULL;}squeue->elem = (int *)malloc(sizeof(DataType) * m);if (squeue->elem!=NULL){squeue->Max = m;squeue->f = 0;squeue->r = 0;return squeue;}else free(squeue);}int IsNullQueue_seq(SeqQueue squeue){return (squeue->f==squeue->r);}void EnQueue_seq(SeqQueue squeue, DataType x) //入队{if ((squeue->r+1) % squeue->Max==squeue->f) //是否满printf("It is FULL Queue!");else{squeue->elem[squeue->r] = x;squeue->r = (squeue->r+1) % (squeue->Max);}}void DeQueue_seq(SeqQueue squeue) //出队{if (IsNullQueue_seq(squeue))printf("It is empty queue!\n");elsesqueue->f = (squeue->f+1) % (squeue->Max); }DataType FrontQueue_seq(SeqQueue squeue) //求队列元素{if (squeue->f==squeue->r)printf("It is empty queue!\n");elsereturn (squeue->elem[squeue->f]);}main.c#include <stdio.h>#include <stdlib.h>#include "FarmerRiver.h"int main(void){FarmerRiver();return 0;}实验结果：四、实验总结。
【数据结构与算法】狼、⽺、菜和农夫过河：使⽤图的⼴度优先遍历实现【数据结构与算法】狼、⽺、菜和农夫过河：使⽤图的⼴度优先遍历实现Java农夫需要把狼、⽺、菜和⾃⼰运到河对岸去，只有农夫能够划船，⽽且船⽐较⼩。
除农夫之外每次只能运⼀种东西。
还有⼀个棘⼿问题，就是如果没有农夫看着，⽺会偷吃菜，狼会吃⽺。
请考虑⼀种⽅法，让农夫能够安全地安排这些东西和他⾃⼰过河。
解题思路学了图论的⼴度优先遍历算法后，我们可以使⽤⼴度优先遍历的思想来完成这道题。
⾸先定义如何表达农夫、狼、⽺、菜在河的哪⼀边。
只有两种状态：1. 在河的⼀边（假设为东边）2. 在河的另⼀边（假设为西边）那么恰好可以⽤0和1来表达，任务定义如下（使⽤字符串来表达）：// ⼈狼⽺菜// 源： 0 0 0 0//⽬标： 1 1 1 1String s = "0000";String t = "1111";那接下来程序的任务就是搜索出从s到t的过程了。
那么如何转换成图论问题？我们知道，0000 代表农夫、狼、⽺、菜都在河的东边，那么下⼀种状态可以有如下⼏种选择：1. 东：空狼⽺菜 | 西：⼈空空空（农夫⾃⼰过河）2. 东：空空⽺菜 | 西：⼈狼空空（农夫带狼过河）3. 东：空狼空菜 | 西：⼈空⽺空（农夫带⽺过河）4. 东：空狼⽺空 | 西：⼈空空菜（农夫带菜过河）我们根据这个可以绘制⼀个图，顶点0000 分别与顶点1000、顶点1100、顶点1010、顶点1001有边连接；其中，根据规则在没有农夫的情况下，狼和⽺不能在⼀起，⽺和菜不能在⼀起，所以排除掉以上的1,2,4选项。
那么下⼀个状态就是 0101然后根据这个原理，再往下查找有哪些是可以的：1. 东：⼈狼空菜 | 西：空空⽺空（农夫⾃⼰过河）2. 东：⼈狼⽺菜 | 西：空空空空（农夫带⽺过河）我们根据这个也可以绘制⼀个图，顶点0101 分别与顶点0000、顶点0010有边连接；然后再根据规则进⾏查找。
题目：一个农夫带着一匹狼、一只羊、一颗白菜要过河，只有一条船而且农夫每次最多只能带一个动物或物品过河，并且当农夫不在的时候狼会吃羊，羊会吃白菜，列出所有安全将所有动物和物品带过河的方案。
要求：广度优先搜索农夫过河解，并输出结果源代码：#include <stdio.h>#include <stdlib.h>typedef int DataType;struct SeqQueue{int MAXNUM;int f, r;DataType *q;};typedef struct SeqQueue *PSeqQueue; // 顺序队列类型的指针类型PSeqQueue createEmptyQueue_seq(int m)//创建一个空队列{PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue)); if (queue != NULL){queue->q = (DataType*)malloc(sizeof(DataType) *m);if (queue->q){queue->MAXNUM = m;queue->f = 0;queue->r = 0;return (queue);}elsefree(queue);}printf("Out of space!!\n"); // 存储分配失败return NULL;}int isEmptyQueue_seq(PSeqQueue queue)//判断队列是否为空{return (queue->f == queue->r);}void enQueue_seq(PSeqQueue queue, DataType x)//入队{if ((queue->r + 1) % queue->MAXNUM == queue->f)printf("Full queue.\n");else{queue->q[queue->r] = x;queue->r = (queue->r + 1) % queue->MAXNUM;}}void deQueue_seq(PSeqQueue queue)// 删除队列头部元素{if (queue->f == queue->r)printf("Empty Queue.\n");elsequeue->f = (queue->f + 1) % queue->MAXNUM;}DataType frontQueue_seq(PSeqQueue queue)//取队头元素{if (queue->f == queue->r)printf("Empty Queue.\n");elsereturn (queue->q[queue->f]);}int farmer(int location)//判断农夫的位置 1000表示在北岸{return (0 != (location &0x08));}int wolf(int location)//判断狼的位置 0100表示在北岸{return (0 != (location &0x04));}int cabbage(int location)//判断白菜的位置 0010表示在北岸{return (0 != (location &0x02));}int goat(int location)//判断羊的位置 0001表示在北岸{return (0 != (location &0x01));}int safe(int location)//安全状态的判断{if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location))) //羊与白菜不安全return 0;if ((goat(location) == wolf(location)) && (goat(location) != farmer(location)))//羊与狼不安全return 0;return 1; // 其他状态是安全的}void bin_print(int num)//将十进制数转换成二进制数输出{char tmp[4];int i;for (i = 0; i < 4; ++i){tmp[i] = num & 0x01;num >>= 1;}for (i = 3; i >= 0; --i)putchar((tmp[i] == 0)?'0':'1');return;}int main(){int i, movers, location, newlocation;int a=0;int r[16];int route[16]; //用于记录已考虑的状态路径PSeqQueue moveTo; //用于记录可以安全到达的中间状态moveTo = createEmptyQueue_seq(20); //创建空队列enQueue_seq(moveTo, 0x00); //初始状态进队列for (i = 0; i < 16; i++)route[i] = -1; //准备数组route初值route[0] = 0;while (!isEmptyQueue_seq(moveTo) && (route[15] == - 1)){location = frontQueue_seq(moveTo); //取队头状态为当前状态deQueue_seq(moveTo);for (movers = 1; movers <= 8; movers <<= 1)//考虑各种物品移动 if ((0 != (location & 0x08)) == (0 != (location & movers)))//判断农夫与移动的物品是否在同一侧{newlocation = location ^ (0x08 | movers);//计算新状态，代表把船上的（0x08|movers）从一个岸移到另一个岸；（0x08|movers）代表船上有农夫和movers代表的东西if (safe(newlocation) && (route[newlocation] == -1)) //新状态安全且未处理{route[newlocation] = location; //记录新状态的前驱 enQueue_seq(moveTo, newlocation); //新状态入队}}}// 打印出路径if (route[15] != -1)//到达最终状态{printf("The reverse path is : \n");for (location = 15; location >= 0; location = route[location]) {r[a]=location;a++;if (location == 0) break;}for(i=a-1;i>=0;i--){printf("%d ",r[i]);bin_print(r[i]);//用1表示北岸，0表示南岸,用四位二进制数的顺序依次表示农夫、狼、白菜、羊的位置if(r[i]==0) printf("开始\n");//0000else if(r[i]==1) printf(" 农夫独自返回南岸\n"); //0001else if(r[i]==2) printf(" 农夫带着羊返回南岸\n");//0010else if(r[i]==3) printf(" 白菜与羊共同在北岸，不安全\n"); //0011else if(r[i]==4) printf(" 只有狼在北岸，农夫独自返回南岸\n"); //0100else if(r[i]==5) printf(" 狼与羊共同在北岸，不安全\n");//0101else if(r[i]==6) printf(" 农夫独自返回南岸\n");//0110else if(r[i]==7) printf(" 狼、白菜和羊共同在北岸，不安全\n");// 0111else if(r[i]==8) printf(" 农夫独自去北岸\n");//1000else if(r[i]==9) printf(" 农夫把羊带到北岸\n");//1001else if(r[i]==10) printf(" 农夫把白菜带到北岸\n");//1010else if(r[i]==11) printf(" 农夫把白菜带到北岸\n");//1011else if(r[i]==12) printf(" 农夫把狼带到北岸\n");//1100else if(r[i]==13) printf(" 只有白菜在南岸\n");//1101else if(r[i]==14) printf(" 农夫把狼带到北岸\n");//1110else if(r[i]==15) printf(" 农夫把羊带到北岸\n");//1111 putchar('\n');}printf("\n");}elseprintf("No solution.\n");}。
目录引言 (2)1 问题描述 (2)基本要求 (2)2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性； (2)2.2设计一个算法求解农夫过河问题，并输出过河方案； (2)3 概要设计 (2)3.1数据结构的设计。
(2)3.1.1农夫过河问题的模型化 (2)3.1.2 算法的设计 (3)4、运行与测试 (5)5、总结与心得 (6)附录 (6)参考文献 (12)引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。
一条小船只能容下他和一件物品, 只有农夫能撑船。
问农夫怎么能安全过河, 当然狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品单独放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。
1 问题描述一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫设计过河方案。
基本要求2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；2.2设计一个算法求解农夫过河问题，并输出过河方案；3 概要设计3.1 数据结构的设计。
3.1.1农夫过河问题的模型化分析这类问题会发现以下特征:有一组状态( 如农夫和羊在南, 狼和白菜在北) ; 从一个状态可合法地转到另外几个状态( 如农夫自己过河或农夫带着羊过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态集( 这里只有一个, 都在北) 。
问题表示: 需要表示问题中的状态, 农夫等位于南P北( 每个有两种可能) 。
可以采用位向量, 4 个二进制位的0P1 情况表示状态, 显而易见, 共24= 16种可能状态。
从高位到低位分别表示农夫、狼、白菜和羊。
