农夫过河 实验报告

农夫过河问题——程序设计(2009-06-05 13:38:22)标签：分类：一、问题需求分析一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。

他要把这些东西全部运到北岸。

问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。

另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。

请问农夫该采取什么方案才能将所有的东西运过河呢？二、算法选择求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。

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

广度优先：u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。

u 要实现广度优先搜索，一般都采用队列作为辅助结构。

把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。

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

三、算法的精化要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。

一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。

例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。

因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。

四、算法的实现完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。

农夫过河问题一、需求分析1.问题描述：一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。

他要把这些东西全部运到北岸。

他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。

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

2.基本要求:（1）利用图的存储结构（2）图的搜索算法（3）求出农夫将所有的东西运过河的所有方案二、设计1. 设计思想（1）存储结构以邻接矩阵存储合理状态，用一个一维数组保存所有的方案；（2）主要算法基本思想人，狼，羊和白菜共有2的四次方16种状态（河岸的状态可由人的状态确定），去掉不允许出现的6种状态，10个状态对应矩阵的10个结点值，然后根据状态的连续改变初始化矩阵，接着就用递归的深度优先法搜索所有的路径，即求出过河的方案。

main2. 设计表示（1）函数调用关系图main→Judge→Initiate→DFS→Push→StackPop→Top→GetTop→printfpath→Ch（2）函数接口规格说明int Judge(int a,int b) //将16种状态通过a，b输入，去掉不允许的6种int GetTop(Path *path,int *m) //出栈int Push(Path *path,int m) //入栈int Top(Path *path ,int *m) //读出栈顶值void Initiate(AdjMGraph *G,int n)//邻接矩阵顶点数为n的邻接矩阵G的建立int DFS(AdjMGraph *G,Path *path,int x,int t) 图G中搜索的起始点为X，从t点开始搜索与x关联的顶点，搜索过的点入栈path。

int printfpath(Path *path) //复制出出栈path中所有值，用FA【】保存void Printf(AdjMGraph *G)//辅助：邻接矩阵输出，用于观察搜索的过程。

一、实验目的1. 了解动物行为学的基本概念，观察动物在不同环境下的行为反应。

2. 探究小黄鸭在过河过程中的行为特点，分析其适应环境的能力。

3. 培养学生的观察、分析、总结能力。

二、实验原理动物行为学是研究动物在自然界中的行为规律和适应策略的学科。

通过观察小黄鸭过河的行为，可以了解其在不同环境下的适应能力，以及动物行为与环境因素之间的关系。

三、实验材料与工具1. 实验材料：小黄鸭、水桶、河岸、摄像机、记录表等。

2. 实验工具：摄像机、录音笔、计时器等。

四、实验方法1. 实验分组：将小黄鸭分为实验组和对照组，实验组过河，对照组在河岸观察。

2. 实验步骤：（1）将小黄鸭放入水桶中，观察其在水中的行为；（2）将水桶移至河岸，模拟小黄鸭过河的过程；（3）记录小黄鸭过河的时间、速度、路线等行为特点；（4）观察小黄鸭在过河过程中的适应能力，如游泳、潜水、攀爬等；（5）对实验数据进行统计分析。

五、实验结果与分析1. 实验结果（1）实验组小黄鸭过河的时间平均为10秒；（2）对照组小黄鸭在河岸观察的时间平均为15秒；（3）实验组小黄鸭在过河过程中，游泳、潜水、攀爬等行为均有出现。

2. 实验分析（1）实验组小黄鸭过河的时间较短，说明其具有较强的适应能力；（2）对照组小黄鸭在河岸观察的时间较长，说明其对过河环境不熟悉，适应能力较弱；（3）实验组小黄鸭在过河过程中，游泳、潜水、攀爬等行为的出现，表明其具有较强的适应环境的能力。

六、实验结论1. 小黄鸭在过河过程中具有较强的适应能力，能够通过游泳、潜水、攀爬等方式应对环境变化；2. 观察动物行为有助于了解其在自然界中的生存策略，为动物保护提供参考。

