大家好，我是来自海淀区的新人，刚刚通过云九班报名的基础测试，希望还能赶上与大家做同学的机会
我做基础测试耽误时间最久的就是最后一题
题目如下：
一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。
PS：这个是道经典的逻辑题，所以大家可能很早就有接触了
我个人感觉这题的编码难点跟逻辑推断难点是一致的：怎么去想到带猫从对岸回来/怎么让程序自己做出这个选择
我自己花了5个写了个很繁琐的算法，也在网上看了一些答案，但是目前找到解答难点的
基本上不约而同的讲把猫带回或者把动物带回当作是一种已经存在方案然后备选，而不是让程序自己递推出来
我自己也没做到，但是我还是感觉一段程序，自己加入的逻辑思路的痕迹越少越好
附件是我的代码，希望大家能给予我指点

楼主最后虽然得到了正确的结果，但是最后输出结果不够清晰，而且程序执行的每一步都是跟着你的思想在进行，没有一点程序自己的选择，这是我写的，可以交流一下

谢谢你，比我写得简练多了，其实我还是尽量让系统自己判断的，只不过用了循环，恨不得每一步都进行了循环并在内部进行判断，现在看来还是挺繁琐的，我为了让他们正常的按组内的索引编号循环下去，每次不得不复位直到找到正确答案才真正进行remove和add操作，你的比我的优化了很多，多谢指教了

呃。。怎么结帖。。没找到哪儿能改成已解决

都是大神呀，我就写了几行代码哈。。。

想了半天，没搞清思路。还是参考下大神的答案吧

刘望望童鞋确实思路清晰，领教了

经典的题目...

学习学习！

思路清晰就好

这也是我的基础测试题最后一题，没有思路，正在膜拜大神的杰作

谢谢，楼主分享...

我也在想这问题 这题目看着简单 想想要做好 还是有一点难度的

刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果，但是最后输出结果不够清晰，而且程序执行的每一步都是跟着你的思想在进行， ...

厉害！！！

真心不错

刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果，但是最后输出结果不够清晰，而且程序执行的每一步都是跟着你的思想在进行， ...

public boolean isSafe(List<String> list)
        {
                boolean b = true;
               
                //如果某一边没有人，猫单独和其他动物在一起，则不和谐
                if(list.size() > 1 && list.contains("cat") && !list.contains("person"))
                {
                        b = false;
                }
               
                return b;
        }
这个函数为什么要boolean b = true;  直接return true，不可以吗？  有什么特别的？

刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果，但是最后输出结果不够清晰，而且程序执行的每一步都是跟着你的思想在进行， ...

你好！在吗？/我在网上看到你的一份关于农夫过河的问题！有个问题想请教你

lwy0319 发表于 2014-3-11 11:02
谢谢你，比我写得简练多了，其实我还是尽量让系统自己判断的，只不过用了循环，恨不得每一步都进行了循环并 ...

楼上的好像有点问题啊

学习啊了，厉害！

1. package com.itheima;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.List;
   
5. import java.util.Random;
   
6. 
   
7. /**
   
8. * 10、 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时， 狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
   
9. * 则不会发生这种问题。编程解决猫狗鱼过河问题。
   
10. *
    
11. * 分析：
    
12. *         假设动物和老农都在左岸，要到达右岸
    
13. *                 第一步：老农带着猫到达右岸
    
14. *                 第二步：老农一个返回左岸
    
15. *                 第三步：老农带着狗或者鱼到达右岸
    
16. *                 第四步：老农带着猫返回左岸
    
17. *                 第五步：老农带着非猫的动物到达右岸
    
18. *                 第六步：老农一个人返回左岸
    
19. *                 第七步：老农带着猫到达右岸
    
20. *                 过河完成！
    
21. *
    
22. * 把整个过河问题分为从左岸到右岸，从右岸到左岸这两个动作问题。
    
23. * 老农从左岸到右岸，必须带着动物，否则没有任何意义，并且该动物不能为上次从右岸返回到左岸的动物。老农从右岸到左岸，
    
24. * 如果可以不带动物，则不带，效率高，否则必须带一个动物返回左岸，并且该动物不能为上次从左岸到达右岸的动物。
    
25. *
    
26. * 采用过程追溯法来是实现过河问题，不满足条件追溯回原状态，知道满足条件为止。
    
27. *
    
28. * @author liuxiangyun
    
29. *
    
30. */
    
