经典的穿越沙漠题本来是这样的：假设有N桶油（比如说5桶），一辆车。一桶油可以让车开一个单位的距离，车的油箱恰好和一个油桶一样大。途中任何地方都可以储存任意数量的油。这辆车能穿越多宽的沙漠？www.ddhw.com 这个问题不难，但不太实际：没有容器，油怎么能放在沙漠里？我们把题改得实际一点（但是难了很多）：www.ddhw.com 假设有2N桶油（算10桶吧），一辆车。一桶油可以让车开1/2个单位的距离，车的油箱恰好和一个油桶一样大，而且车上还可以装一个桶。如果车上有油桶，油桶和里面的油可以储存在途中任何地方。这辆车能穿越多宽的沙漠？www.ddhw.com 解答：www.ddhw.com www.ddhw.com 两题的解法都是找出一系列存油点S1，…，Sn，彼此距离为D1，…，D(n-1)，再设S1到终点距离为D0，Sn到起点距离为Dn，每个往返都从起点出发，到比上次更远的存油点，然后返回，最后一次一直开到终点。总距离为D0+D1+…+Dn，总用油量为D0+3D1+5D2+…+(2n+1)Dn。www.ddhw.com www.ddhw.com 对经典问题，容易看出Di=1/(2i+1)，在每个Si处存油(2i-1)/(2i+1)，以后再路过时加油1/(2i+1)，5桶油能开1+1/3+1/5+1/7+1/9 = 563/315 = 1.7873单位。www.ddhw.com www.ddhw.com 对改过的题就没有很好的公式了。从后面倒推可得D0=1，D1=1/3，D2=1/6，D3=2/15，D4=1/10，D5=8/105，…。10小桶油（能开5个单位距离）起点应该在离S5点1/33处，总距离为1+1/3+1/6+2/15+1/10+1/33 = 291/165 = 1.7636单位。具体方法：第一次到S5，存油18/33桶，以后每次路过取油2/33桶，9次取光。第二次到S4，存油1桶。第三次到S3，存油1桶，路过S4时不取油，以后再路过S4时，每次取油1/5桶，5次取光。第四次到S2，存油1桶，去时路过S3不取油，回来时取油1/5桶，以后再路过S3时，每次取油4/15桶，3次取光。第五次到S1，存油2/3桶。来回路过S2都取油1/3桶。最后一次到各存油点都加满油，开到终点。 www.ddhw.com 这些距离的算法比较繁琐。以D5为例，设D5为x，S6为起点。第一次开到S5，存油1桶。第二次开到S4，存油1桶。这次不用S5的油。第三次开到S3，存油一桶。这次来回要在S5 加4(x+1/10+2/15) -1桶油，以后再路过S5时，每次加2x桶油，共5次，即10x + 4(x+1/10+2/15) -1 = 1，解得 x = 8/105。www.ddhw.com www.ddhw.com 一般来说，油比较多的时候，前几个存油点离起点的距离小于1/4，算距离的时候先估计到哪一点距离超过1/4，然后用这一点的条件列方程。
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2006-3-12 06:09:59
收藏
分享
支持
反对
置顶卡
千斤顶
