农夫过河问题
一、题目:农夫过河问题
二、目的与要求
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.完成系统总结报告以及使用说明书
五、进度安排
此次课程设计时间为一周，分以下几个阶段完成：
1.选题与搜集资料：每人选择一题，进行课程设计课题的资料搜集。
2.分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的
数据结构、并在此基础上进行实现程序功能的算法设计。
3.程序设计：运用掌握C/C++语言编写程序，实现各个模块功能。
4.调试与测试：调试程序，并记录测试情况。
5.完成课程设计报告。
6.验收与评分：指导教师对每个同学的开发的系统进行综合验收，并由学院考核小组
进行随机抽查评分。
六、撰写课程设计报告或课程设计总结
课程设计报告要求：
课程设计报告要求规范书写，应当包括如下7个部分：
1. 需求分析
2. 系统设计
3. 程序流程图
4. 类关系图
5. 实现代码
6. 总结
7. 参考书目
七、答辩与评分标准：
1 、作业文档：50 分；
2 、基本功能和要求：20 分；
2 、设计报告及使用说明书：10 分；
3 、设置错误或者按照要求改变结果：10 分；
4 、回答问题：10 分。
八、参考资料
《数据结构(C语言版)》
网上相关资料(....略)
农夫过河数据结构
郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：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)
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)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设 计； (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)
数据结构课程设计报告(农夫过河)
目录 引言 (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岸
农夫过河实验报告――数据结构
数据结构实验报告 ——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 一、【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。 二、【数据结构设计】 求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。 实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步
农夫过河实验报告
“数据结构与算法综合实验”课程设计报告题目：农夫过河问题 学院计算机科学技术 年级2014级 专业计算机科学与技术 学号20142060 姓名高晗 日期2016年3月30日星期三 成绩 评语 黑龙江大学 计算机科学技术学院、软件学院
《数据结构与算法综合实验》报告 1.系统概述 （1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。 （2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。 （3）掌握顺序表和队列的逻辑结构和存储结构。 2.系统需求分析 (1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。 (3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。 (4)实验运行环境为VC++6.0. 3.系统概要设计 (1)数据结构设计 要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初
任务书-农夫过河问题的逻辑建模与程序验证
上海工程技术大学 毕业设计（毕业论文）任务书 学院继续教育学院 专业计算机科学与技术 班级学号 学生王俊佶 指导教师张辉 题目农夫过河问题的逻辑建模与程序验证 任务规定 进行日期自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
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
农夫过河问题
农夫过河问题 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.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。 2.基本要求 编写求解并输出此问题的一个合法布局的程序。 3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。 4 程序代码 #include
{ 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//否则输出
农夫过河问题(c++编写)
1、问题描述 从前，一个农夫带着一只狼，一只羊和一棵白菜要河（注意该狼被农夫训服了，但还会吃羊）。他要将所有东西安全的带到河的对岸，不幸的是河边只有一条船，只能装下农夫和他的一样东西，并且农夫必须每次都随船过，因为只有他能撑船。在无人看管的情况下，狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。那么农夫如何才能使三样东西平安过河呢？ 2、需求分析 1）、农夫必须把狼，羊，白菜全部都载过河，且一次只能载一个； 2）、要求狼和羊不能单独在一起，羊和白菜也不能单独在一起，即要么羊单独在河的一边，要么羊和农夫在一起。 3、系统概述设计 对于上述情况，可以将河的两岸抽象成成数学问题，即将河的本岸抽象成数字‘0’，将对岸抽象成‘1’；且将狼，羊，白菜，农夫，分别抽象成数字‘0’，‘1’，‘2’，‘3’。而用数组a[i][j]（取值只能为0和1）表示第i次运载是，j （j=0,1,2,3。分别表示狼，羊，白菜，农夫）所在的位置。而用b[i]表示第i 次运载时船上运载的东西（因为农夫每次都必须在船上，所以不用记录，除非穿上只有农夫一人）。 如此一来，是否全部过河的问题就转化为判断a[i][0]，a[i][1]，a[i][2]，a[i][3]是否全为1了，即相加之和是否为4的问题了；而四者中的两者是否能在一起的问题就转化它们各自的a[i][j]是否相等的问题了。 4、系统详细设计 创建一个数组a[MAXTIMES][4]用于存放农夫，狼，羊，白菜的位置，用0表示本岸，1表示对岸； b[MAXTIMES]用于存放狼，羊，白菜，农夫的编号; 0: 狼，1:羊，2:白菜，3:农夫； 编写一个递归函数Ferry(int ferryTimes)，其中ferryTimes为渡河次数，在函数中，应考虑3个问题： 1）、用a[ferryTimes][0] + a[ferryTimes][1] + a[ferryTimes][2] + a[ferryTimes][3] == 4语句判断是否全部到达对岸，如果是，则直接输出结果，否则，考虑第二个问题； 2）、狼和羊是否单独在一起，羊和白菜是否单独在一起，用语句a[ferryTimes][1] != a[ferryTimes][3] && (a[ferryTimes][2] == a[ferryTimes][1] || a[ferryTimes][0] == a[ferryTimes][1])来实现； 3）、如果上两个条件都不满，则可执行运输的动作，但每次都应考虑，该运输情况以前是否执行过（即两岸以及船上的东西以及各自位置和以前完全相同），
农夫过河问题
农夫过河问题 1．问题描述 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。 要求：利用图的存储结构和图的搜索算法，求出农夫将所有的东西运过河的方案。 2．需求分析 2.1规定程序功能 本题要解决的问题就是农夫如何带着狼、羊、白菜安全过河。要求是船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。 2.2输入和输出形式 本程序自动完成所有情况的输入，不需要人为的输入。然后根据程序里面调用相应函数模块可得到一种过河方案，然后自行输出。输出的是农夫过河每一步的方案，即每一步中农夫采取的行动。 3．概要设计 3.1数据结构的设计 题目要求用图的存储结构，所以要想办法将农夫、狼、羊、白菜每一步的状态用结点表示，他们状态的改变到下一个结点可行，则在两条结点中加一条边。但是每个结点包含四个量，如果他们每个都各自用一个结构体表示，则图形就变得相当的繁琐，因此想到一个简单的结局办法。河的两岸是两个不同的变量，刚好可以用0和1表示，那么四个状态量都用0和1则可表示他们每一步所处的位置，也就能明白农夫每次是怎么过河的。 3.2算法的设计 本程序可以分成四个模块，分别是：找到所有情况的点、从中挑选出满足题意的点、创建满足题意的点之间的边、通过图的深度优先遍历找到过河方案。 各模块之间的关系图如下：
数据结构 农夫过河问题
#include
校园导航系统 农夫过河问题 图的遍历演示 数据结构课程设计(实验报告)
广东技术师范学院天河学院 数据结构与算法 课程设计报告 题目:校园导航系统 农夫过河问题 图的遍历演示 学号: 23 27____28 32 ___ __ 班级: 移动121____ ____ _ __ 小组成员:_李俊、刘锦浩、刘钦锐、潘文伟_ 指导教师: 蔡柳萍 所属系部: 计算机科学与技术系
目录 题目一：农夫过河 (3) 一、问题描述 (3) 二、基本要求 (2) 三、算法思想 (2) 四、数据结构 (2) 五、模块划分 (3) 六、源程序 (6) 七、测试数据 (7) 1）运行测试........................................................ 错误！未定义书签。题目二：校园导航. (7) 一、问题描述 (8) 二、基本要求 (8) 三、算法思想 (8) 四、模块划分 (8) 五、源程序 (10) 六、运行及测试情况 (17) 题目二：图的遍历演示 (6) 一、问题描述 (6) 二、基本要求 (6) 三、算法思想 (6) 四、模块划分 (6) 五、源程序 (9) 六、运行及测试情况 (27) 1、主界面 (27) 2、输入信息运行测试（部分数据） (29) 3、运行测试 (30) 课程设计总结 (33)
题目一：农夫过河 一、问题描述 有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？二、基本要求 1）编程实现农夫过河的过程； 2）执行结果中要体现过河的先后顺序 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构 三、算法思想 求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。现在问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。 四、数据结构 实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。由于队列的操作遵循先进