汽车加油问题实验报告(共5页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
一、实验名称：
用贪心算法解决)
{ //求一个从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千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业