沙漠储油点

沙漠储油点"/>

沙漠储油点

原文地址：沙漠储油点 作者：忽然之间
      一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？
算法分析：
      编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。
              No.              Distance(k.m.)              oil(litre)
              1                              X X                              X X
              2                              X X                              X X
              3                              X X                              X X
              ...                            .....                          ......
      设dis[i]    为第i个贮油点至终点(i=0)的距离；
          oil[i]    为第i个贮油点的存贮油量；
      我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。
下图表示倒推时的返回点：

 

      从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500分升汽油的要求(0<=i<=n-1)。具体地讲，第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说
      dis[1]=500              oil[1]=500;
      为了在i=1处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000。另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d ₁₂=500/3km
              dis[2]=dis[1]+d ₁₂=dis[1]+500/3

 

      为了在i=2处贮存1000公升汽油，卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车，合计5次。路途耗油量也应为500公升，即d ₂₃=500/5,
              dis[3]=dis[2]+d ₂₃=dis[2]+500/5;

 

      依此类推，为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即
      oil[k+1]=[k+1]*500=oil[k]+500，加上从i=k处返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即
      d _k,k+1=500/(2k-1)
                dis[k+1]=dis[k]+d _k,k+1
                                =dis[k]+500/(2k-1);

 

      最后，i=n至始点的距离为1000-dis[n],oil[n]=500*n。为了在i=n处取得n*500公升汽油，卡车至少从始点开n+1次满载车至i=n，加上从i=n返回始点的n趟返程空车，合计2n+1次，2n+1趟的总耗油量应正好为(1000-dis[n])*(2n+1)，即始点藏油为oil[n]+(1000-dis[n])*(2n+1)。
   
转换为C语言程序如下：
#include<stdio.h>
void main()
{
    int k;            
    float d,d1;      
    float oil[10],dis[10];
    int i;
    printf("NO. distance(k.m.)toil(l.)n");
    k=1;
    d=500;       
    dis[1]=500;
    oil[1]=500;
    do{
        k=k+1;
        d=d+500/(2*k-1);
        dis[k]=d;
        oil[k]=oil[k-1]+500;
    }while(!(d>=1000));
    dis[k]=1000;       
    d1=1000-dis[k-1];   
    oil[k]=d1*(2*k+1)+oil[k-1];   
    for(i=0;i<k;i++)      
        printf("%dt%ft%ftn",i,1000-dis[k-i],oil[k-i]);
}