当前位置:文档之家› 农夫过河问题状态图及程序

农夫过河问题状态图及程序

农夫过河问题状态图及程序
农夫过河问题状态图及程序

农夫过河问题状态图及程序

一、问题需求分析

一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。另外,因为狼能吃羊,而羊爱吃白菜,所以农夫不能留下羊和白菜或者狼和羊单独在河的一边,自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢?

二、算法选择

求解这个问题的最简单的方法是一步一步进行试探,每一步都搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案。

用计算机实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先(breadth_first) 搜索,另一种是深度优先(depth_first) 。

广度优先:

u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态,然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索,一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来,放在这个队列中,

然后顺序取出来分别进行处理,处理过程中把再下一步的状态放在队列里……。

u 由于队列的操作遵循先进先出的原则,在这个处理过程中,只有在前一步的所有情况都处理完后,才能开始后面一步各情况的处理。

三、算法的精化

要模拟农夫过河问题,首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸,1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸,而狼和羊在北岸。

四、算法的实现

完成了上面的准备工作,现在的问题变成:

从初始状态二进制0000(全部在河的南岸) 出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸) 为最终目标,并且在序列中的每一个状态都可以从前一状态通过农夫(可以带一样东西)划船过河的动作到达。

为避免不必要的瞎费功夫,要求在序列中不应该出现重复的状态。为了实现广度优先搜索,算法中需要使用了一个整数队列moveTo,它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态,以及已被发现的能够到达当前这个状态的路径。

由于在这个问题的解决过程中需要列举的所有状态(二进制0000 ~ 1111)一共16种,所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过,若已被访问过则在这个顺序表元素中记入前驱状态值,算法中把这个顺序表叫做route。route 的每个分量初始化值均为-1,每当我们在队列中加入一个新状态时,就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过,或是正被考虑。最后我们可以利用route顺序表元素的值建立起正确的状态路径。

五、程序代码

// farmerProblem.c

// 用队列解决农夫过河问题

#include

#include

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);

}

else

free(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)

// 在队尾插入元素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");

else

queue->f = (queue->f + 1) % queue->MAXNUM; }

DataType frontQueue_seq(PSeqQueue queue)

{

if (queue->f == queue->r)

printf("Empty Queue.\n");

else

return (queue->q[queue->f]);

}

//个体状态判断函数

int farmer(int location)

{

//判断农夫的位置

return (0 != (location &0x08));

}

int wolf(int location)

{

//判断狼的位置

return (0 != (location &0x04)); }

int cabbage(int location)

{

//判断白菜的位置

return (0 != (location &0x02)); }

int goat(int location)

{

//判断羊的位置

return (0 != (location &0x01)); }

//安全状态的判断函数

int safe(int location)

{

// 若状态安全则返回true

if ((goat(location) == cabbage(location)) &&

(goat(location) != farmer

(location)))

return (0);

// 羊吃白菜

if ((goat(location) == wolf(location)) && (goat(location) != farmer

(location)))

return (0);

// 狼吃羊

return (1); // 其他状态是安全的

}

main()

{

int i, movers, location, newlocation;

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); //计算新状态 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])

{

printf("The location is : %d\n", location);

if (location == 0)

exit(0);

}

}

else

printf("No solution.\n");

//问题无解

}

六、测试结果

程序输出按相反的变化方向输出的,真实的情况应该是从0、

9、……、15变化的。

七、总结和体会

这个程序还有很大的改进空间,首先是人性化方面的设计,这个程序最终的输出结果是用10进制的,而我们需要知道的应该是二进制的结果,所以应该直接把结果输出为二进制,还要按开始到最终状态的排序输出。还有一种更为人性化的设计,就是把对应的每个二进制代码代表的含义直接用中文表示出来,这样的结果更直观,方便用户使用。例如:0000时,程序输出:所有的物品都在南岸。后面的一个状态是9(1001),程序输出:农夫和羊到了北岸。

通过这个程序的学习,很受启发,明白了如何用计算机解决实际生活中的问题。刚开始接到这个题目时,感觉到相当困难,因为这种题以前是考验我们的IQ用的,现在没想到要用计算机来解决,而且计算机又没有思想,怎样让它想问题,实现我们需要的功能。原来,可以把实际的问题转变为数学模型,通过计算机超强悍的循环功能和强大的数据处理能

力,把所有可能的结果都算出来,然后用约束项来对这些结果进行筛选,然后把结果用数学格式来输出,让问题得以求解。

