给大家分享一下

四个人晚上要过一个桥回家,
由于桥上的灯坏了,只能用四个人仅有的一个手电筒照明,手电筒只能坚持照明17分钟.
而且桥很窄,一次只能通过两个人,
四个人过桥的速度也不同,甲乙丙丁过桥需要的时间分别是1分钟.2分钟.5分钟.10分钟.
问 怎样能让4人全部照明通过

挺有意思的，。。。。。。。。

我没算这个题，但是我好多年前就听过这个……

代码写得有点长，你自己优化一下，希望可以帮到你

1. import java.util.ArrayList;
   
2. 
   
3. /**
   
4. * 思路：在桥这边枚举两个人过去，然后在桥那表让花时最小的送手电筒回来，
   
5. * 然后继续枚举两个人过桥，再让花时最小的送手电筒回来，循环的，直到这边的人只剩下两个。
   
6. */
   
7. 
   
8. class Tie_2
   
9. {
   
10.         // 记录过程
    
11.         private static String changes = "";
    
12.          // 标记是否成功过桥，若成功过了，那么就跳出，不找了
    
13.         private static boolean isCross = false;
    
14. 
    
15.         public static void main(String[] args)
    
16.         {
    
17.                 ArrayList<Integer> here = new ArrayList<Integer>();
    
18.                 ArrayList<Integer> there = new ArrayList<Integer>();
    
19.                 init(here,there);
    
20. 
    
21.                 // 枚举两个人过桥
    
22.                 o:for(int i=0; i<here.size(); i++)
    
23.                 {
    
24.                         for(int j=0; j<here.size(); j++)
    
25.                         {
    
26.                                 if(i==j)
    
27.                                         continue;
    
28.                                 int timeone = here.get(i);
    
29.                                 int timetwo = here.get(j);
    
30.                                 if(!isCross){
    
31.                                         crossBridge(here,there,timeone,timetwo,0);
    
32.                                         init(here,there);
    
33.                                 }else{
    
34.                                         break o;
    
35.                                 }
    
36.                         }
    
37.                 }
    
38.         }
    
39. 
    
40.         // 初始化数据
    
41.         public static void init(ArrayList<Integer> here,ArrayList<Integer> there)
    
42.         {
    
43.                 here.clear();
    
44.                 there.clear();
    
45.                 here.add(1);
    
46.                 here.add(2);
    
47.                 here.add(5);
    
48.                 here.add(10);
    
49.         }
    
50. 
    
51.         // 过桥
    
52.         public static void crossBridge(ArrayList<Integer> a, ArrayList<Integer> b, int timeone, int timetwo,int allTime)
    
53.         {
    
54.                 // 取出花时最大的
    
55.                 int bigTime = timeone > timetwo ? timeone : timetwo;
    
56.                 changes += "这边：" + a +"  -------桥--------  " + "那边："+b + "\n\t" +timeone + "和" + timetwo + "一起过桥！---用时："+bigTime+"分\n";
    
57.                 // 将过桥的两个存在b集合，代表过桥了
    
58.                 b.add(timeone);
    
59.                 b.add(timetwo);
    
60.                 allTime += bigTime; // 一共用了多少时间
    
61. 
    
62.                 // 把过桥的两个人在a集合中删除
    
63.                 for(int i=0;i<a.size();i++)
    
64.                         if(timeone==a.get(i)){
    
65.                                 a.remove(i);
    
66.                                 break;
    
67.                 }
    
68.                 for(int i=0;i<a.size();i++)
    
69.                         if(timetwo==a.get(i)){
    
70.                                 a.remove(i);
    
71.                                 break;
    
72.                 }
    
73.                
    
74.                 // 在这边找一个花时最小的送手电筒回去
    
75.                 int smallTimeIndex = getSmallTime(b); // 花时最小的时间的角标
    
76.                 changes += "这边：" + a +"  -------桥--------  " + "那边："+b+"\n\t"
    
77.                                 + b.get(smallTimeIndex)  + "送手电筒回去！---用时：" +b.get(smallTimeIndex)+"分\n";
    
78.                 allTime += b.get(smallTimeIndex); // 累加时间
    
79.                 a.add(b.get(smallTimeIndex)); // 送手电筒回去了，就添加到a集合
    
80.                 b.remove(smallTimeIndex);
    
81. 
    
82.                 // 出口判断
    
83.                 if(a.size()==2 && b.size()==2)
    
84.                 {
    
85.                         bigTime = Math.max(a.get(0),a.get(1));
    
86.                         allTime+=bigTime;
    
87.                         if(allTime > 17)
    
88.                         {
    
89.                                 changes = "";
    
90.                                 return;
    
91.                         }
    
92.                         System.out.println(changes +"\t"+ a.get(0)+"和"+a.get(1) +"一起过桥！---用时："+bigTime+"分");
    
93.                         System.out.println("\t一共花时："+allTime+"分");
    
94.                         isCross = true; // 标记已经成功过桥了
    
95.                         changes = "";
    
96.                         return;
    
97.                 }
    
98. 
    
99.                 // 继续枚举两个人过桥
    
100.                 for(int i=0; i<a.size(); i++)
     
101.                 {
     
102.                         for(int j=0; j<a.size(); j++)
     
103.                         {
     
104.                                 if(i==j)
     
105.                                         continue;
     
106.                                 timeone = a.get(i);
     
107.                                 timetwo = a.get(j);
     
108.                                 if((allTime + (timeone > timetwo ? timeone : timetwo)) > 17)
     
109.                                         continue;
     
110.                                 crossBridge(a,b,timeone,timetwo,allTime);
     
111.                         }
     
112.                 }
     
113.                
     
114.         }
     
115. 
     
116.         // 获取b集合中花时最小时间的角标
     
117.         public static int getSmallTime(ArrayList<Integer> b)
     
118.         {
     
119.                 int small = Integer.MAX_VALUE;
     
120.                 int index = -1;
     
121.                 for(int i=0;i<b.size();i++)
     
122.                         if(small > b.get(i))
     
123.                         {
     
124.                                 small = b.get(i);
     
125.                                 index = i;
     
126.                         }
     
127.                 return index;
     
128.         }
     
129. }
     

