汽车加油问题实验报告图文稿.docx

集团文件版本号：（M928-T898-M248-WU2669-I2896-DQ586-M1988）
汽车加油问题实验报告
#include<>
intadd_station(int n,in
由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。
,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。
加油站贪心算法设计（C）：
include<>
include<>
int add(int b[ ],int m,int n)
{ //求一个从m到n的数列的和
int sb;
for(int i=m;i<n;i++) sb+=b[i];
return sb;
}
int Tanxin(int a[n], int N) //a[n]表示加油站的个数，N为加满油能行驶的最远距离
{
int b[n]; //若在a[i]加油站加油，则b[i]为1，否则为0
int m=0;
if(a[i]>N) return ERROR; //如果某相邻的两个加油站间的距离大于N，则不能到达终点
if(add(a[i], 0, n)<N)
{ //如果这段距离小于N，则不需要加油
b[i]=0;
return add(b[i],0,n);
}
if(a[i]==a[j]&&a[i]==N)
{ //如果每相邻的两个加油站间的距离都是N，则每个加油站都需要加油
b[i]=1;
return add(b[i],0,n);
}
if(a[i]==a[j]&&a[i]<N)
{ //如果每相邻的两个加油站间的距离相等且都小于N
if( add(a[i],m,k) < N && add(a[i],m,k+1) > N )
{
b[k]=1;
m+=k;
}
return add(b[i],0,n);
}
if(a[i]!=a[j])
{ //如果每相邻的两个加油站间的距离不相等且都小于N
if( add(a[i],m,k) < N && add(a[i],m,k+1) > N )
{
b[k]=1;
m+=k;
}
return add(b[i],0,n);
}
viod main( )
{
int a[ ];
scanf("%d",a);
scanf("/n");
scanf("/d",&N);
Tanxin(a[ ],0,n);
}
贪心算法正确性证明：
贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，如图：
由图知：因为m+N<n+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。
最优子结构性质：
当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于（b[1],b[2],……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1,则（b[2],b[3],……b[n]）是从 a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2],a[3],……a[n]）的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。
贪心算法时间复杂度分析
由于若