/*
* 题目描述:有一个农夫,带着一只狼、一只羊、一颗白菜过河。其中农夫不在的时候狼会吃羊,
* 羊会吃白菜。只有一只船,且每次农夫最多只能带一样物品过河。求解决方案。
*
* 思路:1. 过程回溯法。把人、狼、羊、白菜看成A、B、C、D。过河的时候从ABCD中选两个过河,在
* 选一个回来。若发生狼跟羊、羊跟白菜在同一个岸边,且农夫不在场,则回溯.
*
* 2. 图的遍历。设从南岸到北岸,在南岸ABCD的各个状态是(用二进制表示):0000,在
* 北岸的时候各个状态是:1111。所以过河问题就是从0000起始状态到1111最终状态的
* 过程。易得,总共有16中状态。然后把每一种状态看成图的一个结点,把可以连通的
* 结点用有向边连起来,就构成的一个有向图。从0000这个结点遍历(深度优先或者广
* 度优先)图,遍历到1111结点则找到解。
*
* 3. 状态回溯法。设从南岸到北岸,在南岸ABCD的各个状态是(用二进制表示):0000,在
* 北岸的时候各个状态是:1111。所以过河问题就是从0000起始状态到1111最终状态的
* 过程。易得,总共有16中状态。从第一种状态0000开始搜索,搜索当前状态下可以到达的
* 状态,搜索到一个则把这个状态看成当前状态,继续搜索。若出现当前状态搜索无可到达
* 的状态或已遍历所有搜索出来的状态,则回溯。直到到达1111状态。
*
* 4. 状态队列搜索法。跟思路3类似,只是搜索的方式不一样。思路3中用栈的思想进行深度搜索
* 这里采用队列的思想进行广度搜索。
*/
分享到:
相关推荐
一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。他前面只有一条小船,船只能容下他和一件物品,另外只有农夫才能撑船。...请求出农夫将所有的东西运过河的方案。
农夫过河的完整代码(农夫、羊、狼和蔬菜安全过河)
1.问题描述 一个农夫带着一只狼、一只羊和一棵白菜,身处河的南岸。他要把这些东西 全部运到北岸。他面前只有一条小船,船只能容下他和一件物品,另外只有农夫 才能撑船。...请求出农夫将所有的东西运过河的方案。
采用深度优先遍历图的方法,解决农夫过河的问题,有代码,有可执行文件和流程图
农夫过河问题的算法与实现.doc
农夫过河问题的一种解法.一个在校大学生的课程设计。请斧正!
用c语言解决农夫过河问题的原代码,完整版
找了好久,终于找到了一个C语言版的农夫过河问题的解法,认真看就看的懂,写的不错!简介明了!
采用深度优先遍历图的方法,解决农夫过河的问题,有代码,有可执行文件和流程图
经典的农夫过河问题。 用1代表狼,2代表羊,3代表白菜。则在河的某一岸边,物体的分布有8种情况: 当两物体在一起并且它们的代码之和为3或5时,将导致相克的情况出现。 设计c语言算法实现过河,并将结果打印
c语言农夫过河思维游戏程序及源代码,简单易懂,并有详细注释!
要模拟农夫过河问题,首先...出发,寻找一种全部由安全状态构成的状态序列,它以二进制1111(全部到达河的北岸) 为最终目标,并且在序列中的每一个状态都可以从前一状态通过农夫(可以带一样东西)划船过河的动作到达。
有一农夫带着一条狼,一只羊,一筐菜想过河,农夫每次只能带一件东西,如果没有农夫看管,狼会吃羊,羊吃草,如何设计使得每个东西都能安全过河
因为狼、羊和菜不会划船,所以状态转换算法也很简单,不需要象“用三个水桶均分8升水”问题那样要用排列组合的方式确定转换方法(倒水动作),本题一共只有8种固定的状态转换运算(过河动作),分别是: 农夫单独...
农夫过河问题——C语言程序设计(转) 实验报告
主要介绍了基于C++的农夫过河问题算法设计与实现方法,简单描述了农夫过河问题,并结合实例形式详细分析了基于C++实现农夫过河问题的相关算法实现步骤与操作技巧,需要的朋友可以参考下
设一个农夫过河带着一条狼、一只羊和一棵白菜,身处河的南岸。现在他要把这些西全部运到北岸,现在问题是他面前只有一条小船,船小到只能容下他和一件物品,另外只有农夫能撑船。当农夫在场的时候,这三样东西相安无事...
怎样用c语言解决 数据结构农夫过河问题
一个农夫带着一只狼,一只羊和一棵白菜,身处河的南岸。他要把这些东西全部运到北岸。...请求出农夫将所有东西运过河的方案。 实现上述求解的搜索过程可以用两中不同的方案:一种是广度优先搜索,另一种是深度优先搜索
包含prolog求解农夫过河问题的实验报告、源代码及试验运行截图