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

1. import java.util.*;
   
2. 
   
3. /**
   
4. * 思路：使用递归。在此岸枚举动物过河，判断剩下是否能够共存，如果过河了，判断对岸的是否可以共存，两边轮流枚举，知道对岸的能够共存为此。
   
5. * @author 朦胧色彩
   
6. */
   
7. 
   
8. public class Test {  
   
9. 
   
10.         private static int go = -1;                // 记住过河的动物
    
11.         private static int back = -1;           // 记录回头的动物
    
12.         private static String animal[] = {"狗", "猫", "鱼"};
    
13. 
    
14.     public static void main(String[] args) {  
    
15.   
    
16.                 ArrayList<Integer> here = new ArrayList<Integer>();
    
17.                 ArrayList<Integer> there = new ArrayList<Integer>();
    
18. 
    
19.                 System.out.println("0代表狗，1代表猫，2代表鱼"+"\n");
    
20.                 // 初始化此岸的动物有哪些
    
21.                 for(int i = 0;i < 3; i++)
    
22.                         here.add(i);
    
23.                
    
24.                 // 一开始是过河
    
25.                 crossRiver(here, there, true, -1);
    
26.                 there.add(here.get(0));
    
27.                 here.remove(0);
    
28.                 System.out.println("最后农夫和猫过河");
    
29.                 System.out.println("此岸："+here+"\t彼岸："+there);
    
30.         }
    
31. 
    
32.         /*
    
33.          * a b 代表此岸，彼岸或者（彼岸，此岸），具体由where决定
    
34.          * where 代表的是过河和回来 true是此岸去彼岸，false是彼岸回此岸
    
35.          * type 是记录上一次过河或者回来的是哪种动物
    
36.          */
    
37.         public static void crossRiver(ArrayList<Integer> a, ArrayList<Integer> b, boolean where, int type)
    
38.         {
    
39.                 if(where) // 过
    
40.                         System.out.println("此岸："+a+"\t彼岸："+b);
    
41.                 else // 回
    
42.                         System.out.println("此岸："+b+"\t彼岸："+a);
    
43. 
    
44.                 for(int i = 0; i < a.size() ; i++)
    
45.                 {
    
46.                         if(type != a.get(i))
    
47.                         {
    
48.                                 int temp = a.get(i);
    
49.                                 //System.out.println(temp + " " + i);
    
50.                                 a.remove(i);
    
51.                                 if(!isOk(a) && a.size() > 1){
    
52.                                         a.add(temp);
    
53.                                         Collections.sort(a);
    
54.                                 }
    
55.                                 else
    
56.                                 {
    
57.                                         // 如果是过河的，那么用go记录住这次是谁过的，如果过了对岸，发现不能共存的话，就不能是它回头了，避免死循环
    
58.                                         if(where){
    
59.                                                 go = temp;
    
60.                                                 System.out.println("农夫和"+animal[temp]+"过河");
    
61.                                         }
    
62.                                         // 回头的，back记录住谁回头了
    
63.                                         else{
    
64.                                                 back = temp;
    
65.                                                 System.out.println("农夫和"+animal[temp]+"回河");
    
66.                                         }
    
67.                                         b.add(temp);
    
68.                                         Collections.sort(b);
    
69.                                         // 如果对岸只有一种动物，那么此岸还要继续
    
70.                                         if(b.size() == 1)
    
71.                                         {
    
72.                                                 //System.out.println(a+" "+b+"-1");
    
73.                                                 crossRiver(a, b, true, back);
    
74.                                         }
    
75.                                         // 当该岸已经有两种动物了，那就要判断是否能够共存，这里是不能共存的操作
    
76.                                         else if(!isOk(b))
    
77.                                         {
    
78.                                                 //System.out.println(b+" "+a+"-2");
    
79.                                                 if(where) // 如果是刚过去的，且目前该岸不能共存的话，那就回一种动物到对岸，并且该种动物不能是go
    
80.                                                         crossRiver(b, a, false, go);        
    
81.                                                 else // 如果是刚回来的，且目前该岸不能共存的话，那就过一种动物到对岸，并且该种动物不能是back
    
82.                                                         crossRiver(b, a, true, back);
    
83.                                         }
    
84.                                         else
    
85.                                         {
    
86.                                                 //System.out.println(a+" - " + b + "="+back);
    
87.                                                 crossRiver(a, b, true, back);
    
88.                                         }
    
89.                                 }
    
90.                         }
    
91.                 }
    
92.         }
    
93. 
    
94.         // 判断农夫所在的岸边是否能够共存
    
95.         public static boolean isOk(ArrayList<Integer> arr)
    
96.         {
    
97.                 int sum = 0;
    
98.                 if(arr.size() < 2)
    
99.                         return false;
    
100.                 for(int i = 0; i < arr.size(); i++)
     
101.                         sum += arr.get(i);
     
102.                 // 狗和猫相加是1，猫和鱼相加是3，都是不能共存的
     
103.                 if(sum == 1 || sum == 3)
     
104.                         return false;
     
105.                 return true;
     
106.         }
     
107. }  

复制代码

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

