汽车加油问题
一辆载油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)
第二题,可以反过来推。
最优的方案是车开到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点)放的油应该在(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;
(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)。
相关推荐
微软试题合集,里面是一些微软的面试题。希望对找工作的人有帮助
微软公司面试人员的面试题解答,google微软等大公司面试题,软件架构师的设计。
面试题 经典面试题 微软面试题 C#面试面试题 经典面试题 微软面试题 C#面试
微软面试试题...微软面试试题微软面试试题微软面试试题
微软面试题 数据结构 C++微软面试题 数据结构 C++
最近详细的微软面试题集锦C/C++试题赶快下载
IBM面试题集 MBA面试题集 微软面试题集
面试题,微软面试题答案,微软面试题答案,微软面试题答案
几道微软面试题,给大家参考一下(很有意思的)几道微软面试题,给大家参考一下(很有意思的)
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
微软面试题微软面试题微软面试题微软面试题微软面试题微软面试题
微软面试试题及答案 .
2023念整理编辑vue面试题详情介绍和解答.docx2023念整理编辑vue面试题详情介绍和解答.docx2023念整理编辑vue面试题详情介绍和解答.docx2023念整理编辑vue面试题详情介绍和解答.docx2023念整理编辑vue面试题详情介绍...
这是微软面试题以及答案,有了它,您可以做个又准备的人,因为机会只会给又准备的人
齐全的面试题,当前主流互联网公司 百度 腾讯 等面试题库 相当实用的文档,百度面试通过全靠它了
微软面试题选 微软面试题选 微软面试题选
408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试面试题及解答408复试...
微软面试题,机试,需要写出系统设计,源代码,及测试用例
微软等数据结构面试题100个 很实用哦,适合高级进阶架构看看,统一修改了博主所有下载文件的积分,方便大家学习,一起提升
微软面试题100道 程序员面试 应届生找工作 面试百度 找工作的童鞋们都看懂了,就可以进百度了