七、实验讨论1. 本实验结果表明，小黄鸭在过河过程中具有较好的适应能力，这与其在自然界中的生存环境密切相关；2. 实验过程中，对照组小黄鸭在河岸观察的时间较长，说明其在过河前需要一定的时间来熟悉环境，提高适应能力；3. 本实验为动物行为学研究提供了新的思路，有助于进一步了解动物在自然界中的生存策略。

青蛙过河实验报告总结引言本实验旨在通过观察和记录青蛙在不同条件下过河的行为，探究青蛙在不同河流环境中的适应能力和行为模式。

通过实验，我们进一步了解了青蛙的特性和行为习惯，对生态学领域的研究和保护工作具有一定的参考意义。

实验方法实验使用的设备和材料包括：一条模拟河流，距离标记板，青蛙，记录表格等。

实验过程如下：1. 准备河流：在实验区域搭建模拟河流，确保河流的长度、水流速度和水深能在一定范围内进行调节。

在距离标记板上分别标注不同距离的刻度，用于测量青蛙从起点到达不同距离的时间。

2. 实验组设置：选取不同种类、不同个体的青蛙作为实验对象。

将青蛙放置在河流起点，记录青蛙从起点到达不同距离所花费的时间。

每组实验重复3次，取平均值作为结果数据。

3. 数据记录与分析：将实验过程中观察到的数据记录在表格中，包括青蛙种类、个体、距离和所需时间等信息。

通过对数据的分析和比较，得出相应的结论。

实验结果与讨论结果呈现在实验中，我们观察到不同种类的青蛙在通过模拟河流时表现出了不同的行为模式。

以下是我们得到的主要结果：1. 青蛙种类差异：我们选取了可跳跃类青蛙和游泳类青蛙作为实验对象，发现可跳跃类青蛙在通过短距离的水域时表现出较好的适应能力，而游泳类青蛙在长距离的水域中更加游刃有余。

2. 个体差异：在同一种类的青蛙中，不同个体之间也存在着差异。

有些青蛙表现出较好的跳跃能力或游泳能力，而有些则相对较差。

这种个体差异可能与青蛙体型大小、年龄和健康状况等因素相关。

3. 距离与时间关系：我们观察到青蛙在越短的距离内通过水域所需时间越短，而在较长的距离上则需要更多的时间。

这与跳跃和游泳所需的能量消耗以及行动的效率有关。

结果讨论通过以上结果的观察和分析，我们可以得出以下一些结论和讨论：1. 青蛙的适应能力：不同种类的青蛙在过河实验中表现出了不同的适应能力。

可跳跃类青蛙具有较好的腿力和跳跃能力，而游泳类青蛙则具备较好的水生适应能力。

这与它们在不同生态环境中的生活习惯和适应能力相吻合。

课程设计题目：农夫过河一．问题描述一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。

他要把这些东西全部运到北岸。

他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。

