2 two water Two_Water 于 2016.09.20 00:34 提问

2017完美世界研发部笔试题_取经

一、题目概述

师徒四人西天取经,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗而他们只有一支手电筒,一次同时最多可以有两个人一起经过桥。而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒不能用丢的方式来传递,四个人的步行速度各不同,若两人同行则以较慢者的速度为准,大师兄需花1分钟过桥,二师兄需花2分钟过桥,三师兄需花5分钟过桥,师傅需花10分钟过桥。请问他们最短在多少分钟内过桥?()
A. 18
B. 17
C. 19
D. 16

一开始直接想到,用最小的那个数来回跑,也就是大师兄来回跑,算出来是19,可是又想了下,如下:
1、大师兄和二师兄过桥,算二师兄的时间也就是2分钟
2、大师兄独自拿手电回来 1分钟
3、三师弟和师傅那手电过桥,算师傅的时间也就是10分钟
4、二师弟拿手电回来 2分钟
5、最后大师兄和二师弟过桥 2分钟
总共17分钟

虽然结果出来了,感觉有点不实在,这其中的规律是怎样的呢?有没有什么规律解决这类似的问题呢,比如只有三个人过桥呢?二师兄不过桥,结果又是什么呢?再比如,多一个人过桥呢?多了个白龙马过桥,白龙马过桥的时间时6分钟,结果又是什么呢?有没有什么规律呢,或者说有没有个公式来计算呢?用编程怎么解?

具体看链接:http://blog.csdn.net/Two_Water/article/details/52590899

4个回答

qq_29594393
qq_29594393   Ds   Rxr 2016.09.20 17:17
已采纳

这个问题想了很久 ,像是递归,又有一些差别
分析一下如何过河吧,得出一个结论就是 ,数值最小的两个需要当勤劳的搬运工
1,2,5,10
不计手电的情况 ,就是 10,5 和 2,1,总计 12 ,
但是需要手电,在上述过程中先是 1 搬运一次 然后是2 搬运一次 ,由于搬运产生的额外开销 1,2 加2
也就是 12+1+2+2
分析1,2,3,5,10,
不计手电的情况 就是 10,5 和3,2 和 1 总计14
但是需要手电,在上述过程中先是 1 搬运一次 +1然后是2 搬运一次+2 ,由于搬运产生的额外开销 1,2 加2 ,然后 1又开始搬运 +1
14+1+2+2+1
分析1,2,3,5,7,10
不计手电的情况 就是10,7 和 5,3 和 2,1总计17
但是需要手电,在上述过程中先是 1 搬运一次+1 然后是2 搬运一次+2 ,由于搬运产生的额外开销 1,2 加2 ,然后 1又开始搬运 +1 ,然后 2搬运一次+2 额外开销2
17+1+2+2+1+2+2
然后就找出规程了,搬运一次+1 搬运第二次加4 ,第三次 加1 第四次加2

搬运的次数为 数组长度-2

接下来上代码 .....不必要了
就是先总结次数,然后加起来就可以了,

qq_29594393
qq_29594393 回复fuck两点水: 总结一下,只使用最小的数作为搬运,以1,2,5,10,为例,总数为19,1使用的次数为7次也就是1*7,而使用最小的两个数为5,也就是1*1+2*2,当第二小的数为3的时候,1*7和 1*1+2*3,也就是为什么1,3,4,5,会计算一样的原因,但是为什么不娶比值为3呢?,由于取最小的两位做搬运的额外次数的增加为1,2*2,1,2*2,散点式的增长,而只使用1的话,是线性增长,,那么1,3,4,5,会相等,但是1,3,4,5,6,就是使用一个搬运更优,
大约一年之前 回复
Two_Water
Two_Water 回复当作看不见: 请问为什么是2呢?
大约一年之前 回复
qq_29594393
qq_29594393 回复fuck两点水: 最好的方法是将着两者情况都算出来,比较大小,这就是我能想到的最优的算法了,虽然说不上好,但相对遍历来说效率高太多
大约一年之前 回复
qq_29594393
qq_29594393 回复fuck两点水: 1,4,5,10,的列子确实有些问题,还要再加一个判断第二小的数和最小的数的比值,大于>2,采用最小数一直搬运的方法。应该没问题了,你说的问题就能解决了
大约一年之前 回复
qq_29594393
qq_29594393 回复fuck两点水: 没错,计算一下1,3,4,5,确实是15,你仔细算一下,先过去1,3,,1回来 在过去4,5然后3送手电回来,和1一起回去
大约一年之前 回复
Two_Water
Two_Water 说错例子了,是1,4,5,10的时候,你会发现每次都用1去搬运,是时间最短的!max(1,4)+1+max(1,5)+1+max(1,10)=21
大约一年之前 回复
Two_Water
Two_Water 不计手电的情况 ,就是 1,3和4,5,总计8;需要手电时,1搬运一次,3搬运一次,由于搬运,产生的额外开销是1,3,,最后就是8+1+3+3=15
大约一年之前 回复
Two_Water
Two_Water 比如1,3,4,5 的时候,按你的分析,
大约一年之前 回复
caozhy
caozhy   Ds   Rxr 2016.09.20 03:26
Two_Water
Two_Water 谢谢了,答案是知道的!主要是这类题用编程怎么解决呢?最好可以应对类似的题目!
大约一年之前 回复
feng1790291543
feng1790291543   Ds   Rxr 2016.09.20 07:22

又是旧题目,网上很多的图片说明

Two_Water
Two_Water 没有找到比较好的解决方案,不知道有没有什么好的链接呢?
大约一年之前 回复
qq_29594393
qq_29594393   Ds   Rxr 2016.09.20 08:33

17分钟,求解题思路,还是代码??

wzq__janeGreen_
wzq__janeGreen_ ...
大约一年之前 回复
Two_Water
Two_Water 你好,用代码遍历所有的情况出来,选最优!或者有其他更好的方法?
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片