题目如下:
一辆载油500升的汽车从A开往1000公里外的B,已知汽车每公里耗油量为1升,A处有无穷多的油,其他任何地点都没有油,但该车可以在任何地点存放油以备中转,问从A到B最少需要多少油。
这个题想了好多天也没想出来,在网上找答案也都是基本相同的,只给出了一个结论,而没有一个详细推导过程。今天没事在家仔细的推导了一下,终于有些眉目了。记录如下:
由最少耗油的要求,先得有几个前提:
1.汽车到达终点时油箱是空的。
2.路上的每一个中转点都没有剩下油。
现在画一个数轴,代表起点到终点的路径,在这个数轴上取m个点,分别记为X(1),X(2),...,X(m)。X(i)表示第i个点到终点的距离。1号点为起点,m号点为终点。所以有X(1)=0,X(m)=1000。设汽车油箱的容量为A,由题目可知A=500。设S(i)表示在第i最少存放多少升油,那么显然S(m)=0,而我们要求的就是S(0)。再设n(i)为从第i-1点到第i点需要的往返次数(注意,一去一回代表一次往返)。好,以上就是需要定义的一些符号,下面开始推导过程:
从i-1点往i点运油时,最节省的情况是从i-1点出发时应该油箱装满油,然后在i点放下油后回到i-1点时油箱是空的,这时候运油的效率是最高的。所以有:
S(i) = A - [X(i)-X(i-1)] + {A - 2*[X(i) - X(i-1)]}*n(i)。
上式中A - [X(i)-X(i-1)]是最后一次从i-1点到i点油箱中剩下的油;{A - 2*[X(i) - X(i-1)]}*n(i)表示在n(i)次往返过程中总共在i点存下的油。把上式化简合并一下得到式(1):
S(i) = [n(i) + 1]*A - [2*n(i) + 1]*[X(i) - X(i-1)] -----(1)
又因为到第i点存下的油等于第i-1点存下的油减去从i-1点到i点的总损耗,而从i-1点到i点的总损耗为[2*n(i) + 1]*[X(i) - X(i-1)],所以有下式:
S(i) = S(i-1) - [2*n(i) + 1]*[X(i) - X(i-1)]。
把(1)式带入上式则可得到式(2-1):
S(i-1) = [n(i) + 1]*A -----(2-1)
同理有式(2-2)
S(i) = [n(i+1) + 1]*A -----(2-2)
用(2-1)减去(2-2)得到式(3):
S(i-1) - S(i) = [n(i) - n(i+1)]*A -----(3)
因为S(i-1) - S(i)表示的是从i-1点到i点的总损耗,而A是固定值,所以由(3)式得知,要使总损耗最小,就需要n(i) - n(i+1)最小,因为S(i-1) - S(i)必然>0,所以n(i) - n(i+1)>0,且n[i]是整数,所以就有min([n(i) - n(i+1)]) = 1。所以有式(4):
n(i) - n(i+1)= 1 ==> n(i) = n(i+1) + 1 -----(4)
把式(4)代入式(2-2)就得到式(5):
S(i) = n(i)*A -----(5)
再把式(5)代入式(1)并化简就可以得到式(6):
X(i) - X(i-1) = A/[2*n(i) + 1] -----(6)
X(i) - X(i-1)表示的相邻两点之间的距离,所以显然要达到终点的话就必须有:
又因为n(m)=0,即从最后一个中转点到终点是不需要往返的。再由式(4)就有:n(m-1) = 1,n(m-2) = 2, …,即有n(i) = m-i成立。我们从终点往起点回退,再由上式就有:
所以求出来m=8。但是m=8时,求出来的和 约等于1010.9比1000大,所以不能由式(5)直接算S(0),而应该先算S(1) = (m-1)*A = (8-1)*500 = 3500升。也就是说在第一个中转点应该要存3500升油。然后再算从第0点到第1点的损耗,由前面的计算我们可以得到X(1) = 1000 – (500 + 500/3 + 500/5 + 500/7 + 500/9 + 500/11 + 500/13) ≈ 22.433米。
所以从第0点到第1点的总耗损可以由前面的总损耗公式[2*n(i) + 1]*[X(i) - X(i-1)]求出:
[2*n(1) + 1]*(22.433 - 0) = (2*7 + 1)*22.433 = 336.495
所以总耗油量就约为 3500 + 336.495 = 3836.495升。
Reprint from:http://blog.csdn.net/bad_sheep/article/details/5830013
相关推荐
reprint 是一个适用于 Python 2/3 的简易变量绑定与多行输出刷新的库
reprint 使用说明 直接从datasource,dbgrid,stringgrid导入数据, 只需简单设置,不用手工制作,即可生成您需要的报表,具有预览功能。即可自定义纸张,又可适应 打印机默认纸张。各种打印设置,功能更强大。 ...
A simple, unified fingerprint authentication library for Android with RxJava extensions. Eliminates the need to deal with the different available Fingerprint APIs, including Imprint and Samsung Pass....
gartner reprint-2018
reprint 使用说明 本人长期使用delphi做数据库的开发,报表控件使用Quickrpt,在打印上经常遇到一些问题,于是自己经常编写一部分打印的程序,经过总结开发了这个控件。 本控件可打印 datasource,dbgrid,...
2019 Gartner Reprint_APM_英文原版 Gartner Reprint_APM_英文原版 Gartner Reprint_APM_英文原版
不推荐使用请改用 ,它支持... 在您的Application.onCreate ,使用Reprint.initialize(this)初始化Reprint。 这将加载棉花糖模块和Spass模块(如果包含)。 然后,在代码中的任何位置,都可以调用Reprint.authenticate
with块一起使用以控制初始化, output对象包含以下参数: output_type : "list"或"dict" (默认值: "list" ),指示列表模式或dict模式。 initial_len : int (默认值: 1 ),仅在列表模式下工作,指示列表的...
Processing of signals is often facilitated by transforming to a representation in which individual components are statistically independent. In such a natural coordinate system, the components of the ...
资源来自pypi官网。 资源全名:reprint-0.3.0.tar.gz
reprint 使用说明 本控件可打印 datasource,dbgrid,stringgrid. 一 、控件属性: 1、colstitle 设置报表的列标题属性 (1) Print:boolean;;是否打印 (2) Font:tfont;;字体 (3) Rowsline:tpen;;横线...
使用重印,用户可以下载和共享永久免费的NFT重印。 如果您喜欢某种风格,请跟随艺术家进入其实际的NFT销售页面。 浏览趋势重印。 创建您最喜欢的转载的集合。 演示版 截屏 屏幕截图即将推出! 目录 安装 运行npm ...
具有带通选择性的ICA算法可以改善对于带通时间序列的... 因此本文提出的方案可将被估计信号, 如:周期性响应信号以及具有平滑空间分布的脑功能激活区, 的先验特性以特征选择的方式加入ICA算法用以提高对此类信号的估计
用最简单的方式让你的项目接入安卓的指纹识别功能,内为demo和工具源码!
Gartner 2019 十大安全项目 中文版
是检测估计和调制理论的经典著作,最新版,2013版,英文原版,Highly readable paperback reprint of one of the great time-tested classics in the field of signal processing Together with the reprint of Part ...
SCRIPTWRITER
Reprint only shows that the program is very high
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, ...we may rectify in any future reprint.