一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
        当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。

1. 
   
2. import java.util.*;
   
3. 
   
4. public class MaoGouYu
   
5. {
   
6.         List<String> left = new ArrayList<String>(); //表示河正岸
   
7.         List<String> right = new ArrayList<String>();  //表示河对岸
   
8.        
   
9.         public MaoGouYu() //初始化，老农、猫、狗、鱼都在河正岸准备渡河
   
10.         {
    
11.                 left.add("person");
    
12.                 left.add("fish");
    
13.                 left.add("dog");
    
14.                 left.add("cat");
    
15.         }
    
16.        
    
17.         //渡河方法，解决思路：猫不能和其他动物单独在一起
    
18.         //第一步：老农带着猫渡河
    
19.         //第二步：把猫放在对岸，老农自己回去接狗和鱼
    
20.         //第三步：老农带着狗或者鱼渡河，假设带狗
    
21.         //第四步：老农把猫带回去，把狗自己放在河对岸
    
22.         //第五步：老农把猫放在和正岸，带着鱼一起渡河
    
23.         //第六步：老农自己回去
    
24.         //第七步：老农带着猫渡河，这样他们就都过去了，也不会发生冲突
    
25.         public void cross()
    
26.         {
    
27.                 while(left.size() > 1)
    
28.                 {
    
29.                         left.remove("person");
    
30.                         Random random = new Random(); //老农随机带走一直动物
    
31.                         int index = random.nextInt(left.size());
    
32.                         if(index == left.size() - 1 && left.size() > 1) //为防止老农带走刚带回来的动物
    
33.                         {
    
34.                                 left.add("person");
    
35.                                 continue;
    
36.                         }
    
37.                         String s = left.get(index);
    
38.                         left.remove(s);
    
39.                         if(isSafe(left)) //如果老农带走该动物后，正岸没有冲突，则带走该动物
    
40.                         {
    
41.                                 right.add("person"); // 该动物和老农到达对岸
    
42.                                 right.add(s);
    
43.                                 System.out.println("老农带" + s + "到对岸");
    
44.                                
    
45.                                 if(right.size() == 4) //当老农和动物全部到达对岸，则渡河完成
    
46.                                 {
    
47.                                         break;
    
48.                                 }
    
49.                                
    
50.                                 right.remove("person"); //老农准备返回
    
51.                                 if(isSafe(right)) //如果老农自己返回，对岸不会发生冲突，则老农自己返回
    
52.                                 {
    
53.                                         left.add("person"); //老农返回正岸
    
54.                                         System.out.println("老农单独返回");
    
55.                                 }
    
56.                                 else //否则，老农带着一只动物一起返回
    
57.                                 {
    
58.                                         String s2 = right.get(random.nextInt(right.size()));
    
59.                                         while(s2.equals(s)) //如果老农要带走的动物是刚带来的那只，则换一只带走
    
60.                                         {
    
61.                                                 s2 = right.get(random.nextInt(right.size()));
    
62.                                         }
    
63.                                         right.remove(s2);
    
64.                                         left.add(s2); //老农和一只动物返回正岸
    
65.                                         left.add("person");
    
66.                                         System.out.println("老农带着" + s2 + "返回");
    
67.                                 }
    
68.                         }
    
69.                         else //如果老农带走一只动物后，正岸发生冲突，则放下该动物
    
70.                         {
    
71.                                 left.add(s);
    
72.                                 left.add("person");
    
73.                         }
    
74.                 }
    
75.                 System.out.println("老农和所有的宠物都成功渡河");
    
76.         }
    
77.        
    
78.         //判断某一边是否和谐
    
79.         public boolean isSafe(List<String> list)
    
80.         {
    
81.                 boolean b = true;
    
82.                
    
83.                 //如果某一边没有人，猫单独和其他动物在一起，则不和谐
    
84.                 if(list.size() > 1 && list.contains("cat") && !list.contains("person"))
    
85.                 {
    
86.                         b = false;
    
87.                 }
    
88.                
    
89.                 return b;
    
90.         }
    
91.        
    
92.         public static void main(String[] args)
    
93.         {
    
94.                 MaoGouYu mgy = new MaoGouYu();
    
95.                 mgy.cross();
    
96.         }
    
97. }
    