过河有以下规则：(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结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。

农夫过河C语言课程设计一、课程目标知识目标：1. 理解C语言中基本的数据类型和语法结构；2. 学会使用C语言进行逻辑判断和循环控制；3. 掌握C语言中的函数定义和调用方法；4. 了解“农夫过河”问题的背景和解决方案。

技能目标：1. 能够运用C语言编写出解决“农夫过河”问题的程序；2. 培养逻辑思维和问题分析能力，将实际问题转化为程序代码；3. 提高编程实践能力，学会调试和修改代码，解决程序中的错误。

情感态度价值观目标：1. 激发学生对编程的兴趣，培养计算机科学素养；2. 培养学生面对问题积极思考、勇于探索的精神；3. 强调团队合作，学会与他人共同解决问题，培养沟通与协作能力。

分析课程性质、学生特点和教学要求：本课程为C语言编程课程，旨在让学生掌握C语言的基本知识，并通过解决实际问题，提高编程能力。

学生为初中生，具有一定的逻辑思维能力和数学基础。

教学要求注重实践，将理论教学与实际操作相结合，引导学生主动参与，培养其独立思考和解决问题的能力。

课程目标分解：1. 知识目标：通过讲解和实例演示，让学生掌握C语言的基本知识；2. 技能目标：通过编写“农夫过河”程序，提高学生的编程实践能力；3. 情感态度价值观目标：通过课程教学，激发学生对编程的兴趣，培养其积极思考、勇于探索的精神，以及团队合作能力。

二、教学内容1. C语言基础知识回顾：- 数据类型、变量、常量- 运算符、表达式、语句- 选择结构（if-else）- 循环结构（for、while、do-while）2. 函数定义与调用：- 函数的概念和作用- 函数的定义、声明和调用- 递归函数的原理和应用3. “农夫过河”问题分析：- 问题的描述和规则- 状态表示和状态空间- 搜索策略（深度优先、广度优先）4. 编程实践：- 设计“农夫过河”问题的算法- 编写C语言程序实现算法- 调试和优化程序5. 教学内容安排与进度：- 第一课时：C语言基础知识回顾，引入“农夫过河”问题- 第二课时：函数定义与调用，分析问题并设计算法- 第三课时：编写程序，实现“农夫过河”算法- 第四课时：调试优化程序，总结经验，展示成果教学内容关联教材章节：- 《C语言程序设计》第一章：C语言概述- 《C语言程序设计》第二章：数据类型与运算符- 《C语言程序设计》第三章：控制结构- 《C语言程序设计》第四章：函数- 《C语言程序设计》第十章：算法与程序设计实例教学内容注重科学性和系统性，结合教材章节，使学生能够在掌握C语言基础知识的基础上，学会解决实际问题，提高编程能力。

课程设计农夫过河一、教学目标本章节的教学目标包括以下三个方面：1.知识目标：学生能够理解并掌握“农夫过河”问题的背景、条件和目标，了解相关的数学知识，如线性方程、不等式等。

2.技能目标：学生能够运用所学的数学知识，通过分析和逻辑推理，找到解决问题的方法，并能够进行有效的沟通和合作。

3.情感态度价值观目标：学生能够培养问题解决的兴趣和自信心，培养团队合作和沟通的能力，培养对数学学科的积极态度。

二、教学内容本章节的教学内容主要包括以下几个部分：1.引入“农夫过河”问题的背景和条件，引导学生了解问题的目标和意义。

2.引导学生学习相关的数学知识，如线性方程、不等式等，并通过例题和练习题进行巩固。

3.引导学生运用所学的数学知识，分析和解决“农夫过河”问题，寻找最优解法。

4.通过小组讨论和展示，培养学生的团队合作和沟通能力。

三、教学方法本章节的教学方法主要包括以下几种：1.讲授法：教师通过讲解和演示，引导学生理解和掌握相关的数学知识和解决问题的方法。

2.讨论法：教师学生进行小组讨论，鼓励学生提出问题、分享思路和解决方案。

3.案例分析法：教师提供具体的案例，引导学生运用所学的数学知识进行分析和解决。

4.实验法：教师引导学生进行实验操作，通过实践来加深对数学知识的理解和应用。

四、教学资源本章节的教学资源主要包括以下几种：1.教材：教师准备相关的数学教材，提供理论知识的学习和练习题的练习。

2.参考书：教师提供相关的参考书籍，供学生进一步深入学习和探索。

3.多媒体资料：教师准备相关的多媒体资料，如图片、视频等，用于辅助讲解和演示。

4.实验设备：教师准备相关的实验设备，供学生进行实验操作和实践。

五、教学评估本章节的教学评估主要包括以下几种方式：1.平时表现：教师通过观察和记录学生在课堂上的参与程度、提问回答等情况，评估学生的学习态度和表现。

2.作业：教师通过布置和批改相关的作业，评估学生对知识的理解和应用能力。

3.考试：教师通过安排章节考试或者小测验，评估学生对知识掌握的程度和问题解决的能力。

农夫过河问题一、实验目的掌握广度优先搜索策略，并用队列求解农夫过河问题二、实验内容问题描述：一农夫带着一只狼，一只羊和一颗白菜，身处河的南岸，他要把这些东西全部运到北岸，遗憾的是他只有一只小船，小船只能容下他和一件物品。

这里只能是农夫来撑船，同时因为狼吃羊、羊吃白菜、所以农夫不能留下羊和狼或羊和白菜在河的一边，而自己离开；好在狼属肉食动物，不吃白菜。

农夫怎么才能把所有的东西安全运过河呢？实验要求如下：（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;}实验结果：四、实验总结。

