微软面试题 汽车加油【求人解答】

 汽车加油问题
一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油？

 

答案：

(提示，严格证明该模型最优比较麻烦，但确实可证，大胆猜想是解题关键)
题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6
当n=6时，S6=977.57
所以第一个中转点离起始位置距离为1000-977.57=22.43公里
所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升
此后每次中转耗油500升
所以总耗油量为7*500+336.50=3836.50升

 

写道

http://bbs.csdn.net/topics/340205828 得到了提示
第二题，可以反过来推。
最优的方案是车开到B地时油刚好被用完。
那当然最后一个中转油的地方离B地500公里，并且车在这个地方能够把邮箱装满。
要满足上面这条，车必须在到达最后一个中转点时，先从前一个中转点搬部分油到这个中转点，然后再在前一个中转点加满油，跑到最后一个中转点时，路上消耗的油正好是最后一个中转点放的油。我们可以很简单地看到这辆车500升的油在最后一个中转点和前一个中转点之间要跑500公里是最优方案，而这段距离刚好要跑3次，于是前一个中转点离最后一个中转点的距离是500/3公里。
依此类推，可以得到上面那个通项公式an=500/(2n+1)

 

最后中转点（n）为中点 写道

最优解：汽车经过最后中转点时候可以将油加满然后到总结正好油完。

 

倒是第二个中转点（n-1点） 写道

（n-1点）应该向n点中转油。
（n点）放的油应该在（n-1点）出发最后一次的正好加满车。
车最少在（n-1点）到（n点）开2次，一次送油，一次经过而且加上存的油正好加满。

设（n点）放的油是x，而要正好在车经过的时候车正好加满，x就要等于路程（这样路程消耗了x，正好加x油加满）。

那么第一从（n-1点）到（n点）放的油是x，路径是x，还要返回，这样2x+x=500，也就是（n-1点）到（n点）的距离是500/3。

（n-1点）总结：
（n点）到终点的距离 ：500
（n点）到终点的此次 ：1次
（n点）放油 ：500/3
（n-1点）到（n点）距离：500/3
（n-1点）到（n点）次数：2次
（n-1点）放的油 ：500 + x；

 

倒是第三个中转点（n-2点） 写道

（n-2点）到（n-1点）次数：2次不可能，第一次要带500油到（n-1点）不可能。
（n-2点）到（n-1点）次数：3次。前两次带油500+x，最后要求路上的消耗正好（n-1点）放的油x（这样x就是路程了）。
带油2*（500-2x）= 500 + x，这样x=500/5

（n-2点）总结：
（n点）到终点的距离 ：500
（n点）到终点的此次 ：1次
（n点）放油 ：500/3
（n-1点）到（n点）距离：500/3
（n-1点）到（n点）次数：2次
（n-1点）放的油 ：500 + x；（x = 500/5）
（n-2点）到（n-1点）距离：500/5
（n-2点）到（n-1点）次数：3次
（n-1点）放的油 ：500 + 500 + y；

 依次推出中转点之间的距离500，500/3，500/5，500/7，500/9，....,500/(2n+1)。