注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

力的博客

小歇一会 heiheidemaolv

 
 
 

日志

 
 

热门智力题 过桥问题  

2014-05-07 20:10:09|  分类: 热门面试题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一.过桥问题

在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时通过。如果各自单独过桥的话,四人所需要的时间分别是1258分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,你如何设计一个方案,让用的时间最少。

这个题目被微软、GOOGLE、百度、华硕、建设银行等很多公司用作笔试题或面试题。当然也有用在IQ测试中。

解答其实也容易,能者多劳这四个字就足以形容解答方案了——用时短的人必须要多跑几趟以便传递手电筒。

设这四个人叫做ABCD,他们所需要的时间分别是1258分钟。

第一步:AB过桥,花费2分钟。

第二步:A回来,花费1分钟。

第三步:CD过桥,花费8分钟。

第四步:B回来,花费2分钟。

第五步:AB过桥,花费2分钟。

这样只要花费2+1+8+2+2=15分钟,下面再来考虑如何用程序来解决这类问题,在写程序之前还有个细节要考虑下,比如ABCD四个人所需要的时间分别是18910分钟。

方案一

第一步:AB过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:CD过桥,花费10分钟。

第四步:B回来,花费8分钟。

第五步:AB过桥,花费8分钟。

一共要8+1+10+8+8=35分钟。

方案二

第一步:AB过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:AC过桥,花费9分钟。

第四步:A回来,花费1分钟。

第五步:AD过桥,花费10分钟。

一共要8+1+9+1+10=29分钟。

因此可以得出更加细化的解决方案——要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列,设为AB,…… YZ。其中AB是最快的二个,YZ是最慢的二个。那么就有二种方案:

方案一 最快者将最慢的2个送过桥

第一步:AZ过桥,花费Z分钟。

第二步:A回来,花费A分钟。

第三步:AY过桥,花费Y分钟。

第四步:A回来,花费A分钟。

这四步后总人数就减小2个,花费时间为A + A + Y + Z分钟。

方案二 最快的2个将最慢的2个送过桥

第一步:AB过桥,花费B分钟。

第二步:A回来,花费A分钟。

第三步:YZ过桥,花费Z分钟。

第四步:B回来,花费B分钟。

这四步后总人数同样减小2个,花费时间为A + B + B + Z分钟。

这样,每次比较一下这二种方案就能将总人数减小2。然后我们再考虑一些边界情况:

有三个人过桥设为ABC(已经排好序,下同)。应该花费A + B + C分钟。

有二个人过桥设为AB。那么肯定是花费B分钟。

有一个人过桥设为A。肯定花费A分钟。

 

分析至此,代码很容易写出,对输入的数据可以用快速排序来排下序(关于qsort的使用,可以参见《使用VC库函数中的快速排序函数》)。

  1. //热门智力题 - 过桥问题  
  2. #include<iostream.h>  
  3. #include<stdlib.h>  
  4. const int MAXN = 1000;  
  5. int cmp(const void *x,const void *y)  
  6. {  
  7.     return *(int *)x-*(int *)y;  
  8. }  
  9. int main()  
  10. {  
  11.     cout<<"热门智力题 - 过桥问题"<<endl;  
  12.     cout<<"  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n"<<endl;    
  13.   
  14.     int n, i, sum, a[MAXN];  
  15.     cout<<"请输入人数:";  
  16.     cin>>n;  
  17.     cout<<"请输入每个人过桥时间,以空格分开"<<endl;  
  18.     for (i = 0; i < n; i++)  
  19.         cin>>a[i];  
  20.     qsort(a, n, sizeof(a[0]), cmp);  
  21.     sum = 0;  
  22.     for (i = n - 1; i > 2; i = i - 2)  
  23.     {    
  24.         //最小者将最大2个送走或最小2个将最大2个送走  
  25.         if (a[0] + a[1] + a[1] + a[i] < a[0] + a[0] + a[i - 1] + a[i])  
  26.             sum = sum + a[0] + a[1] + a[1] + a[i];  
  27.         else  
  28.             sum = sum + a[0] + a[0] + a[i - 1] + a[i];    
  29.     }  
  30.     if (i == 2)  
  31.         sum = sum + a[0] + a[1] + a[2];  
  32.     else if (i == 1)   
  33.         sum = sum + a[1];  
  34.     else   
  35.         sum = a[0];  
  36.     cout<<"最短过桥时间为:"<<sum<<endl;  
  37.     return 0;  
  38. }  

程序运行结果如下:

 

  评论这张
 
阅读(56)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018