一位探险家必须穿过一片宽度为800km的沙漠,他仅有的交通工具是一辆每升汽油可以行驶10km的吉普车,这辆吉普车的油箱可以装10L汽油.另外车上还携带着8个可装5L汽油的油桶,也就是说,吉普车

Question

一位探险家必须穿过一片宽度为800km的沙漠,他仅有的交通工具是一辆每升汽油可以行驶10km的吉普车,这辆吉普车的油箱可以装10L汽油.另外车上还携带着8个可装5L汽油的油桶,也就是说,吉普车最多可以携带50L汽油（最多能在沙漠中连续行驶500km）.现在假定在探险家出发地处的汽油是无限充足的,问这位探险家应该怎样设计他的旅行才能通过此沙漠?他要通过沙漠所需的汽油最少是多少升?为穿过这片800千米宽的沙漠,他总共需要行驶多少公里的路程,总共要花费多少升的汽油?

Answer 1

思路：
1、若沙漠只有550公里或者更短,这时很简单,一次搞定.  \x0b2、若沙漠有600km,怎么办?需要保证的是：车到了离沙漠终点还有550km的地方,能恰恰加满油且不会有多余.方案可为：600-550＝50,从起点处加5*3(趟)＝15升油,开出50km,设一加油站,存下5升,剩下5升刚好使得汽车返回起点.再在起点处加满55升油,到加油站时,只乘50升了,把存放在那儿的5升油加上.则可跑出沙漠.（这样共加油15＋55＝70,总路程为150+550＝700km）   \x0b3、再看2的情况,符合这种情况的沙漠的最大距离是多少呢：答案是550*（1+1/3）公里.即在起点准备110升油,第一次装550升,跑了550/3公里后存放55*1/3升油,然后返回起点,这时车里的油也正好用完,然后再在起点处装55升,跑了55/3公里后,车内剩下（55*2/3）升油,再加上存放的55*1/3升油,恰好为55升油,则可跑出沙漠.   
4.当沙漠的距离超过了550*（1+1/3）km（但又超过得不多）又当如何?这时我们可以把前面的550*（1+1/3）km看成一段整体,需要保证的是：在距离沙漠终点550*（1+1/3）km处恰恰有110升油（由3的分析可知）.怎么来保证呢,我们假设沙漠的距离只比550*（1+1/3）多了1公里,因为汽车的容量是55升,所以110升油最少从起点运3次油才能满足.除了3次装油,还有两次折回,所以往返正好有5次,这5次的能保证的距离是550/5,所以这时我们又把沙漠的距离延伸到了：550*（1+1/3+1/5）,起点应该储备165升油.  \x0b5.当沙漠的距离超过了550*（1+1/3+1/5）km,要保证在距离沙漠终点550*（1+1/3+1/5）km的地方有165升油.
综上所述：总有某一个值k,使得
fdis=550*（1+1/3+1/5+…+1/(2k-1)）800,
应该在起点准备多少油呢?这时多了一小段出来,按情形2的分析,在起点准备的油应当是：
（(800 - fdis)/油耗）*往返次数  + k*55.
经计算：fdis=733.33,k=2,故应准备的油应为：
（(800 – 733.33)/10）*5  + 2*55＝143.33.