算法求教--汽车过沙漠(100分)

L

LuJuhe

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-07

• #1

一辆汽车要穿越一个宽1000公里的沙漠，假设汽车的耗油量是平均的每公里1升。
并且在起点处有容量不限的加油站，汽车能够装载500升汽油，要穿过沙漠必须
在沙漠中建立储油点。请问，在哪些地方建立储油点，能使汽车耗油最少地穿过
沙漠？每个储油点得存储多少汽油？

 

D

DarwinZhang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #2

假如不用考虑保险系数，在500公里处设立一个储油点。车子开到500公里处正好没油，
加一下，再开500公里。总共是消耗1000升汽油。你的题目是不是有问题？

 

Y

ysai

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #3

晕呀,问题是:储油点的油哪来?当然要汽车运来了

 

X

xyl999

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #4

关注 ！

 

L

LuJuhe

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #5

这是某本算法书上讲“倒推法”的一个例题，但是我觉得书上的答案有问题，所以提出来
大家讨论。。。 或者能够提出其它的办法。

 

D

DarwinZhang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #6

to ysai: 输油管来的，嘿嘿...
还是等楼主来澄清吧。

 

N

netameng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #7

呵呵，运油的与用油的是同一台车！

 

L

lldhz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #8

好象是有答案的啊！
你把倒推法写出来看看！

 

D

DarwinZhang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-10

• #9

to LuJuhe: 假如油是车运过去放在路边的话，
我认为不管怎么样开车子，假如要在一个点放汽油的话比如：
---a---------->b
---a<----------b
---a---------->b---------d
你总是至少要开3次，所以存储油的地点应该尽量离目的地远，
所以倒推法肯定是必须的。不妨把你看到的"倒推法"说来听听。

 

B

bqfhw

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-14

• #10

up

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-18

• #11

这道题在《电脑爱好者》1998年中的“擂台赛”出现过，等我明天把书拿过来...

摘抄自《电脑爱好者》98下半年合订本：
一辆卡车欲穿越X公里的沙漠，卡车耗油量为1升/公里，载油量为Y升（0<Y<X），计算最少
要建立几个加油站，才能使卡车消耗最少的汽油通过该沙漠。
由于耗油量不变，此题等价于汽车所走的距离最短。设自救加油站的方案可以由终点至起点
的方向逆向分析确定。
用序号1,2,..i依次表示从终点到起点加油站的编号，用符号d1表示终点与第1号加油站的距
离，di表示第i-1号与第i号加油站的间距。由于第1个加油站至终点线路段显然的最少往返数
为一趟，故d1<=y，依原题应取最大值d1=Y。
第2与1号加油站间距最少往返次数为3，从第2加油站满载油走到终点至少要出发两次，故有
3*d2+d1<=2Y，即d2<=(2*Y-di)/3=Y-3，d2最大可取d2=Y/3。
一般有结论：
1.第i与第i-1站之间距离最大可取di=Y/(2*i-1)；
2.第i个加油站至终点段的纵耗油量为 Si=i*Y。
证明（从略——太长了 ）
当x=1000,y=500时，可以算出n=7。总耗油量为n*Y+(2*n+1)*d(n+1)，当最后一个加油站到
起点的距离正好为Y/(2*n+1)时，可简化为(n+1)*Y，即(7+1)*500=4000。

 

L

LuJuhe

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-12-06

• #12

多人接受答案了。