一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。编程解决猫狗鱼过河问题，这题怎么理解？不懂什么意思

第一次把猫带过来，第二次把鱼拉过来把猫带回去，然后第三次把狗带过来，然后什么都不带回去，第四次把猫带过来。

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

复制代码

   转载自 刘望望 同学的回帖

这是黑马入学考试的一道题,很有难度的!

杨庆雷 发表于 2014-6-29 00:38
转载自 刘望望 同学的回帖

哇塞，答案都发来了不会有什么问题吧，就是想问问这题考的什么知识点，谢谢了  辛苦额

面向大众 发表于 2014-6-29 00:30
第一次把猫带过来，第二次把鱼拉过来把猫带回去，然后第三次把狗带过来，然后什么都不带回去，第四次把猫带 ...

谢谢，了解了

……好厉害……学习了

学习一下！

哇，不错，好复杂，参考参考

这到题好像我在哪里见过哦！

学习学习 参考参考

杨庆雷 发表于 2014-6-29 00:38
转载自 刘望望 同学的回帖

第40行，不明白这句话是什么意思，left.size() > 1，能给解释一下吗？谢谢了。还有这句index == left.size() - 1怎么判断出来的不是刚带过来的动物。感谢

不错啊。看看