编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。格式如下:
No. Distance(k.m.) Oil(litre)
1 × × × ×
2 × × × ×
… … … … …分析:
设Way[I]——第I个贮油点到终点(I=0)的距离;
oil[I]——第I个贮油点的贮油量;
我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。
从贮油点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处,这就是说
Way[I]=500;oil[I]=500;
为了在I=1处贮藏500公升汽油,卡车至少从I=2处开两趟满载油的车至I=1处,所以I=2处至少贮有2*500公升汽油,即oil[2]=500*2=1000;另外,再加上从I=1返回至I=2处的一趟空载,合计往返3次。三次往返路程的耗油量按最省要求只能为500公升,即d12=500/3km,Way[2]=Way[1]+d12=Way[I]+500/3
此时的状况如图20所示。
为了在I=2处贮藏1000公升汽油,卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油,即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车,合计5次。路途耗油亦应500公升,即d23=500/5,
Way[3]=Way[2]+d23=Way[2]+500/5;
此时的状况如图21所示。
依次类推,为了在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公升,即dk,k+1=500/(2k-1),
No. Distance(k.m.) Oil(litre)
1 × × × ×
2 × × × ×
… … … … …分析:
设Way[I]——第I个贮油点到终点(I=0)的距离;
oil[I]——第I个贮油点的贮油量;
我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。
从贮油点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处,这就是说
Way[I]=500;oil[I]=500;
为了在I=1处贮藏500公升汽油,卡车至少从I=2处开两趟满载油的车至I=1处,所以I=2处至少贮有2*500公升汽油,即oil[2]=500*2=1000;另外,再加上从I=1返回至I=2处的一趟空载,合计往返3次。三次往返路程的耗油量按最省要求只能为500公升,即d12=500/3km,Way[2]=Way[1]+d12=Way[I]+500/3
此时的状况如图20所示。
为了在I=2处贮藏1000公升汽油,卡车至少从I=3处开三趟满载油的车至I=2处。所以I=3处至少贮有3*500公升汽油,即oil[3]=500*3=1500。加上I=2至I=3处的二趟返程空车,合计5次。路途耗油亦应500公升,即d23=500/5,
Way[3]=Way[2]+d23=Way[2]+500/5;
此时的状况如图21所示。
依次类推,为了在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公升,即dk,k+1=500/(2k-1),
#define MAX_STATION_NUM 32 /*定义最大允许的储油点数目*/
void main()
{
int k,i;
float wDistance; /*wDistance是终点至当前贮油点的距离*/
float storedOil[MAX_STATION_NUM];/*storedOil[i]是第i个储油点的储油量*/
float distance[MAX_STATION_NUM]; /*distance[i]是第i个储油点到终点的距离*/
clrscr();
puts("***********************************************");
puts("* this program will solve *");
puts("* the problem about storing oil *");
puts("***********************************************");
puts("The whole distance is 1000km,and the result is:\n");
puts("station distance(km) oil(l)");
k=1;
wDistance=500; /*从i=1处开始向始点倒推*/
distance[1]=500;
storedOil[1]=500;
while(1)
{
k++;
wDistance+=500/(2*k-1);
distance[k]=wDistance;
storedOil[k]=storedOil[k-1]+500;
if(wDistance>=1000)
break;
}
distance[k]=1000; /*置始点至终点的距离值*/
storedOil[k]=(1000-distance[k-1])*(2*k+1)+storedOil[k-1]; /*求始点藏油量*/
for(i=0;i<k;i++) /*由始点开始逐一打印始点至当前贮油点的距离和藏油量*/
printf("%4d %6.3f %6.3f\n",i,1000-distance[k-i],storedOil[k-i]);
getch();
}