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

Question

一、题目概述

师徒四人西天取经，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗而他们只有一支手电筒，一次同时最多可以有两个人一起经过桥。而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒不能用丢的方式来传递，四个人的步行速度各不同，若两人同行则以较慢者的速度为准，大师兄需花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

Answer 1

这个问题想了很久 ,像是递归,又有一些差别
分析一下如何过河吧,得出一个结论就是 ,数值最小的两个需要当勤劳的搬运工
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

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