讨论/面试考题/面试题/
面试题

拖拉机过沙漠
有一片沙漠长度500KM,拖拉机每次加满油50L可以跑50KM,在沙漠的起点有无限的油,拖拉机可以从起点把油运到中途,在中途建立加油站,那么拖拉机刚好跑出沙漠需要加多少次油,来回多少次(改变一次向为一次),总共需要跑多远的里程?

展开讨论
Hell within reach发起于 2020-05-12
共 2 个讨论

我们从一开始开始看。
如果只跑1次,那最远是50km。
如果跑3次(只有可能是奇数),那最远是50 * (1 + 1/3)km,在1/3处放1/3的油,最后一次经过时拿走。
如果跑5次,那最远是50 * (1 + 1/3 + 1/5)km,在1/5处放3/5的油,每次经过拿1/5,再右边按照之前的策略,在(1/5+1/3)处放1/3的油,最后一次经过时刚好全部拿走。
以此类推。
因此如果跑2n + 1次,那最远可以到达50 * (1 + 1/3 + ... + 1/(2n + 1))km,然后就能算了,100km是15次,比楼上那个方法好,按楼上那个方法需要33次。
python循环代码

t = 0.0
for c in count(1, 2):
    t += 50 / c
    if t >= 100:
        print(c)
        break

楼上那个思路也很不错,但500km的数据规模不对劲,可能是题主记错了,500km我的方法没法算,两种思路的区别在于要尽可能把加油站靠前放,来节省运油的路费。

不过对于这道题目,500km的数据,没法算出精确解,因为如果你直接用循环算,肯定会超时,因为次数非常的大,因此我们查一下近似公式。
名字好像叫Harmonic progression Sum,忘了什么时候看到的了,可以自己去了解一下。
不过近似公式也会有误差,可以通过前几百项可以通过循环手动算来减小误差,后面再套公式。
我们先估计一个数据规模,然后用二分逼近,最终即可得到答案。

1

12.5建立一个加油站 一直建到450Km处 36个 第36站需50L 每个站 运输的损耗为50%(来回运输) 可以计算出共需 2^36*50 油 运送次为 2^37+1 不知道思路对不对