1. import java.util.*;
   
2. 
   
3. /**
   
4. * 思路：使用递归。在此岸枚举动物过河，判断剩下是否能够共存，如果过河了，判断对岸的是否可以共存，两边轮流枚举，知道对岸的能够共存为此。
   
5. * @author 朦胧色彩
   
6. */
   
7. 
   
8. public class Test {  
   
9. 
   
10.         private static int go = -1;                // 记住过河的动物
    
11.         private static int back = -1;           // 记录回头的动物
    
12.         private static String animal[] = {"狗", "猫", "鱼"};
    
13. 
    
14.     public static void main(String[] args) {  
    
15.   
    
16.                 ArrayList<Integer> here = new ArrayList<Integer>();
    
17.                 ArrayList<Integer> there = new ArrayList<Integer>();
    
18. 
    
19.                 System.out.println("0代表狗，1代表猫，2代表鱼"+"\n");
    
20.                 // 初始化此岸的动物有哪些
    
21.                 for(int i = 0;i < 3; i++)
    
22.                         here.add(i);
    
23.                
    
24.                 // 一开始是过河
    
25.                 crossRiver(here, there, true, -1);
    
26.                 there.add(here.get(0));
    
27.                 here.remove(0);
    
28.                 System.out.println("最后农夫和猫过河");
    
29.                 System.out.println("此岸："+here+"\t彼岸："+there);
    
30.         }
    
31. 
    
32.         /*
    
33.          * a b 代表此岸，彼岸或者（彼岸，此岸），具体由where决定
    
34.          * where 代表的是过河和回来 true是此岸去彼岸，false是彼岸回此岸
    
35.          * type 是记录上一次过河或者回来的是哪种动物
    
36.          */
    
37.         public static void crossRiver(ArrayList<Integer> a, ArrayList<Integer> b, boolean where, int type)
    
38.         {
    
39.                 if(where) // 过
    
40.                         System.out.println("此岸："+a+"\t彼岸："+b);
    
41.                 else // 回
    
42.                         System.out.println("此岸："+b+"\t彼岸："+a);
    
43. 
    
44.                 for(int i = 0; i < a.size() ; i++)
    
45.                 {
    
46.                         if(type != a.get(i))
    
47.                         {
    
48.                                 int temp = a.get(i);
    
49.                                 //System.out.println(temp + " " + i);
    
50.                                 a.remove(i);
    
51.                                 if(!isOk(a) && a.size() > 1){
    
52.                                         a.add(temp);
    
53.                                         Collections.sort(a);
    
54.                                 }
    
55.                                 else
    
56.                                 {
    
57.                                         // 如果是过河的，那么用go记录住这次是谁过的，如果过了对岸，发现不能共存的话，就不能是它回头了，避免死循环
    
58.                                         if(where){
    
59.                                                 go = temp;
    
60.                                                 System.out.println("农夫和"+animal[temp]+"过河");
    
61.                                         }
    
62.                                         // 回头的，back记录住谁回头了
    
63.                                         else{
    
64.                                                 back = temp;
    
65.                                                 System.out.println("农夫和"+animal[temp]+"回河");
    
66.                                         }
    
67.                                         b.add(temp);
    
68.                                         Collections.sort(b);
    
69.                                         // 如果对岸只有一种动物，那么此岸还要继续
    
70.                                         if(b.size() == 1)
    
71.                                         {
    
72.                                                 //System.out.println(a+" "+b+"-1");
    
73.                                                 crossRiver(a, b, true, back);
    
74.                                         }
    
75.                                         // 当该岸已经有两种动物了，那就要判断是否能够共存，这里是不能共存的操作
    
76.                                         else if(!isOk(b))
    
77.                                         {
    
78.                                                 //System.out.println(b+" "+a+"-2");
    
79.                                                 if(where) // 如果是刚过去的，且目前该岸不能共存的话，那就回一种动物到对岸，并且该种动物不能是go
    
80.                                                         crossRiver(b, a, false, go);        
    
81.                                                 else // 如果是刚回来的，且目前该岸不能共存的话，那就过一种动物到对岸，并且该种动物不能是back
    
82.                                                         crossRiver(b, a, true, back);
    
83.                                         }
    
84.                                         else
    
85.                                         {
    
86.                                                 //System.out.println(a+" - " + b + "="+back);
    
87.                                                 crossRiver(a, b, true, back);
    
88.                                         }
    
89.                                 }
    
90.                         }
    
91.                 }
    
92.         }
    
93. 
    
94.         // 判断农夫所在的岸边是否能够共存
    
95.         public static boolean isOk(ArrayList<Integer> arr)
    
96.         {
    
97.                 int sum = 0;
    
98.                 if(arr.size() < 2)
    
99.                         return false;
    
100.                 for(int i = 0; i < arr.size(); i++)
     
101.                         sum += arr.get(i);
     
102.                 // 狗和猫相加是1，猫和鱼相加是3，都是不能共存的
     
103.                 if(sum == 1 || sum == 3)
     
104.                         return false;
     
105.                 return true;
     
106.         }
     
107. }  

复制代码