这个程序的设计方法比较巧妙的地方是数学建模,即每个角色的位置进行描述的方法:用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸,1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸,而狼和羊在北岸。这个方法令人拍案叫绝,不得不佩服人类的智慧。

农夫过河数据结构

郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容: 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸,要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜;否则狼会吃羊,羊会吃白菜。所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序,并用此程序上机运行、调试,屏幕显示结果,能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限:2012/6/21 指导教师签名: 课程负责人签名: 年月日

郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目:农夫过河 学生姓名: 系别:计算机与通信工程学院 专业:计算机科学与技术 班级:计算机科学与技术 学号: 指导教师: 2012年6 月21 日

一,设计题目 问题描述: 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸,他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜;否则狼会吃羊,羊会吃白菜。所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二,运行环境(软、硬件环境) VC6.0 Windows7系统 三,算法设计的思想 对于这个问题,我们需要先自动生成图的邻接矩阵来存储,主要方法是先生成各种安全状态结点,存放在顶点向量中;再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边,并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后,利用递归深度优先搜索求出从顶点(0,0,0,0)到顶点(1,1,1,1)的一条简单路径,这样做只能搜到一种合理方法,因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四,算法的流程图 要写算法的流程图,必须要先很了解自己的函数结构,我先在纸上手动的把整个过程在纸上画一遍,了解它的大体流程,然后把各个函数给分开,下面是我自己根据我的代码中画的各个函数画的流程图,希望老师满意。 主函数的流程图:

农夫过河问题状态图及程序

农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。另外,因为狼能吃羊,而羊爱吃白菜,所以农夫不能留下羊和白菜或者狼和羊单独在河的一边,自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢? 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探,每一步都搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先(breadth_first) 搜索,另一种是深度优先(depth_first) 。 广度优先: u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态,然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索,一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来,放在这个队列中,

然后顺序取出来分别进行处理,处理过程中把再下一步的状态放在队列里……。 u 由于队列的操作遵循先进先出的原则,在这个处理过程中,只有在前一步的所有情况都处理完后,才能开始后面一步各情况的处理。 三、算法的精化 要模拟农夫过河问题,首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸,1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸,而狼和羊在北岸。 四、算法的实现 完成了上面的准备工作,现在的问题变成: 从初始状态二进制0000(全部在河的南岸) 出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸) 为最终目标,并且在序列中的每一个状态都可以从前一状态通过农夫(可以带一样东西)划船过河的动作到达。

农夫过河问题状态空间表示

