文档介绍：汽车加油问题之贪心算法
问题描述
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。
给出N,并以数组的形式给出加油站的汽车加油问题之贪心算法
问题描述
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。
给出N,并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次
数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快
越好。
问题分析（前提行驶前车里加满油）
对于这个问题我们有以下几种情况：设加油次数为
k,每个加油站间距离为a[i];
i=0,1,2,3……n
1.
始点到终点的距离小于N,则加油次数 k=0;
2.
始点到终点的距离大于 N，
力口油站间的距离相等，即a
[i]=a[j]=L=N
k=n；
力口油站间的距离相等，即a
[i]=a[j]=L>N
,则不可能到达终点;
力口油站间的距离相等，即a
[i]=a[j]=L<N
k=n/N(n%N==0) 或
k=[n/N]+1(n%N！=0)；
D 力口油站间的距离不相等，即a
[i] ！ =a[j]
k 通过以下算法求解。
（三）算法描述
贪心算法的基本思想
该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每个步
骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优
解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目
标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个
最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题，并期望做
出的局部最优的选择产生一个全局得最优解。
贪心算法的适用的问题
贪心算法适用的问题必须满足两个属性：
贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选
择可以依赖以前做出的选择，但不能依赖于以后的选择。
最优子结构：问题的整体最优解包含着它的子问题的最优解。
贪心算法的基本步骤
(1)分解：将原问题分解为若干相互独立的阶段。
(2)解决：对于每一个阶段求局部的最优解。
合并：将各个阶段的解合并为原问题的解。
[问题分析]
由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可
以使我们既可以到达终点又可以使我们加油次数最少。
,取得最优方案。我们可以假设不
到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。
在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法
进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。
加油站贪心算法设计(C)：
include<>
include<>
intadd(intb[],intm,intn)
{//求一个从m到n的数列的和
intsb;
for