【精品】农夫过河问题状图及程序

【精品】农夫过河问题状图及程序【精品】农夫过河问题状图及程序农夫过河问题状态图及程序一、问题需求分析一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢,二、算法选择求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求...

【精品】农夫过河问题状图及程序农夫过河问题状态图及程序一、问题需求分析一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢,二、算法选择求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先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// 用队列解决农夫过河问题includeincludetypedef int DataType//顺序队列:类型和界面函数声明struct SeqQueue // 顺序队列类型定义 int MAXNUM // 队列中最大元素个数 int f r DataType qtypedef struct SeqQueue PSeqQueue // 顺序队列类型的指针类型PSeqQueue createEmptyQueue_seqint m //创建一个空队列 PSeqQueue queue PSeqQueuemallocsizeofstructSeqQueue if queue NULL queue-q DataTypemallocsizeofDataType m if queue-q queue-MAXNUM m queue-f 0 queue-r 0 return queue else freequeue printfOut of spacen // 存储分配失败 return NULLint isEmptyQueue_seqPSeqQueue queue //判断队列是否为空 return queue-f queue-rvoid enQueue_seqPSeqQueue queue DataType x// 在队尾插入元素 x if queue-r 1 queue-MAXNUM queue-f printfFull queue.n else queue-qqueue-r x queue-r queue-r 1 queue-MAXNUM void deQueue_seqPSeqQueue queue// 删除队列头部元素 if queue-f queue-r printfEmpty Queue.n else queue-f queue-f 1 queue-MAXNUMDataType frontQueue_seqPSeqQueue queue if queue-f queue-r printfEmpty Queue.n else return queue-qqueue-f//个体状态判断函数int farmerint location //判断农夫的位置 return 0 location 0x08int wolfint location //判断狼的位置 return 0 location 0x04int cabbageint location //判断白菜的位置 return 0 location 0x02int goatint location //判断羊的位置 return 0 location 0x01//安全状态的判断函数int safeint location // 若状态安全则返回 true if goatlocation cabbagelocation goatlocation farmer location return 0 // 羊吃白菜 if goatlocation wolflocation goatlocation farmer location return 0 // 狼吃羊 return 1 // 其他状态是安全的main int i movers location newlocation int route16 //用于记录已考虑的状态路径 PSeqQueue moveTo //用于记录可以安全到达的中间状态 moveTo createEmptyQueue_seq20 //创建空队列 enQueue_seqmoveTo 0x00 //初始状态进队列 for i 0 i 16 i routei - 1 准备数组 route 初值 route0 0 while isEmptyQueue_seqmoveTo route15 - 1 // location frontQueue_seqmoveTo //取队头状态为当前状态 deQueue_seqmoveTo for movers 1 movers

                    本文档为【【精品】农夫过河问题状图及程序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

【精品】农夫过河问题状图及程序

你可能还喜欢