数据结构农夫过河项目课报告数据结构-农夫过河项目课报告-计算机四班第七组项目名称:农夫过河算法与数据结构设计专业班级:计算机科学与技术四班学生姓名:王喆指导教师: 完成日期:2015年12月28日数据结构-农夫过河项目课报告-计算机四班第七组农夫过河算法与数据结构设计摘要农夫过河问题即一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。

而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农夫能撑船。

农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。

好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的东西安全地从河的南岸运到北岸,这类农夫问题是一个传统的数据结构问题,农夫过河问题根据图求解的搜索过程可采用两种不同的策略:一种是图的深度优先遍历搜索，另外一种是广度优先遍历搜索。

如果采用深度优先遍历搜索，则需要采用递归的方式来编写程序，而这种程序的系统的开销比较大，如果采用广度优先搜索，则可以借助队列的方式，这种方式开销较小。

关键字:农夫过河，广度优先遍历搜索，队列，深度优先遍历搜索，递归。

2数据结构-农夫过河项目课报告-计算机四班第七组目录1.前言…………………………………………………………42.设计任务与技术要求………………………………………43.总体设计方案………………………………………………44.数据结构和算法的设计……………………………………55.程序测试与调试(一)……………………………………7 6.程序测试与调试(二)..........................................9 7.程序出现的问题及修改情况....................................14 8.心得与体会.........................................................14 参考文献 (15)3数据结构-农夫过河项目课报告-计算机四班第七组1.前言课程研究项目是《数据结构》课程学习的重要方式之一，也是《数据结构》课程学习的重要组成部分之一。

一、实验目的1. 了解河流地貌的形成过程及其特征。

2. 学习野外观察和记录河流地貌的方法。

3. 掌握河流侵蚀、搬运、沉积作用的规律。

4. 分析河流对周边环境的影响。

二、实验时间与地点实验时间：2023年X月X日至X月X日实验地点：XX省XX市XX县XX河三、实验内容1. 河流地貌观察2. 河流侵蚀、搬运、沉积作用分析3. 河流对周边环境的影响调查四、实验方法1. 观察法：通过对河流地貌的实地观察，记录河流的形态、宽度、流速、侵蚀与沉积特征等。

2. 样本采集法：采集河床、河岸土壤、河中砾石等样本，分析其成分、粒径等特征。

3. 问卷调查法：对周边居民进行问卷调查，了解河流对周边环境的影响。

五、实验过程1. 河流地貌观察（1）河流形态：XX河呈东西走向，全长约XX公里，流域面积XX平方公里。

河流上游为峡谷，中游为宽谷，下游为平原。

（2）河流宽度：上游河宽约20米，中游河宽约50米，下游河宽约100米。

（3）流速：上游流速较快，约1.5米/秒；中游流速适中，约1.0米/秒；下游流速较慢，约0.5米/秒。

（4）侵蚀与沉积特征：上游河床多为砾石，侵蚀作用明显；中游河床为砂质沉积物，沉积作用明显；下游河床为粉质沉积物，沉积作用更加明显。

2. 河流侵蚀、搬运、沉积作用分析（1）侵蚀作用：上游河流流速快，侵蚀作用强烈，河床多为砾石，河岸侵蚀严重。

（2）搬运作用：中游河流流速适中，搬运作用明显，河床沉积物以砂质为主。

（3）沉积作用：下游河流流速慢，沉积作用明显，河床沉积物以粉质为主。

3. 河流对周边环境的影响调查（1）生态环境：河流上游生态环境较好，植被覆盖率高；中游生态环境一般，植被覆盖率降低；下游生态环境较差，植被覆盖率低。

（2）农业生产：河流上游地区以林业为主，中游地区以农业为主，下游地区以渔业为主。

（3）居民生活：河流上游居民以捕鱼、伐木为生；中游居民以种植、养殖为生；下游居民以渔业、旅游业为生。

六、实验结果与分析1. XX河上游侵蚀作用强烈，河床多为砾石，河岸侵蚀严重；中游搬运作用明显，河床沉积物以砂质为主；下游沉积作用明显，河床沉积物以粉质为主。