31. public class Test10 {
    
32.         List<String> leftBank = new ArrayList<String>();// 左岸
    
33.         List<String> rightBank = new ArrayList<String>();// 右岸
    
34. 
    
35.         public static void main(String args[]) {
    
36.                 new Test10().crossRiver();
    
37.         }
    
38. 
    
39.         public Test10() {
    
40.                 // 初始化数据
    
41.                 leftBank.add("person");
    
42.                 leftBank.add("fish");
    
43.                 leftBank.add("cat");
    
44.                 leftBank.add("dog");
    
45.         }
    
46. 
    
47.         // 过河
    
48.         public void crossRiver() {
    
49.                 boolean isAtLeftBank = true;// 老农是否在左边
    
50.                 String lastToLeftAnl = "";// 上一个到左边去的动物，默认没有，用""表示
    
51.                 String lastToRightAnl = "";// 上一个到右边去的动物，默认没有，用""表示
    
52.                 while (leftBank.size() > 0) {
    
53.                         //从左岸到右岸
    
54.                         if (isAtLeftBank) {
    
55.                                 lastToRightAnl = toRight(lastToLeftAnl);
    
56.                                 System.out.println("老农带着{" + lastToRightAnl + "}到达右岸");
    
57.                                 isAtLeftBank = false;
    
58.                         //从右岸到左岸
    
59.                         } else {
    
60.                                 lastToLeftAnl = toLeft(lastToRightAnl);
    
61.                                 if (lastToLeftAnl == "")
    
62.                                         System.out.println("老农一个人回到左岸");
    
63.                                 else
    
64.                                         System.out.println("老农带着{" + lastToLeftAnl + "}到达左岸");
    
65.                                 isAtLeftBank = true;
    
66.                         }
    
67.                 }
    
68.                 System.out.println("老农和动物全部过河！");
    
69.         }
    
70. 
    
71.         /**
    
72.          * 从左岸到右岸，老农必须携带一个动物，否则没有任何意义，并且要保证左右岸不出现安全问题
    
73.          *
    
74.          * @param lastToLeftAniaml
    
75.          *            上一个到左岸去的动物，没有则用""表示
    
76.          * @return 返回要携带的动物
    
77.          */
    
78.         public String toRight(String lastToLeftAniaml) {
    
79.                 boolean flag = true;
    
80.                 String animal = null;
    
81.                 while (flag) {
    
82.                         leftBank.remove("person");
    
83.                         animal = leftBank.get(new Random().nextInt(leftBank.size()));// 随机获取一个动物
    
84.                         leftBank.remove(animal);
    
85.                         rightBank.add("person");
    
86.                         rightBank.add(animal);
    
87.                         if (isSafe() && (animal != lastToLeftAniaml)) {// 不是上一个去左边的动物，并且不产生和谐问题
    
88.                                 flag = false;
    
89.                         } else {
    
90.                                 rightBank.remove("person");
    
91.                                 rightBank.remove(animal);
    
92.                                 leftBank.add("person");
    
93.                                 leftBank.add(animal);
    
94.                         }
    
95.                 }
    
96.                 return animal;
    
97.         }
    
98. 
    
99.         /**
    
100.          * 从左岸到右岸，老农独自返回，如果没有产生安全问题，他就独自返回，否则必须携带一个动物返回左岸，并且也要保证不产生安全问题。
     
101.          *
     
102.          * @param lastToRightAniaml
     
103.          *            上一个到达右岸的动物
     
104.          * @return 返回要携带的动物，没有则返回""
     
105.          */
     
106.         public String toLeft(String lastToRightAniaml) {
     
107.                 String animal = null;
     
108.                 rightBank.remove("person");
     
109.                 leftBank.add("person");
     
110.                 if (isSafe()) {
     
111.                         return animal = "";
     
112.                 } else {
     
113.                         leftBank.remove("person");
     
114.                         rightBank.add("person");
     
115.                         boolean flag = true;
     
116.                         while (flag) {
     
117.                                 rightBank.remove("person");
     
118.                                 animal = rightBank.get(new Random().nextInt(rightBank.size()));// 随机获取一个动物
     
119.                                 rightBank.remove(animal);
     
120.                                 leftBank.add("person");
     
121.                                 leftBank.add(animal);
     
122.                                 if (isSafe() && (animal != lastToRightAniaml)) {// 不是上一个去右边的动物，并且不产生和谐问题
     
123.                                         flag = false;
     
124.                                 } else {
     
125.                                         leftBank.remove("person");
     
126.                                         leftBank.remove(animal);
     
127.                                         rightBank.add("person");
     
128.                                         rightBank.add(animal);
     
129.                                 }
     
130.                         }
     
131.                 }
     
132.                 return animal;
     
133.         }
     
134. 
     
135.         // 判断左右岸是否存在安全问题
     
136.         public boolean isSafe() {
     
137.                 boolean leftBankIsSafe = true;
     
138.                 boolean rightBankIsSafe = true;
     
139.                 // 岸上没有老农，有猫且有狗或者鱼就存在安全问题
     
140.                 if (!leftBank.contains("person") && leftBank.contains("cat")
     
141.                                 && leftBank.size() > 1)
     
142.                         leftBankIsSafe = false;
     
143.                 if (!rightBank.contains("person") && rightBank.contains("cat")
     
144.                                 && rightBank.size() > 1)
     
145.                         rightBankIsSafe = false;
     
146.                 return leftBankIsSafe && rightBankIsSafe;
     
147.         }
     
148. }

复制代码