Question

讨教一个C++ 编程作业

.重型卡车穿越1000km的沙漠，汽车耗油为1升/公里，卡车总载油量为500升，显然卡车一次过不了沙漠，因此司机必须在沿途设立一些储油点，则司机应该如何建立储油点、储多少油才能使汽车以最少的汽油代价通过沙漠，请分析写出算法、通过程序计算出每个储油点的安排情况。

Answer 1

算法分析：
1：装满油，开到125公里处，储存250公升油，开回起点；
2：装满油，开到125公里处，取出125公升油，开到250公里处，储存250公升油，开回到125公里处，取出125公升油，开回起点；
3：装满油，开到125公里处，储存250公升油，开回起点；
4：装满油，开到125公里处，取出125公升油，开到250公里处，取出125公升油，开至375公里处，储存250公升油，开回到250公里处，取出125公升油，开回到125公里处，取出125公升油，开回起点；
5：装满油，开到125公里处，储存250公升油，开回起点；
6：装满油，开到125公里处，取出125公升油，开到250公里处，储存250公升油，开回到125公里处，取出125公升油，开回起点；
7：装满油，开到125公里处，储存250公升油，开回起点；
8：装满油，开到125公里处，取出125公升油，开到250公里处，取出125公升油，开至375公里处，取出125公升油，开到500公里处，储存250公升油，回到375公里处，取出125公升油，开回到250公里处，取出125公升油，开回到125公里处，取出125公升油，开回起点；
9：装满油，开到125公里处，储存250公升油，开回起点；
10：装满油，开到125公里处，取出125公升油，开到250公里处，储存250公升油，开回到125公里处，取出125公升油，开回起点；
11：装满油，开到250公里处，取出250公升油，开到500公里处，储存250公升油，开到终点。
全程总共用去11*500＝5500公升油。

125 250 375 500 …… 1000 （公里）
01 250 0 0 0
02 0 250 0 0
03 250 250 0 0
04 0 0 250 0
05 250 0 250 0
06 0 250 250 0
07 250 250 250 0
08 0 0 0 250
09 250 0 0 250
10 0 250 0 250
11
要运载油量的 1/2 到 总路程的 n/8 处，需要运 2^(n-1) 次。
设dis第i个贮油至终点（i=0）的距离
oil第i个贮油的存贮油量
我们可以用倒推法来解决该问题。从终点向始点倒推，逐一求出每个贮油点的位置以及油量。
终点 起点
|------- |-------- |--------- |
i=0 i=2 ...i=n
从贮油点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公升汽油，即oid[2]=500*2=1000。另外，再加上上i=1返回至i=2处的一趟空载，合计往返3次。3次路程的蚝油量按最省要求只能为500公升，即d12=500/3(如下图示）
dis[2]=dis[1]+d12=dis[1]+500/3
|<-500/3---> |
|<---------- |
|----------> |
|<---------- |
|----------- |----------- |--------------->
i=0 i=1 i=2
为了在i=2出贮存1000公升汽油，卡车至少从i=3处开3趟满载油的车至i=2出。所以i=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500.加上i=2至i=3处的两趟返程空车，合计5次。路途蚝油量也应500公升，即d23=500/5
dis[3]=dis[2]+d23=dis[2]+500/5
依次类推，为了在i=k-1出贮藏(k-1)*500公升汽油，卡车至少从i=K处开k趟满载车至i=k-1处，即oid[K]=(k-1)*500=oik[k-1]+500,加上从i=k返回i=k=1的k-1趟返程空间，合计2k-1。这2K-1次总耗油量按最省要求为500公升，即dk-1k=500/(2K-1)
dis[k]=dis[k-1]+dk-1k=dis[k-1]+500/(2K-1)
程序如下：
#include<iostream>
using namespace std;
int main()
{
int k; /*贮油点位置序号*/
float d,d1; /*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/
float oil[10],dis[10];
int i;
cout << "序号 距离（km） 油量（L）"<<endl;
k=1;
d=500; /*从i=1处开始向始点倒推*/
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]; /*求i=n处至始点的距离*/
oil[k]=d1*(2*k+1)+oil[k-1]; /*求始点藏油量*/
for(i=0;i<k;i++) /*由始点开始逐一打印始点至当前贮油点的距离和藏油量*/
cout << i <<" " << 1000-dis[k-i] <<" " <<oil[k-i] << endl;
}

结果就很明显了

Answer 2

没读懂。。

Answer 3

这个可以用贪心法 直接就可以算 - -

在500KM处设立一个站点 储油500升。。。然后直接就行了 - -

你这题目感觉应该没叙述清楚

Answer 4

沙漠不存在油的，所以题目表达的是汽车要自己运油存储下来才可以的。所以要经常往回跑运油