编程沙龙（20）
IT商界
参考题目：已知一辆汽车要从A地前往B地，而旅途中有M个加油站，已知这M个加油站分别到A地距离为S1、S2 ……Sm。该车加满油后可行驶N公里(可以确定该车一定能到达B地)，车从A地开车时已加满了油。设计一个程序，输入N以及S1、S2 ……Sm，输出该车应在哪些加油站停靠加油，使沿途加油次数最少。并证明该方法获得的是最优解。
我们这期的题目其实很简单，主要是考查朋友们理解和使用贪心算法的情况。当然也能用其他方法解决该题，有的朋友就使用了穷举法来解题，但在不要求获得全部最优解的情况下，贪心算法明显优于穷举法。参与答题活动的大多数朋友都能正确使用贪心算法解题，但完成题目要求的证明所用方法获得的是最优解的朋友就少得多了。
我们要求证明最优解，其实也就是要判断问题是否可用贪心算法来解的。这里我们先看看如何证明本题使用贪心算法获得的解是最优解。
首先能用贪心算法，题目就必须具有最优子结构性质。假设本题有一组解(I1、I2……IK)表示汽车依次在加油站I1、I2……IK停靠加油，并且加油次数最少，也就是K最小。容易看出，(I2、I3……IK)是当出发地是I1时的一个最优解，否则将导致I1、I2……IK不是原问题的最优解。
其次我们要判断问题是否具有贪心选择性质。假设采用每次加满油后使汽车行驶尽可能远的贪心算法得一个最优解是(I1、I2……IK)，如果汽车在加油站I1不停靠加油还可行驶至I1以后得加油站I1'再加油，则在I1'站停靠加油，其后再按最优解提供得停靠站加油，也能达到目的地，且停靠次数不会比原来的解次数多。因此满足贪心算法的选择性质。
下面是解决该题的算法描述和核心代码(C语言)，关于参数输入部分代码略。
void _ refuel (float s[],int m,int n)
{
int i,j,k;
for (i=m+1;i>0;i--)
{
if (i>1) s[i]=s[i]-s[i-1]; //将各加油站到A点的距离转为加油站之间的间距
if (s[i]>n) //如果两加油站的间距大于N，则汽车无法到终点
{
//错误处理略
}
}
j=s[1];
k=0;
//贪心算法核心
//从起点或上一个停靠加油站开始汽车距尽可能远的距离再停靠加油
for (int i=1;i<=m;i++)
{
j=j+s[i+1];
if (j>n)
{
k=k+1;
x[k]=i;
j=s[i+1];
}
}
}
本月获奖名单：湖南省东安一中 高二 280班 叶文
湖北省英山县电信局 郭鼎
他们将分别获得赛门特克公司提供的《诺顿网络安全特警2003简体中文版》正版软件一套。
幸运读者：
贵阳 周平、四川 李崇海、吉林 张中儒
他们分别可获得《VB6/.NET编程实例精选》一书。
本月题目源程序下载：http://paladin.nease.net/cpcw/refuel.zip