6.解：用四元组(f、w、s、g)表示状态， f 代表农夫，w 代表狼，s
代表羊，g 代表菜，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。
初始状态S0：(0,0,0,0) 目标状态：(1,1,1,1)
不合法的状态:(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1)
操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4}
方案有两种：p2→q0 →p3→q2 →p2 →q0 →p2
p2→q0 →p1→q2 →p3→q0→p2
郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：2012/6/21 指导教师签名： 课程负责人签名： 年月日
郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目：农夫过河 学生姓名： 系别：计算机与通信工程学院 专业：计算机科学与技术 班级：计算机科学与技术 学号： 指导教师： 2012年6 月21 日
一，设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二，运行环境（软、硬件环境） VC6.0 Windows7系统 三，算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四，算法的流程图 要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图：
人工智能学科诞生于20世纪50年代中期，当时由于计算机的产生与发展，人们开始了具有真正意义的人工智能的研究。（虽然计算机为AI提供了必要的技术基础,但直到50年代早期人们才注意到人类智能与机器之间的联系. Norbert Wiener是最早研究反馈理论的美国人之一.最熟悉的反馈控制的例子是自动调温器.它将收集到的房间温度与希望的温度比较,并做出反应将加热器开大或关小,从而控制环境温度.这项对反馈回路的研究重要性在于: Wiener从理论上指出,所有的智能活动都是反馈机制的结果.而反馈机制是有可能用机器 模拟的.这项发现对早期AI的发展影响很大。） 1956年夏，美国达特莫斯大学助教麦卡锡、哈佛大学明斯基、贝尔实验室申龙、IBM公司信息研究中心罗彻斯特、卡内基——梅隆大学纽厄尔和赫伯特.西蒙、麻省理工学院塞夫里奇和索罗门夫，以及IBM公司塞缪尔和莫尔在美国达特莫斯大学举行了以此为其两个月的学术讨论会，从不同学科的角度探讨人类各种学习和其他职能特征的基础，并研究如何在远离上进行精确的描述，探讨用机器模拟人类智能等问题，并首次提出了人工智能的术语。从此，人工智能这门新兴的学科诞生了。这些青年的研究专业包括数学、心理学、神经生理学、信息论和电脑科学，分别从不同角度共同探讨人工智能的可能性。他们的名字人们并不陌生，例如申龙是《信息论》的创始人，塞缪尔编写了第一个电脑跳棋程序，麦卡锡、明斯基、纽厄尔和西蒙都是“图灵奖”的获奖者。 这次会议之后，在美国很快形成了3个从事人工智能研究的中心，即以西蒙和纽威尔为首的卡内基—梅隆大学研究组，以麦卡锡、明斯基为首的麻省理工学院研究组，以塞缪尔为首的IBM公司研究组。随后，这几个研究组相继在思维模型、数理逻辑和启发式程序方面取得了一批显著的成果： （1）1956年，纽威尔和西蒙研制了一个“逻辑理论家“（简称LT）程序，它将每个问题都表示成一个树形模型,然后选择最可能得到正确结论的那一枝来求解问题，证明了怀特黑德与罗素的数学名著《数学原理》的第2章中52个定理中的38个定理。1963年对程序进行了修改，证明了全部定理。这一工作受到了人们的高度评价，被认为是计算机模拟人的高级思维活动的一个重大成果，是人工智能的真正开端。 （2）1956年，塞缪尔利用对策论和启发式搜索技术编制出西洋跳棋程序Checkers。该程序具有自学习和自适应能力，能在下棋过程中不断积累所获得的经验，并能根据对方的走步，从许多可能的步数中选出一个较好的走法。这是模拟人类学习过程第一次卓有成效的探索。这台机器不仅在1959年击败了塞缪尔本人，而且在1962年击败了美国一个州的跳棋冠军，在世界上引起了大轰动。这是人工智能的一个重大突破。 （3）1958年，麦卡锡研制出表处理程序设计语言LISP，它不仅可以处理数据，而且可以方便的处理各种符号，成为了人工智能程序语言的重要里程碑。目前，LISP语言仍然是研究人工智能何开发智能系统的重要工具。 （4）1960年纽威尔、肖和西蒙等人通过心理学实验，发现人在解题时的思维过程大致可以分为3个阶段：1。首先想出大致的解题计划；2。根据记忆中的公理、定理和解题规划、按计划实施解题过程；3.在实施解题过程中，不断进行方法和目标分析，修改计划。这是一个具有普遍意义的思维活动过程，其中主要是方法和目的的分析。（也就是人们在求解数学问题通常使用试凑的办法进行的试凑是不一定列出所有的可能性，而是用逻辑推理来迅速缩小搜索范围的办法进行的），基于这一发现，他们研制了“通用问题求解程序GPS”，用它来解决不定积分、三角函数、代数方程等11种不同类型的问题，并首次提出启发式搜索概念，从而使启发式程序具有较普遍的意义。
农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？ 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(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;
课程设计第五题 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) {
人工智能发展史 人工智能学科诞生于20世纪50年代中期，当时由于计算机的产生与发展，人们开始了具有真正意义的人工智能的研究。（虽然计算机为AI提供了必要的技术基础,但直到50年代早期人们才注意到人类智能与机器之间的联系. Norbert Wiener是最早研究反馈理论的美国人之一.最熟悉的反馈控制的例子是自动调温器.它将收集到的房间温度与希望的温度比较,并做出反应将加热器开大或关小,从而控制环境温度.这项对反馈回路的研究重要性在于: Wiener从理论上指出,所有的智能活动都是反馈机制的结果.而反馈机制是有可能用机器模拟的.这项发现对早期AI的发展影响很大。） 1956年夏，美国达特莫斯大学助教麦卡锡、哈佛大学明斯基、贝尔实验室申龙、IBM公司信息研究中心罗彻斯特、卡内基——梅隆大学纽厄尔和赫伯特.西蒙、麻省理工学院塞夫里奇和索罗门夫，以及IBM公司塞缪尔和莫尔在美国达特莫斯大学举行了以此为其两个月的学术讨论会，从不同学科的角度探讨人类各种学习和其他职能特征的基础，并研究如何在远离上进行精确的描述，探讨用机器模拟人类智能等问题，并首次提出了人工智能的术语。从此，人工智能这门新兴的学科诞生了。这些青年的研究专业包括数学、心理学、神经生理学、信息论和电脑科学，分别从不同角度共同探讨人工智能的可能性。他们的名字人们并不陌生，例如申龙是《信息论》的创始人，塞缪尔编写了第一个电脑跳棋程序，麦卡锡、明斯基、纽厄尔和西蒙都是“图灵奖”的获奖者。 这次会议之后，在美国很快形成了3个从事人工智能研究的中心，即以西蒙和纽威尔为首的卡内基—梅隆大学研究组，以麦卡锡、明斯基为首的麻省理工学院研究组，以塞缪尔为首的IBM公司研究组。随后，这几个研究组相继在思维模型、数理逻辑和启发式程序方面取得了一批显著的成果： （1）1956年，纽威尔和西蒙研制了一个“逻辑理论家“（简称LT）程序，它将每个问题都表示成一个树形模型,然后选择最可能得到正确结论的那一枝来求解问题，证明了怀特黑德与罗素的数学名著《数学原理》的第2章中52个定理中的38个定理。1963年对程序进行了修改，证明了全部定理。这一工作受到了人们的高度评价，被认为是计算机模拟人的高级思维活动的一个重大成果，是人工智能的真正开端。 （2）1956年，塞缪尔利用对策论和启发式搜索技术编制出西洋跳棋程序Checkers。该程序具有自学习和自适应能力，能在下棋过程中不断积累所获得的经验，并能根据对方的走步，从许多可能的步数中选出一个较好的走法。这是模拟人类学习过程第一次卓有成效的探索。这台机器不仅在1959年击败了塞缪尔本人，而且在1962年击败了美国一个州的跳棋冠军，在世界上引起了大轰动。这是人工智能的一个重大突破。 （3）1958年，麦卡锡研制出表处理程序设计语言LISP，它不仅可以处理数据，而且可以方便的处理各种符号，成为了人工智能程序语言的重要里程碑。目前，LISP语言仍然是研究人工智能何开发智能系统的重要工具。 （4）1960年纽威尔、肖和西蒙等人通过心理学实验，发现人在解题时的思维过程大致可以分为3个阶段：1。首先想出大致的解题计划；2。根据记忆中的公理、定理和解题规划、按计划实施解题过程；3.在实施解题过程中，不断进行方法和目标分析，修改计划。这是一个具有普遍意义的思维活动过程，其中主要是方法和目的的分析。（也就是人们在求解数学问题通常使用试凑的办法进行的试凑是不一定列出所有的可能性，而是用逻辑推理来迅速缩小搜索范围的办法进行的），基于这一发现，他们研制了“通用问题求解程序GPS”，用
人工智能的发展及应用 学院： 班级： 姓名： 学号： 人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能几乎涉及到是自然科学和社会科学的所有学科，其范围
已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。 人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。关于什么是“智能”，就问题多多了。这涉及到其它诸如意识、自我、思维等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。关于人工智能一个大家比较容易接受的定义是这样的：人工智能是人造的智能,是计算机科学、逻辑学、认知科学交叉形成的一门科学，简称AI。 人工智能体现在思维、感知、行为三个层次。它主要模拟眼神、扩展人的智能。其研究内容可以分为机器思维和思维机器、机器行为和行为机器、机器感知和感知机器、三个层次。人工智能研究与应用虽然取得了不少成果，但离全面推广应用还有很大距离，还有很多问题需要许多学科的共同研究。 人工智能有两种实现方式，第一种叫做工程学方法（Engineering approach），是采用传统的编程技术，使系统呈现智能的效果，而不考虑所用方法是否与人或动物机体所用的方法相同。它已在一些领域内作出了成果，如文字识别、电脑下棋等。第二种是模拟法（Modeling approach），它不仅要看效果，还要求实现方法也和人类或生物机体所用的方法相同或相类似。第一种方法，需要人工详细规定程序逻辑，如果游戏简单，还是方便的。如果游戏复杂，角色数量和活动空间增加，相应的逻辑就会很复杂（按指数式增长），人工编程就非常繁琐，容易出错。而一旦出错，就必须修改原程序，重新编译、调试，最后为用户提供一个新的版本或提供一个新补丁,非常麻烦。采用第二种方法时，编程者要为每一角色设计一个智能系统（一个模块）来进行控制，这个智能系统（模块）开始什么也不懂，就像初生婴儿那样，但它能够学习，能渐渐地适应环境，应付各种复杂情况。 人工智能的发展: 人工智能的研究经历了以下几个阶段: 孕育阶段:古希腊的Aristotle（亚里士多德）（前384-322），给出了形式逻辑的基本规律。英国的哲学家、自然科学家Bacon（培根）（1561-1626），系统地给出了归纳法。“知识就是力量”德国数学家、哲学家Leibnitz（布莱尼兹）（1646-1716）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家Boole（布尔）（1815-1864）实现了布莱尼茨的思维符号化和数学化的思想,提出了一种崭新的代数系统——布尔代数。 第一阶段:50年代人工智能的兴起和冷落人工智能概念首次提出后，相继出现了一批显著的成果，如机器定理证明、跳棋程序、通用问题s求解程序LISP表处理语言等。但由于消解法推理能力的有限，以及机器翻译等的失败，使人工智能走入了低谷。这一阶段的特点是：重视问题求解的方法，忽视知识重要性。 第二阶段:60年代末到70年代，专家系统出现，使人工智能研究出现新高潮DENDRAL 化学质谱分析系统、MYCIN疾病诊断和治疗系统、PROSPECTIOR探矿系统、Hearsay-II语
课程设计题目：农夫过河 一．问题描述 一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则： (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)
农夫过河 教学目标 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
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]);