贮油点问题计算一辆重型卡车欲穿过1000公里的沙漠,卡车耗汽油为1升/公里,卡车总载油能力为500公升.显然卡车装一次油是过不了沙漠的.因此司机必须设法在沿途建立若干个贮油点,使卡车能

Question

贮油点问题计算
一辆重型卡车欲穿过1000公里的沙漠,卡车耗汽油为1升/公里,卡车总载油能力为500公升.显然卡车装一次油是过不了沙漠的.因此司机必须设法在沿途建立若干个贮油点,使卡车能顺利穿过沙漠.试问司机如怎样建立这些贮油点?每一贮油点应存储多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠?
求详细解答.

Answer 1

分析：
如果从起点出发顺推,则我们无法确定第一个贮油点的位置及贮油量,因此我们可以用倒推法来解决这个问题：先从终点出发倒推最后一个储油点的位置及储油量,然后再把最后一个储油点作为终点,倒推倒数第二个储油点的位置及储油量,… ….设dis[i]表示第i个贮油点到终点（i=0）的距离；oil[i]表示第i个贮油点的贮油量.
从贮油点i向贮油点i+1倒推的方法是：卡车在贮油点i和贮油点i+1间往返若干次,卡车每次返回i+1点时应该正好耗尽汽油,而每次从i+1点出发时又必须装足500L汽油.两点之间的距离必须满足在耗油最少的条件下,使i点贮足i*500L汽油的要求（0≤i≤n-1）.具体地说,第一个贮油点i=1应距终点i=0处500km,且在该点贮藏500L汽油,这样才能保证卡车能由i=1处到达终点i=0处,这就是说dis[i]=500；oil[i]=500.
为了在i=1处贮藏500L汽油,卡车至少从i=2处开两趟满载油的车至i=1处,所以i=2处至少贮有2*500L汽油,即oil[2]=500*2=1000；另外,再加上从i=1返回至i=2处的一趟空载,合计往返3次.三次往返路程的耗油量按最省要求只能为500L,即d12=500/3km.
pascal程序：
program xt3207;
var a,o:array[1..20]of real;
k,i,j:integer;
begin
a[1]:=500; o[1]:=500; k:=1; i:=1;
repeat
k:=k+2;
i:=i+1;
a[i]:=a[i-1]+500/k;
o[i]:=500+o[i-1];
until a[i]>=1000;
o[i]:=o[i]-(a[i]-1000)*k;
a[i]:=1000;
for j:=i downto 1 do writeln(1000-a[j]:0:1,' ',o[j]:0:1);
readln;
end.