一、需求分析描述1、针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。

对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。

2、题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。

这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到。

3、题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。

4、输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。

二、系统架构设计1．设计中首先涉及的就是数据类型的定义，首先，定义一个结构体用来存放农夫、狼、羊、白菜的信息。

具体定义为：struct Condition{int farmer;int wolf;int sheep;int cabbage;};定义了一个结构体数组Condition conditions[100]，定义状态数组用来记录他们过河的状态0：起始岸；1：目的岸;程序中定义的char action100数组用来存放各个物件以及人过河或返回的说明语句。

2．程序中定义的子函数有：2.1 将狼带到目的岸以及带回起始岸的函数takeWolfOver（）和takeWolfBack （）；takeWolfOver（）函数中将conditions[i+1].wolf=1，白菜、羊的状态不变，同时要有action[i]=" take wolf over."将狼带到目的岸语句；takeWolfBack（）函数中将conditions[i+1].wolf=0，白菜、羊的状态不变，同时要有action[i]=" take wolf back."将狼带回起始岸语句。

数据结构实验报告——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

一、【问题描述】一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。

他要把这些东西全部运到北岸。

他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。

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

请求出农夫将所有的东西运过河的方案。

二、【数据结构设计】求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。

要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。

一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。

用0表示农夫或者某东西在河的南岸，1表示在河的北岸。

例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。

现在问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。

为避免瞎费功夫，要求在序列中不出现重复的状态。

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

本书只介绍在广度优先搜索方法中采用的数据结构设计。

广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。

要实现广度优先搜索，可以使用队列。

把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。

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

数据结构课程设计《农夫过河》学院：软件学院班级：12软工移动2班姓名：学号：12151156711 问题描述农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。

一条小船只能容下他和一件物品, 只有农夫能撑船，问农夫怎么能安全过河？狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品同时放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜。

这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。

