下载文档原格式
算法谜题1，狼⽺菜过河问题描述农夫需要把狼、⽺、菜和⾃⼰运到河对岸去，只有农夫能够划船，⽽且船⽐较⼩，除农夫之外每次只能运⼀种东西，还有⼀个棘⼿问题，就是如果没有农夫看着，⽺会偷吃菜，狼会吃⽺。
请考虑⼀种⽅法，让农夫能够安全地安排这些东西和他⾃⼰过河。
分析问题很简单，但如何⽤计算机求解呢。
农夫渡河从本质上是⼀种状态的改变。
有农夫、狼、⽺、菜四个个体，任何时刻每个个体的状态只有⼀种，每个个体有两种状态（没有过河、已经过河）。
依次⽤4位分别代表农夫、狼、⽺、菜，0表⽰未过河，1表⽰已过河。
则起始状态为0000，⽬标状态为1111。
共有8种过河动作（状态转换运算）农夫单独过河农夫带狼过河农夫带⽺过河农夫带菜过河农夫单独返回农夫带狼返回农夫带⽺返回农夫带菜返回优先级：农夫过河时，优先带货物；回返时优先不带货物。
有限种状态：可能有16（2^4）种状态，但因为狼吃⽺，⽺吃菜的限制，部分状态是⽆法成⽴的。
实现状态空间树（回溯法）是以0000为根的⼀颗状态树，当某个叶⼦节点是状态1111，则表⽰从根到这个叶⼦节点之间的状态序列是本问题的⼀个解，需要避免出现重复状态导致死循环。
⽅法1：每个状态有8种可选动作，转换为8个新状态，但在特定状态下某些动作是⽆效的。
定义8种状态转换运算，对当前节点遍历执⾏这8种运算，找到所有⼦节点⽅法2：依据当前状态，判别它所有可选的动作（最多4种）。
class Program{static void Main(string[] args){var original = new State();var path = new List<State>();path.Add(original);int count = 0;Search(path, ref count);Console.ReadKey();}private static void Search(List<State> path, ref int count){var cur = path[path.Count - 1];if (cur.Man && cur.Wolf && cur.Vegetable && cur.Sheep){count++;Console.WriteLine($"解{count}:");path.ForEach((a) => { Console.WriteLine(a.Action); });return;}if (cur.Man){Switch(path, ref count, cur, "返回");}else{Switch(path, ref count, cur, "过河");}}private static void Switch(List<State> path, ref int count, State cur, string action){var newState = cur.Copy();newState.Man = !newState.Man;newState.Action = "独⾃" + action;Action(path, ref count, newState);if (cur.Sheep == cur.Man){newState.Sheep = !newState.Sheep;newState.Action = "带着⽺" + action;Action(path, ref count, newState);newState.Sheep = !newState.Sheep;}if (cur.Wolf == cur.Man){newState.Wolf = !newState.Wolf;newState.Action = "带着狼" + action;Action(path, ref count, newState);newState.Wolf = !newState.Wolf;}if (cur.Vegetable == cur.Man){newState.Vegetable = !newState.Vegetable;newState.Action = "带着菜" + action;Action(path, ref count, newState);newState.Vegetable = !newState.Vegetable;}}private static void Action(List<State> path, ref int count, State newState) {if (newState.IsOk){foreach (var item in path){if (item.Equals(newState)){return;}}path.Add(newState);Search(path, ref count);path.RemoveAt(path.Count - 1);}}//false 表⽰未过河， true表⽰已过河private class State{public bool Man { get; set; }public bool Wolf { get; set; }public bool Sheep { get; set; }public bool Vegetable { get; set; }public string Action { get; set; }public bool IsOk{get{if (Wolf == Sheep && Wolf != Man){return false;}if (Sheep == Vegetable && Sheep != Man){return false;}return true;}}public State Copy(){return new State{Man = this.Man,Wolf = this.Wolf,Sheep = this.Sheep,Vegetable = this.Vegetable};}public bool Equals(State newState){return (this.Man == newState.Man&& this.Wolf == newState.Wolf&& this.Sheep == newState.Sheep&& this.Vegetable == newState.Vegetable);}}}状态空间图所有状态作为图的节点遍历图，找出所有从0000到1111的路径连接状态的条件农夫的状态要不⼀样（只有农夫可以划船，每次过河，不能缺农夫）最多只有⼀个其他个体的状态不⼀样（⼀次只能带⼀个过河），且这个个体的状态要与农夫⼀致。
龙源期刊网
巧妙过河
作者：陆淼欣
来源：《小天使·二年级语数英综合》2012年第03期
今天，小姨（yí）到我家来玩，还给我出了一道题：农夫要把狼、羊和青菜运过河，每次最多运1个，怎么运？
我想，要是把狼先运过去，留下的羊要吃青菜，不行。
只能先把羊运过去，留下狼和菜。
接下来再运什么呢？如果运菜的话，羊就会吃菜的，可是要运狼的话，狼就会吃羊的，这可怎么办呢？
我有点着急了。
妈妈提醒我：“回来时船是空的，可以带一样东西哦。
”
原来还可以这样啊！我沉思片刻（ｋè），高兴地对小姨说：“我想出来了。
”
小姨让我快回答。
我理直气壮（ｚｈｕàｎɡ）地说：“先把羊运过去，再运狼，狼到了对面再把羊带回来，这样狼就吃不着羊了,然后再把菜运到对岸去，狼又不吃菜，最后再把羊运
过去。
”小姨夸我聪明，说我很会思考问题，我听了心里美滋滋的。
（指导老师沈曙）。
人狼羊菜安全渡河问题1500字人狼羊菜安全渡河问题是一个著名的逻辑推理问题，常常用来考察人们在面对复杂情况时的思考能力和解决问题的能力。
问题描述如下：有一天，一个人带着一只狼、一只羊和一颗白菜来到了一条河边，他想把它们都安全地带到对岸去。
但是，他只有一条小船，而且这条小船只能承载他和另外一个物品（人、狼、羊、菜）。
问题是，如果他将狼与羊或羊与菜一起留在岸上，那么狼会吃掉羊，羊会吃掉菜。
请问，这个人应该如何才能够将所有物品都安全地带到对岸去？这个问题可以通过逐步分析来解决。
首先，我们可以将问题简化为只有三个物品的情况，即人、狼和羊。
这样，我们可以列出所有可能的情况如下：1. 人和狼一起过河，然后人回来，再把狼带过去。
这种情况下，狼会吃掉羊。
2. 人和羊一起过河，然后人回来，再把狼带过去。
这种情况下，羊会吃掉菜。
3. 人和羊一起过河，然后人回来，再把羊带过去。
这种情况下，狼会吃掉羊。
通过分析可以发现，前两种情况都是不可行的，因为狼或羊会被吃掉。
所以，我们只能选择第三种情况。
具体而言，我们可以按照以下步骤来解决问题：1. 人带着羊过河，然后人回来。
2. 人带着狼过河，然后把狼放在对岸，但是人自己回来。
3. 人带着菜过河，然后人放菜在对岸，再一起回去。
4. 人带着羊过河，完成。
通过这个方法，我们可以确保所有物品都能够安全地过河。
而且，我们也可以通过类似的方法解决更复杂的问题，比如加入更多的物品。
总结起来，人狼羊菜安全渡河问题是一个充满挑战和乐趣的逻辑推理问题。
通过逐步分析和合理安排，我们可以找到解决问题的方法，并将所有物品都安全地带到对岸。
这种问题可以提高人们的思维能力和解决问题的能力，同时也展示了逻辑推理的重要性。
精心整理
各种形式的过河问题
1.最古老的过河问题
一个农民携带一只狼，一只羊和一棵白菜，要借助一条小船过河。
小船上除了农民只能再带狼、羊、白菜中的一样。
而农民不在时，狼会吃羊，羊会吃白菜。
农民如何过河呢？
2.三个道士与三个和尚
三个老道士与三个和尚分别在一条河的两岸，都要到河的对岸去。
河中只有
6.如何尽快过河
在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。
如果不借助手电筒的话，大家是无论如何也不敢过桥去的。
不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。
如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。
问题是，如何设计一个方案，让这四人尽快过桥。
