珍珠湾ART

标题: 穿越沙漠 [打印本页]

作者: constant 时间: 2006-3-6 19:34
标题: 穿越沙漠

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

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

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

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

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

作者: QL 时间: 2006-3-6 21:57
标题: 回复：穿越沙漠

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.

作者: constant 时间: 2006-3-7 02:05
标题: 回复：回复：穿越沙漠

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.

作者: zyang131 时间: 2006-3-10 06:07
标题: 回复：穿越沙漠

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

作者: constant 时间: 2006-3-10 17:22
标题: 回复：回复：穿越沙漠

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

作者: 我不是那条鱼 时间: 2006-3-25 07:31
标题: 回复：穿越沙漠

我还是不懂

能不能不说英文

作者: constant 时间: 2006-3-25 20:03
标题: 后边有答案

欢迎光临珍珠湾ART (http://66.160.158.134/)