逻辑学教授的3个得意门生ABC,前一晚在酒吧喝多了,结果第二天3人集体迟到。教授说:“作为对你们迟到的惩罚,你们3人必须比其他同学多做一道作业,完成了这道作业才可以离开教室。”这道附加的作业是一道帽子题,教授给每人戴了顶帽子,帽子不是红色就是白色,不是白色就是红色。每人都能看见其他2人帽子的颜色,却不能看见自己帽子的颜色。每人都看到其他2人帽子的颜色后,每思考5分钟为一轮,谁猜出自己帽子的颜色了就可以说出来并离开。教授还说:“你们3人中至少有1人戴了红色帽子。” 第一轮下来,A说:“我没猜出来。”B说“我也没猜出来”C说:“我也猜不出。” 第二轮下来,还是没人能猜出自己帽子的颜色。 第三轮,3人都猜出了自己帽子的颜色。 问:ABC三人头顶都是什么颜色的帽子?然后用谓词逻辑写出推理过程。 最一般合一及归结反演相关 已知w={P(f(x,g(A,y)),z), P(f(x,z),z),求MGU 令δ0=ε,w0=w,因w中含有两个表达式,因此δ0不是最一般合一 差异集D0={g(A,y)/z} δ1=δ0oD0={g(A,y)/z} w1={P(f(x,g(A,y)),g(A,y)), P(f(x,g(A,y)),g(A,y)) w1中仅含有一个表达式,所以δ1就是最一般合一。 证明G是否是F1、F2的逻辑结论。 F1:(?x)(P(x)→(Q(x)∧R(x))) F2:(?x)(P(x)∧S(x)) G: (?x)(S(x)∧R(x)) F1: ?P(x)∨(Q(x)∧R(x)) ? (?P(x)∨Q(x)) ∧ (?P(x)∨R(x)) F2: P(x)∧S(x) ?G: ?(?x)(S(x)∧R(x)) ? (?x)(?(S(x)∧R(x))) ? ?S(x)∨?R(x) 子句集: 1 ?P(x)∨Q(x) 2 ?P(x)∨R(x) 3 P(x) 4 S(x) 5 ?S(x)∨?R(x) 其中2与3规约,4与5归结,其结果再归结得到空子句,证明G是F1与F2的结论。 农夫过河问题 (1)农夫每次只能带一样东西过河 (2)如果没有农夫看管,狼吃羊,羊吃菜 要求: 设计一个过河方案,使得农夫、狼、羊、菜都能过河,画出相应的状态空间图。 四元组S表示状态,即S=(农夫,狼,羊,菜) 用0表示在左岸,1表示在右岸 初始S=(0,0,0,0) 目标G=(1,1,1,1)

农夫过河和骑士周游(数据结构课程设计)教学内容

1:实验要求 1.1实验目的 掌握图的遍历问题,运用图的遍历算法解决复杂问题。掌握并应用邻接存储结构和图的深度遍历问题。培养学习使用图的相关知识解决实际问题的能力。 1.2实验内容问题描述 问题描述:农夫携带一只狼,一只羊,一棵白菜从和的左岸到达河的右岸,由于船只较小,农夫每次只能携带一样过河,在无人看管的情况下狼吃羊,羊吃白菜。 1.3:实验输出要求 要求输出农夫携带所有东西安全过河的步骤。 2:程序设计分析 2.1:实验内容分析 农夫需要多次驾船往返于河的左右两岸,农夫每次过河都会使农夫,狼,羊,白菜的位置发生变化。利用四元组(农夫,狼,羊,白菜)来表示各自所处于河的左岸右岸的位置,0表示河的左岸,1表示河的右岸。初始状态时(0,0,0,0)都处在河的左岸,终态是(1,1,1,1)四者都处在河的右岸。 共有16种状态,但其中有些状态不安全,删除不安全的状态,将安全的状态按照合理的过河步骤联系起来. (0,0,0,0) (1,0,1,0) (0,0,1,0) (1,1,1,0) (1,0,1,1) (0,1,0,0) (0,0,0,1) (1,1,0,1) (0,1,0,1) (1,1,1,1) 安全过河状态图 2.2主要函数模块算法分析

1:栈的相关函数 PSeqStack Init_SeqStack(void) //栈的初始化 int Empty_SeqStack(PSeqStack s) //判断栈是否为空栈非空1表示栈空 void Push_SeqStack(PSeqStack s,int x) //入栈 int Pop_SeqStack(PSeqStack s,int *x) //出栈 int Size_SeqStack(PSeqStack s) //顺序栈中元素的个数 void Destroy_SeqStack(PSeqStack *S) //销毁栈 2,:求结点直接后继结点个数的函数 int CountAdjoin(MGraph *G,int u) 3:查找状态(f,w,s,v)在无向图中的位置的函数 int located(MGraph *G,int f,int w,int s,int v) 4:结点值安全状态判断函数 int if_safe(int f,int w,int s,int v) 5:判断农夫过河的两个状态是否是相邻的函数 int if_connected(MGraph *G,int i,int j) 6:创建农夫过河状态的无向图 void Creat_MGraph(MGraph *G) 7:广优度先遍历遍历所有从状态下标u到状态下标v的路径函数 void BFS_path(MGraph *G,int u,int v) 8:输出所有从状态下标为u到状态下标为v的所有简单路径 void print_path(MGraph *G,int u,int v) 2.3部分函数源代码 path[u][m] 为状态下标u的直接后继状态下标 m表示状态下标u的直接后继结点个数:int path[MaxVertexNum][MaxVertexNum]; 主要结构:typedef struct { int farmer; int wolf; int sheep; int vegetable;

C# 关于农夫过河的问题

课程设计第五题 1.题目探讨农夫过河的问题 2.设计思路 (1)农夫由A到B的情况 (1)带走一个动物后,另外的两个物是不是可以相吃 (2)会不会把刚带回来的又带到对岸去 (3)最后一次带的情况比较的特殊,判断最后一次走后是不是所有的都不在了对岸 (2)农夫从B到A的情况 (1)对岸是不是只有一个物体 (2)对岸是不是有两个物体,若是有两个物体的话他们的处理方式不一样,1。两个物体会相克的,则把羊带走,2如果不是的话那么农夫就空着手回去。 3.应该注意的问题 (1)。在最后的一次带走羊的时候,应该加如一个新的判段 (2)。以及在带回羊的时候,我们要对其进行一个标记,不然的话我们就很容易进行死循环里面 (3)以及每一次从A带东西去B的时候,我们都要对他的位置进行标记下 4.咸受 在对一个问题分析的时候,我们应该先把每一种情况给分析出来,要把问题分析得分面一些,最好是不要落下任何的一种情况,这样我们就可以对每一种情况编写相应的代码了。5.源代码 static int sum(int[] a) { int sum = 0; for (int i = 0; i < a.Length; i++) { sum = sum + a[i]; } return sum; } static void Main(string[] args) { string[] wu = new string[4] { "农夫", "狼", "羊", "白菜" }; int[] a = new int[4] { 3, 1, -1, 1 }; int[] b = new int[4] { 0, 0, 0, 0 }; Console.WriteLine(" 关于农夫过河的问题"); int weizhi = 0; do { if (a[0] == 3) {

农夫过河问题

课程设计题目:农夫过河 一.问题描述 一个农夫带着一只狼、一只羊和一箩白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。过河有以下规则: (1)农夫一次最多能带一样东西(或者是狼、或者是羊、或者是白菜)过河; (2)当农夫不在场是狼会吃羊; (3)当农夫不在场是羊会吃掉白菜。 现在要求为农夫想一个方案,能将3样东西顺利地带过河。从出事状态开始,农夫将羊带过河,然后农夫将羊待会来也是符合规则的,然后农夫将羊带过河仍然是符合规则的,但是如此这般往返,搜索过程便进入了死循环,因此,在这里,采用改进的搜索算法进行搜索。 二.基本要求 (1)为农夫过河问题抽象数据类型,体会数据模型在问题求解中的重要性; (2)要求利用数据结构的方法以及C++的编程思想来完成问题的综合设 计; (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结构体是为了储图的顶点数与边数,农夫过河问题我采用的是图的深度优先遍历思想。 (2)算法的设计 深度优先遍历基本设计思想:设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的1/12边(x,y)。若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。 程序中的深度优先遍历算法如下: void dfsPath(AdjGraph *graph, int start, int end) // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end)

趣味数学教案—农夫过河

农夫过河 教学目标 1、知识与能力:通过农夫过河的数学逻辑问的题,探讨研究找到解决问题的办法和养成自己动脑动手的解决问题的能力。 2、过程与方法:通过以角色扮演的形式让学生自己动脑动手寻找答案和探讨解决问题的方法。 3、态度价值观:知道数学有很多有趣的东西,培养爱科学的情感。教师准备 1. 数学课件。 2、做“狼、羊、白菜、农夫”头饰。 3、准备四张纸分别写上“狼、羊、白菜、农夫”。 教学过程 一、谈话导入 介绍我国著名的数学家华罗庚爷爷。 数学家华罗庚生平介绍,主要科学业绩,对数学的贡献等等。介绍华罗庚爷爷的话。“数学本身,也是无穷的美妙,认为数学枯燥,是不正确的,就像站在花园外面,说花园枯燥无味一样,只要你踏进大门,随时会发现数学有许多有趣的东西。”数学并不是几个数字算来算去,它的学问大着呢。下面这道题能引起你的兴趣吗? 二、创设情境 1、出示数学问题:有一个农夫带一匹狼、一只羊和一棵白菜过河(从河的东岸到西岸)。如果没有农夫看管,则狼要吃羊,羊要吃白菜。

但是船很小,只够农夫带一样东西过河。 2、图片演示。(一条河;一边是对岸;另一边是河岸,有农夫、狼、羊、白菜) 三、探究学习 1、以小组表演形式(演示出河的位置)和讨论形式解题 第一步是什么?必须是什么?(农夫和羊先过河) 第二步是什么?(农夫自己回来) 第三步是什么? 2、全班学生汇报交流 问题的突破口在——狼与白菜能够共存!农夫、狼、羊、白菜和船组成了这个系统。系统中各要素是一个整体,都依赖农夫过河;最大的问题是“船很小,只够农夫带一样东西过河”和“没有农夫看管,则狼要吃羊,羊要吃白菜”的冲突。我们联系已知条件,做了一系列的分析实验,但是比较其他方案不能实现所有要素都安全过河。最后得出以上方案。 具体描述如下: 第一步:把羊带过河,坐船返回; 第二步:把狼带过河,带羊返回; 第三步:将羊放在这一岸后,带白菜过河; 第四步:坐船返回,把羊带过河。 或者: 第一步:把羊带过河,坐船返回;

数据结构课程设计报告(农夫过河)

目录 引言 (2) 1 问题描述 (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 概要设计 3.1 数据结构的设计。 3.1.1农夫过河问题的模型化 分析这类问题会发现以下特征: 有一组状态( 如农夫和羊在南, 狼和白菜在北) ; 从一个状态可合法地转到另外几个状态( 如农夫自己过河或农夫带着羊过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态集( 这里只有一个, 都在北) 。 问题表示: 需要表示问题中的状态, 农夫等位于南P北( 每个有两种可能) 。可以采用位向量, 4 个二进制位的0P1 情况表示状态, 显而易见, 共24= 16种可能状态。从高位到低位分别表示农夫、狼、白菜和羊。0000( 整数0) 表示都在南岸, 目标状态1111( 即整数15) 表示都到了北岸。有些状态0011,0101, 0111, 0001, 1100, 1001 是不允许出现的, 因为这些状态是不安全状态。根据上述条件可以画出系统的状态图如图1 所示。 图1 系统状态转换图 其中双向的箭头表示状态可逆, 即农夫可以带 着某种东西过去, 也可以带着该东西回来。箭头上的字母表示农夫所携带的东西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。现在的问题转化为: 找一条合法路径( 相邻状态之间的转移合法) , 从开始状态到某个结束状态, 途中不经过不安全状态。

数据结构课程设计农夫过河问题

扬州大学信息工程学院 《数据结构》 ---课程设计报告 题目:农夫过河 班级:网络1501 学号:1524 姓名:王 指导教师:王

一、课程题目 一个农夫带着一只狼,一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。 二、需求分析 求出农夫将所有的东西运过河的方案。 三、概要设计 求解这个问题的简单的方法是一步一步进行试探,每一步搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案。要模拟农夫过河问题,首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸,1表示在河的北岸。例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸,而狼和羊在北岸。现在问题变成:从初始状态二进制0000(全部在河的南岸) 出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸)为最终目标,并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫,要求在序列中不出现重复的状态。 四、详细设计 实现上述求解的搜索过程可以采用策略广度优先(breadth_first) 搜索。广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态,再进一步考虑更后面的各种情况。要实现广度优先搜索,可以使用队列。把下一步所有可能的状态都列举出来,放在队列中,再顺序取出来分别进行处理,处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则,在这个处理过程中,只有在前一步的所有情况都处理完后,才能开始后面一步各情况的处理。这样,具体算法中就需要用一个整数队列moveTo,它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态,以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000 -1111)一共16种,所以可以构造一个包含16个元素的整数顺序表来实现。顺序表的第i个元素记录状态i是否已被访问过,若已被访问过则在这个顺序表元素中记入前驱状态值,把这个顺序表叫做route。route的每个分量初始值均为-1。route的一个元素具有非负值表示这个状态已访问过,或是正被考虑。最后可以利用route顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。在具体应用时,采用链队和顺序队均可,为叙述的方便,不妨设为使用顺序队。 模块划分 1、void BA() //农夫从B岸到A岸 2、void xu() //初始化三样东西的位置 3、void f() //判断农夫的位置 4、int g() //判断羊的位置 5、void huan () //农夫返回 6、void AB() //农夫从A岸到B岸

农夫过河实验报告

“数据结构与算法综合实验”课程设计报告题目:农夫过河问题 学院计算机科学技术 年级2014级 专业计算机科学与技术 学号20142060 姓名高晗 日期2016年3月30日星期三 成绩 评语 黑龙江大学 计算机科学技术学院、软件学院

《数据结构与算法综合实验》报告 1.系统概述 (1)一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸,他要把这些东西全部运到北岸。他面前只有一只小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜;否则狼会吃羊,羊会吃白菜。所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。 (2)为农夫过河问题抽象数据模型,体会数据模型在求解问题中的重要作用。 (3)掌握顺序表和队列的逻辑结构和存储结构。 2.系统需求分析 (1)针对实现整个过程需要多步,不同步骤中各个事物所处位置不同的情况,可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸,可以用0或者1来表示,以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤,没有对先后顺序进行约束,这就需要给各个事物依次进行编号,然后依次试探,若试探成功,进行下一步试探。这就需要使用循环或者递归算法,避免随机盲目运算且保证每种情况均试探到,不接受非法输入。 (3)题目要求求出农夫带一只羊,一条狼和一颗白菜过河的办法,所以依次成功返回运算结果后,需要继续运算,直至求出结果,即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体,需要定义不同的数组来分别存储上述内容,并使界面所示方案清晰简洁。 (4)实验运行环境为VC++6.0. 3.系统概要设计 (1)数据结构设计 要模拟农夫过河的问题,用四位二进制数顺序分别表示农夫,狼,羊,白菜的位置。用0表示农夫或某种东西在河的南岸,1表示在河的北岸。则问题的初

农夫过河实验报告――数据结构

数据结构实验报告 ——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构,进一步提高使用理论知识指导解决实际问题的能力。 一、【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。请求出农夫将所有的东西运过河的方案。 二、【数据结构设计】 求解这个问题的简单的方法是一步一步进行试探,每一步搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题,首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸,1表示在河的北岸。例如整数5(其二进制表示为0101)表示农夫和白菜在河的南岸,而狼和羊在北岸。 现在问题变成:从初始状态二进制0000(全部在河的南岸)出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸)为最终目标,并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫,要求在序列中不出现重复的状态。 实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先(breadth_first)搜索, 另一种是深度优先(depth_first)搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态,再进一步考虑更后面的各种情况。要实现广度优先搜索,可以使用队列。把下一步

任务书-农夫过河问题的逻辑建模与程序验证

上海工程技术大学 毕业设计(毕业论文)任务书 学院继续教育学院 专业计算机科学与技术 班级学号 学生王俊佶 指导教师张辉 题目农夫过河问题的逻辑建模与程序验证 任务规定 进行日期自2011 年9 月?日起,至2012 年 1 月?日止

一、题目来源、目的、意义 数理逻辑作为基础数学的一个重要分支,在通信、电子及计算机科学中起着奠基作用,在模糊数学和人工智能等方面也都有着广泛的应用,其中有限模型、解析算法、有限计算和可判定性等内容都与计算机的软硬件密切相关。 各种游戏的设计,离不开游戏环境的规范描述,大多数使用的都是一个逻辑上的满足关系M╞φ,其中M是某种游戏的场景或模型,而φ是一个情节的规范。本课题可以有效地锻炼学生的综合应用已有知识、自学新知识的能力,使学生有效的对大学所学过的知识进行深入的总结。 二、主要工作内容 本课题利用逻辑语言Alloy或模型检测工具SMV,通过对农夫过河游戏的场景进行逻辑建模,求解智力难题,充分理解和体会逻辑在软件规范中的作用,学习逻辑程序设计的基本原理和培养实际的开发经验,是对计算机软件与理论教学的有效拓展。 1.学习数理逻辑的基础知识 2.学习逻辑语言Alloy或模型验证工具SMV 3.编写出描述农夫过河游戏的逻辑规范程序 4.程序测试,并对错误进行适当处理

三、主要技术指标(或主要论点) 1. 农夫过河游戏的逻辑模型描述 2. 逻辑语言Alloy程序的开发或模型验证工具SMV的运用 3. 程序结果分析 四、进度计划 第一至二周:进行市场调研和文献检索,并进行整理,写出开题报告; 第三周:外文资料翻译,配置程序开发环境; 第四至五周:学习数理逻辑基础知识和时态逻辑的原理; 第六到七周:学习使用逻辑语言Alloy或模型验证工具SMV; 第八周:设计农夫过河游戏的逻辑模型; 第九至十一周:初步设计逻辑程序; 第十二至十四周:调试逻辑程序; 第十五至十八周:论文写作及答辩。

农夫过河问题

一、题目:农夫过河问题 二、目的与要求 1、目的: 通过布置具有一定难度的实际程序设计项目,使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法,以及它们在程序中的使用方法;使学生掌握分析问题,求解问题的方法并提高学生设计编程实现的能力。 2、要求: 基本要求: 1.要求利用C\C++语言来完成系统的设计; 2.突出C语言的函数特征(以多个函数实现每一个子功能)或者C++语言面向对象的 编程思想; 3.画出功能模块图; 4.进行简单界面设计,能够实现友好的交互; 5.具有清晰的程序流程图和数据结构的详细定义; 6.熟练掌握C语言或者C++语言的各种操作。 创新要求: 在基本要求达到后,可进行创新设计,如系统用户功能控制,改进算法的实现,实现友好的人机交互等等 三、问题描述和求解方法: 1 、问题描述 要求设计实现农夫过河问题(农夫带着一只狼,一只养,一棵白菜,一次只能带一个东西)如何安全过河。 2 、问题的解决方案: 可以用栈与队列、深度优先搜索算法及广度优先搜索算法相应的原理去解决问题。 1)实现四个过河对象(农夫、白菜、羊和狼)的状态,可以用一个四位二进制数来表示, 0表示未过河,1表示已经过河了。 2)过河的对象必须与农夫在河的同一侧,可以设计函数来判断。 3)防止状态往复,即农夫将一个东西带过去又带回来的情况发生,需将所有可能的状态 进行标定。 4)可用深度优先搜索算法及广度优先搜索算法去解题。 四、解题过程 1.分析程序的功能要求,划分程序功能模块。 2.画出系统流程图。 3.代码的编写。定义数据结构和各个功能子函数。 4.程序的功能调试。 5.完成系统总结报告以及使用说明书

数据结构—农夫过河问题

题目: 一个农夫带着一匹狼、一只羊、一颗白菜要过河,只有一条船而且农夫每次最多只能带一个动物或物品过河,并且当农夫不在的时候狼会吃羊,羊会吃白菜,列出所有安全将所有动物和物品带过河的方案。 要求:广度优先搜索农夫过河解,并输出结果 源代码: #include #include 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); } else free(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"); else queue->f = (queue->f + 1) % queue->MAXNUM; } DataType frontQueue_seq(PSeqQueue queue)//取队头元素 { if (queue->f == queue->r) printf("Empty Queue.\n"); else return (queue->q[queue->f]);

数据结构实验-农夫过河问题

农夫过河问题 一、实验目的 掌握广度优先搜索策略,并用队列求解农夫过河问题 二、实验内容 问题描述: 一农夫带着一只狼,一只羊和一颗白菜,身处河的南岸,他要把这些东西全部运到北岸,遗憾的是他只有一只小船,小船只能容下他和一件物品。这里只能是农夫来撑船,同时因为狼吃羊、羊吃白菜、所以农夫不能留下羊和狼或羊和白菜在河的一边,而自己离开;好在狼属肉食动物,不吃白菜。农夫怎么才能把所有的东西安全运过河呢?实验要求如下: (1)设计物品位置的表示方法和安全判断算法; (2)设计队列的存储结构并实现队列的基本操作(建立空队列、判空、入队、出队、取对头元素),也可以使用STL中的队列进行代码的编写; (3)采用广度优先策略设计可行的过河算法; (4)输出要求:按照顺序输出一种可行的过河方案; 提示:可以使用STL中的队列进行代码编写。 程序运行结果: 二进制表示:1111 0110 1110 0010 1011 0001 1001, 0000 三、农夫过河算法流程 ?Step1:初始状态0000入队 ?Step2:当队列不空且没有到达结束状态1111时,循环以下操作: ?队头状态出队 ?按照农夫一个人走、农夫分别带上三个物品走,循环以下操作: ?农夫和物品如果在同一岸,则计算新的状态

?如果新状态是安全的并且是没有处理过的,则更新path[ ],并将新状态入队 ?当状态为1111时,逆向输出path[ ]数组 附录一:STL中队列的使用 注:队列,可直接用标准模板库(STL)中的队列。需要#include 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 queue push:Adds an element to the back of the queue empty:Tests if the queue is empty 三、实验代码 FarmerRiver.H #ifndef FARMERRIVER_H #define FARMERRIVER_H int FarmerOnRight(int status); //农夫,在北岸返回1,否则返回0 int WorfOnRight(int status); //狼 int CabbageOnRight(int status); //白菜 int GoatOnRight(int status); //羊 int IsSafe(int status); //判断状态是否安全,安全返回1,否则返回0 void FarmerRiver(); #endif SeqQueue.h #ifndef SEQQUEUE_H #define SEQQUEUE_H typedef int DataType; struct Queue { int Max;

数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河

八皇后问题 1.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子(这里的棋子指皇后棋子)。然后顺序在第1行,第2行……第8行上布放棋子。在每一行中共有8个可选择的位置,但在任一时刻棋盘的合法布局都必须满足3个限制条件(1)任意两个棋子不得放在同一行(2)任意两个棋子不得放在同一列上(3)任意棋子不得放在同一正斜线和反斜线上。 2.基本要求 编写求解并输出此问题的一个合法布局的程序。 3、实现提示: 在第i行布放棋子时,从第1列到第8列逐列考察。当在第i行第j列布放棋子时,需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法,若该棋子布放合法,再递归求解在第i+1行布放棋子;若该棋子布放不合法,移去这个棋子,恢复布放该棋子前的状态,然后再试探在第i行第j+1列布放棋子。 4 程序代码 #include #include static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int QueenNum=0;//记录总的棋盘状态数 void qu(int i);//参数i代表行

{ int Line,Column; //棋盘初始化,空格为*,放置皇后的地方为@ for(Line=0;Line<8;Line++) { a[Line]=0; //列标记初始化,表示无列冲突 for(Column=0;Column<8;Column++) Queen[Line][Column]='*'; } //主、从对角线标记初始化,表示没有冲突 for(Line=0;Line<15;Line++) b[Line]=c[Line]=0; qu(0); return 0; } void qu(int i) { int Column; for(Column=0;Column<8;Column++) { if(a[Column]==0&&b[i-Column+7]==0&&c[i+Column]==0) //如果无冲突 { Queen[i][Column]='Q'; //放皇后 a[Column]=1;//标记,下一次该列上不能放皇后 b[i-Column+7]=1;//标记,下一次该主对角线上不能放皇后 c[i+Column]=1;//标记,下一次该从对角线上不能放皇后 if(i<7) qu(i+1); //如果行还没有遍历完,进入下一行 else//否则输出

农夫过河问题

农夫过河问题 1. 题目描述: 一个农夫带着一只狼,一只羊和一筐菜,欲从河的左岸坐船到右岸,由于船 太小,农夫每次只能带一样东西过河,并且没有农夫看管的话,狼会吃掉羊, 羊会吃菜。设计一个方案,使农夫可以无损失的过河 2. 题目分析: 假设人、狼、菜、羊都在河岸a,要到b 河岸去。 题中的食物链关系为: 菜→羊→狼 所以,第一次人只能带羊到b 河岸; 回到a 时,人不能再将刚带过来的羊带回去,所以人是空手回到a 的; 在a 河岸,人有两个选择 选择一: (1) 带狼到b,人再回到a 时,因为不能把狼和羊同时留下,所以只能带走羊; A A 羊 A B 羊 狼 菜 怎么办呢 B 羊 B 狼 菜 菜 狼

(2) 再次回到a 后,人再到b 时,不能把羊和菜同时留下,所以只能带走菜; (3) 再次回到a 时,因为狼和菜可以同时留下,所以优先选择空手过河;到a 后发现只剩下羊,所以带羊过河。 选择二: (1) 带菜到b,人再回到a 时,因为不能把菜和羊同时留下,所以只能带走 羊; (2) 再次回到a 后,人再到b 时,不能把羊和狼同时留下,所以只能带走 狼; 狼 羊 羊 A 菜 B 羊 狼 A B 狼 A B 狼 A B 羊 菜 菜 菜

(3) 再次回到a 时,因为狼和菜可以同时留下,所以优先选择空手过河; 到a 后发现只剩下羊,所以带羊过河。 解:用四元组S 表示状态,即S =(L ,J ,M ,N ) 其中L :农夫 J :狼 M :羊 N :菜 用0表示在左岸岸,1表示在右岸,即S=(0,0,0,0) 目标G =(1,1,1,1) 定义操作符L (i )表示农夫带东西到右岸: i=0 农夫自己到右岸; i=1 农夫带狼到右岸; i=2 农夫带羊到右岸; i=3 农夫带菜到右岸; 定义操作符R (i )表示农夫带东西到左岸: i=0 农夫自己到左岸; i=1 农夫带狼到左岸; i=2 农夫带羊到左岸; i=3 农夫带菜到左岸; 约束状态如下:(1,0,0,1)狼、羊在左岸; (1,1,0,0)羊、菜在左岸; (0,1,1,0)狼、羊在右岸; (0,0,1,1)羊、菜在右岸; (1,0,0,0)狼、羊、菜在左岸; (0,1,1,1)狼、羊、菜在右岸; 羊 A B 狼 菜

农夫过河问题

农夫过河问题 1.问题描述 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。 要求:利用图的存储结构和图的搜索算法,求出农夫将所有的东西运过河的方案。 2.需求分析 2.1规定程序功能 本题要解决的问题就是农夫如何带着狼、羊、白菜安全过河。要求是船只能容下他和一件物品,另外只有农夫才能撑船。如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜。 2.2输入和输出形式 本程序自动完成所有情况的输入,不需要人为的输入。然后根据程序里面调用相应函数模块可得到一种过河方案,然后自行输出。输出的是农夫过河每一步的方案,即每一步中农夫采取的行动。 3.概要设计 3.1数据结构的设计 题目要求用图的存储结构,所以要想办法将农夫、狼、羊、白菜每一步的状态用结点表示,他们状态的改变到下一个结点可行,则在两条结点中加一条边。但是每个结点包含四个量,如果他们每个都各自用一个结构体表示,则图形就变得相当的繁琐,因此想到一个简单的结局办法。河的两岸是两个不同的变量,刚好可以用0和1表示,那么四个状态量都用0和1则可表示他们每一步所处的位置,也就能明白农夫每次是怎么过河的。 3.2算法的设计 本程序可以分成四个模块,分别是:找到所有情况的点、从中挑选出满足题意的点、创建满足题意的点之间的边、通过图的深度优先遍历找到过河方案。 各模块之间的关系图如下:

相关主题
相关文档 最新文档