2概要设计2.1 数据结构的设计农夫过河问题的模型化有一组状态( 如农夫和羊在南, 狼和白菜在北) ; 从一个状态可合法地转到另外几个状态( 如农夫自己过河或农夫带着羊过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态( 这里只有一个, 都在北) 。

问题表示: 需要表示问题中的状态, 农夫等位于南和北( 每个有两种可能) 。

可以采用位向量, 4 个二进制位的情况表示状态, 显而易见, 共24= 16种可能状态。

从高位到低位分别表示农夫、狼、白菜和羊。

0000( 整数0) 表示都在南岸, 目标状态1111( 即整数15) 表示都到了北岸。

有些状态0011,0101, 0111, 0001, 1100, 1001 是不允许出现的, 因为这些状态是不安全状态。

f( farmer) , w(wolf) , g(goat) , c( cabbage) 分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。

现在的问题转化为: 找一条合法路径( 相邻状态之间的转移合法) , 从开始状态到某个结束状态, 途中不经过不安全状态。

2.2算法的设计求农夫、狼、白菜和羊的当前状态的函数为每一种状态做测试, 状态安全则返回0, 否则返回1。

安全性判断函数, 若状态安全则返回0int farmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置{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; //其他状态是安全的借助于位向量和按位运算符, 很容易描述过河动作, 这种问题表示的设计使得程序的实现比较容易。

程序设计报告题目：农夫过河专业：计算机科学与技术小组成员：班级:指导教师：日期：2014年12月25日成员分工：农夫过河【摘要】农夫问题即一个农民带着一只狼、一只羊和一棵白菜，身处河的南岸,他需要把这些东西全部运到河的北岸。

而他只有一条小船，且这只小船小到只能容下他和一件物品,另外只有农民能撑船。

农夫不能留下狼和羊自己离开，也不能留下白菜和羊自己离开,更不能留下狼，羊和白菜而独自离开，因为没有农夫的照看,狼就要吃掉羊,而羊又要吃掉白菜。

好在狼是是肉动物，它不吃白菜，问农夫应该采取什么方案才能将所有的东西安全地从河的南岸运到北岸？这类农夫问题是一个传统的数据结构问题,利用基于队列的图的广度优先搜索求解农夫过河问题是一个易于理解、切实可行的方案,具有一定的推广价值。

关键字：农夫过河问题;队列;广度优先搜索一、实验内容概述(设计任务与技术要求)农民过河问题是指农民需要带一只狼、一只羊和一棵白菜到河的南岸去,需要安全运到北岸。

而一条小船只能容下他和一件物品,只有农民能撑船。

问农民怎么能安全过河,问题中需要涉及到狼会吃羊,羊会吃白菜,所以农民不能将这两种或三种物品单独放在河的一侧,因为没有农民的照看,狼就要吃掉羊,而羊可能又要吃掉白菜。

这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。

根据实际情况，对此问题分析可以得到不同的特征：1,是农民和羊在河的南岸，狼和白菜在河的北岸；2,是从一个状态可转到另外一个状态，而不违反狼吃羊，羊吃草的规则（例如农民自己过河或者农民带着羊过河）；3,是有些状态是不安全的（例如农民一人在北岸，而其他的东西都在南岸）；4,是初始状态是农民，羊，狼，白菜都在河的南岸和结束状态是农民，羊，狼，白菜都在河的北岸。

实现农夫过河问题，则需要找到一条合法的路径（相邻状态之间的转移合法），从开始状态到某个结束状态，路途中不能经过不安全的状态。

天津农学院<<Prolog语言>>教学实习报告题目：汉诺塔问题求解农夫过河问题求解学号0908054223姓名何训松系别计算机科学与信息工程系专业班级软件工程2班指导教师马国强成绩评定2012年8月目录一、实习目的及要求 (1)二、所用仪器、设备 (1)三、实验原理 (1)四、实验方法与步骤 (1)五、求解的问题与程序 (2)1．梵塔问题： (2)2．摆渡问题： (3)六、讨论与结论 (5)七、所附实验输出的结果或数据 (5)一、实习目的及要求熟悉并掌握prolog的编程环境、prolog语言的回溯、递归技术和表处理技术；具体输入课堂上讲过的member（X,List）、append(L1,L2,L)和findpairs等prolog程序运用prolog及其相关技术，编写并调试求解探宝、摆渡和梵塔问题的程序（三选二，摆渡问题必选）。

要求实验报告中包括：程序及其注释和说明、console 表单中的程序运行结果。

二、所用仪器、设备PC台式机和prolog编译软件三、实验原理prolog本身自带推理机，其回溯、递归技术和表处理技术可简化复杂问题求解。

prolog的跟踪、设断点对于调试程序是非常有用的。

四、实验方法与步骤说明用实例如何观察并理解回溯机制回溯机制所谓回溯,就是在程序运行期间,当某一个子目标不能满足(即谓词匹配失败)时,控制就返回到前一个已经满足的子目标(如果存在的话),并撤消其有关变量的约束值,然后再使其重新满足。

成功后,再继续满足原子目标。

如果失败的子目标前再无子目标,则控制就返回到该子目标的上一级目标(即该子目标谓词所在规则的头部)使它重新匹配。

回溯是PROLOG的一个重要机制。

例如：摆渡问题的move(...)，其对应有四个子目标。

当某个子目标不成立时，就会回溯到前一个子目标，撤销原约束值，然后重新合一。

如何用断点、跟踪以及显示调试prolog程序将鼠标移动至语句之前单击便打入了断点。

八皇后问题1.问题描述设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。

然后顺序在第1行，第2行……第8行上布放棋子。

在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。

2.基本要求编写求解并输出此问题的一个合法布局的程序。

3、实现提示：在第i行布放棋子时，从第1列到第8列逐列考察。

当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。

4 程序代码#include<iostream.h>#include<stdio.h>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 main(){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//否则输出{//输出棋盘状态int Line,Column;cout<<"第"<<++QueenNum<<"种状态为："<<endl;for(Line=0;Line<8;Line++){for(Column=0;Column<8;Column++)cout<<Queen[Line][Column]<<" ";cout<<endl;}cout<<endl;getchar();}/*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/Queen[i][Column]='*';a[Column]=0;b[i-Column+7]=0;c[i+Column]=0;}}}5 程序结果题目2 背包问题的求解1.问题描述假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…w n的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+w m=T，要求找出所有满足上述条件的解。