一道难题，汽车跑路

geslon

那可太令人失望了。这个答案肯定不对，小了。如果mathe说的真是这个答案，建议我们重新计算。

东邪

怀念gauss。
这里应该有很多人和gauss相识吧？mathe应该算一个，也应该知道答案。

这道题最早出现在天涯，dajiahao发的贴，这个人就是gauss，快十年了吧。

527肯定不是答案。

litaoye

不好意思，比较想当然的认为跟飞机加油是同样的问题，而忽略了可以带1桶油这个条件。

答案不会超过200 * (1 + 1/3 + 1/5 + ...... 1/99)，具体再想想。关键是有些油没有桶来装！

geslon

200 * (1 + 1/3 + 1/5 + ...... 1/99)，
不会这么小吧。

litaoye

还有问题是么？LZ可以把自己的思路说一下，我看看是什么问题没有想对！
我目前的是按照来回50次来算的，因此觉得上界应该不会超过200 * (1 + 1/3 + 1/5 + ...... 1/99)
因为有些油没有桶来放，因此判断结果不会超过这个上界。不知道还有那些地方有疏漏。

200 * (1 + 1/3 + 1/5 + ...... 1/99)，
不会这么小吧。
geslon 发表于 2009-12-20 08:26

geslon

200*（1+1/3+....+1/99）,那我是看错了，说错了。我看成100*（...）。郑重道歉。

KeyTo9_Fans

能载一桶油相当于汽车的油箱容量加倍。

相当于以2为单位，100桶油是50个单位，可设49个中间点，一共50段，每段用1个单位，所以第k段为1/(101-2k)个单位长度。

把一桶油倒进汽车油箱后，空油桶不能扔，应拿到下一个地点装汽车油箱里没用完的油（汽车油箱只需留下回程用的油），同时把承载的一满桶油放下。

所以主要问题是汽车还有没有地方放一个空油桶。

不然的话你得在中间点另找一个盛油的容器。

不然的话你只好在中间点把油冻成固体冷藏起来，到时候再拿出来解冻……

geslon

那就分为两个问题讨论：
1，如果中间点随时可以有空桶给你做临时存放，最大值是几？
2，就目前题目条件，空桶自己想办法解决，最大值是几？
3，汽油加进油箱，不可逆。最大值是几？

显然，1>=2>=3.
这道题的本意是情况2.不过我的解决方案是使用的情况3.
我知道这道题有好几年了（那道题初始状态有101桶油），一开始我的思路有问题，答案记得似乎不到520，自己还以为很完美了。后来看到资深网友“youjian”和“东邪”说，101桶应该可以到560多（未公布方案），感觉很诧异。后来有一段时间因为忙，这道题就放下了没有深入思考。大约一年以后偶然回忆起了，研究了不下一周时间，终于得到了560的答案。
然后我非常好奇，想知道此题原创是谁，而且在模拟对于N桶油是否有一般公式。