复制代码

牛啊  我完全不知道用代码该如何表示

其实我觉得楼上的方法不能说好，程序中出现随机取值的现象，感觉不是很完美，运气不好，一直无法得到正确解的，效率不高比较盲目；我给个思路：
假设刚开始渡河的那边  人、猫、鱼、狗各个状态是（用二进制表示）：0000，那么成功过河后他们的各个状态是：1111。所以过河问题就是从0000起始状态到1111最终状态的过程，因此总共有16中状态。然后把每一种状态看成图的一个结点，把可以连通的结点用有向边连起来，就构成的一个有向图。从0000这个结点遍历（深度优先搜索）图，遍历到1111结点则找到解。

大家好，我是新手，刚接触JAVA，正在自学基础，但遇到一些疑惑，求解疑？
请大家帮助，解释一下，path，classpath，%path%，的作用。

daoqin 发表于 2014-9-11 16:21
其实我觉得楼上的方法不能说好，程序中出现随机取值的现象，感觉不是很完美，运气不好，一直无法得到正确解 ...

自己试试如何？
且不说16种状态这个说法从何而来。就这个图从何而来你也解释不清楚吧。
每一步代表一种状态，不说别的，如果农夫闲的没事把一只猫从左边带到右边，从右边带到左边，一直循环，你打算怎样进行深度优先？什么时候决定要带动物，什么时候决定不带动物？

毛毛毛玉 发表于 2014-9-12 22:34
自己试试如何？
且不说16种状态这个说法从何而来。就这个图从何而来你也解释不清楚吧。
每一步代表一种状 ...

基础测试的农夫过河问题
http://bbs.itheima.com/thread-142574-1-1.html
大哥，你说那几个问题都不是问题，我用2个词语解释：图论+深度优先搜索（dfs）http://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA
http://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
这题不仅可以深度优先搜索，还可以用广度优先搜索（bfs)，结果都一样，只是它们的遍历层次不同，但是最后都可以找出最优解。

daoqin 发表于 2014-9-13 09:04
基础测试的农夫过河问题
http://bbs.itheima.com/thread-142574-1-1.html
大哥，你说那几个问题都不是问题 ...

抱歉抱歉，看到你声明那个矩阵的时候我就知道是我错了。我的理解出了问题。
把问题抽象化成类似于寻路问题的思路的确非常厉害。

毛毛毛玉 发表于 2014-9-13 09:44
抱歉抱歉，看到你声明那个矩阵的时候我就知道是我错了。我的理解出了问题。
把问题抽象化成类似于寻路问题 ...

嗯，之前大二学算法的时候遇到过这种问题，其实这个题的解法很多，用图的思想只是其中的一中。
网上有大牛给出了4中思路  
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中用栈的思想进行深度搜索这里采用队列的思想进行广度搜索。

兄弟，一起努力，加油！

农夫可以选择带动物也可以选择不带，还有就是两个状态之间可以互相转换，没有记录的话会有死循环一类的……
想靠遍历解决问题的话，就必须阻止某个状态的重现。
然后……如果做到了阻止某个状态的重现，随机化和遍历两种思路应该也差不了多少。

学习了。

自学快半年了，顿时感觉自己又变成菜鸟了:'(:'(

我来学习的！！

长知识了。、、、、、

正好做这道题呢，学习了

默默地顶一下

万合天宜 发表于 2014-9-16 14:22
自学快半年了，顿时感觉自己又变成菜鸟了

你现在进入黑马了吗

分别看成ABCD  A属于介质，BCD不能出现相邻，可以用map来设计，

学习了，谢谢楼主

卖艺人 发表于 2014-9-5 09:43

牛，，，这个思想方法好。比较自然。学习了