穿越沙漠

constant · 发表于 2006-3-6 19:34:10

难度：++++www.ddhw.com

经典的穿越沙漠题本来是这样的：假设有N桶油（比如说5桶），一辆车。一桶油可以让车开一个单位的距离，车的油箱恰好和一个油桶一样大。途中任何地方都可以储存任意数量的油。这辆车能穿越多宽的沙漠？

这个问题不难，但不太实际：没有容器，油怎么能放在沙漠里？我们把题改得实际一点（但是难了很多）：

假设有2N桶油（算10桶吧），一辆车。一桶油可以让车开1/2个单位的距离，车的油箱恰好和一个油桶一样大，而且车上还可以装一个桶。如果车上有油桶，油桶和里面的油可以储存在途中任何地方。这辆车能穿越多宽的沙漠？

本贴由[constant]最后编辑于：2006-3-6 11:35:3

constant · 发表于 2006-3-25 20:03:01

我不是那条鱼 · 发表于 2006-3-25 07:31:39

我还是不懂

能不能不说英文

constant · 发表于 2006-3-10 17:22:43

经典的答案是1+1/3+1/5+...+1/(2N-1)，方法就是QL给出的。

zyang131 · 发表于 2006-3-10 06:07:07

不好意思，经典的答案是什么？

constant · 发表于 2006-3-7 02:05:25

A correction: It should be 1/(2*(2M-1))+1/(2*(2(M-1)-1)+...1/(2*3)+1/2+1/2. But the problem is that this is not optimal.

QL · 发表于 2006-3-6 21:57:22

I assume the truck has an empty tank at first.

The first barrel of gas can move the other M = 2N-1 barrels x units of distance, we have

(M*2-1)*x = 1/2, so x = 1/(2*(2M-1))

Similarly, the second barrel of gas can move the other M-1 barrels 1/(2*(2(M-1)-1)), and so on,

so the max distance will be:

1/(2*(2M-1))+1/(2*(2(M-1)-1)+...1/(2*2)+1/2+1/2

Do I miss something? Cause this doesn't seem like a ++++ in constant's scale.

		自动登录	找回密码
密码			立即注册

动态微博