复制代码

输出结果：
这边：[1, 2, 5, 10]  -------桥--------  那边：[]
        1和2一起过桥！---用时：2分
这边：[5, 10]  -------桥--------  那边：[1, 2]
        1送手电筒回去！---用时：1分
这边：[5, 10, 1]  -------桥--------  那边：[2]
        5和10一起过桥！---用时：10分
这边：[1]  -------桥--------  那边：[2, 5, 10]
        2送手电筒回去！---用时：2分
        1和2一起过桥！---用时：2分
        一共花时：17分

SF_NEVERMORE 发表于 2015-10-8 22:38
甲乙过桥2分钟  甲回1分钟 丙丁过桥10分钟  乙回2分钟 甲乙过桥2分钟

我觉得二楼解的不错

这是Java  面试 出的题吗

考这个就完蛋了。。。。。我的天

..........有没有大能来发代码······

怎么用代码写出来

挺有意思的

好有意思   请问用代码怎么实现

这个比较厉害！

人：4个  灯：1（17f）  桥 ：1 （2） 【1，2,5,10】 全过、 我有个疑惑。ab- a =3  cd-b=12   ab=2   唯一的关键点，还是在于b的调回哈，a就是运送

看了半天不懂

甲乙过去用2分钟 甲回来1分钟 丙丁过去10分钟 甲回来2分钟 甲乙再过去2分钟
2+1+10+2+2 一共17分钟

想了挺长时间，最后想到可以让最先过去的乙或甲最后返回来接甲或乙才通过

这个题逻辑性太高,HOLD不住啊

呃，，好逻辑的题

很有趣 有没有大神用代码写一个?

赞一个 很有意思 能不能用代码写出来?