文档介绍：一、实验名称:用贪心算法解决汽车加油次数最少问题。二、实验目的:一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,对于给定的n和k个加油站位置,指出应在哪些加油站停靠加油才能使加油次数最少。输入数据中,第一行有2个正整数,分别表示汽车加满油后可行驶n千米,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出为最少的加油次数,如果无法到达目的地,则输出“NoSolution”。实验提示:把两加油站的距离放在数组中,a[1..k]表示从起始位置开始跑,经过k个加油站,a[i]表示第i-1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油,否则要加油。输入数据示例7712345166输出数据4。三、使用的策略:贪心算法、回溯算法等。四、实验内容:(一)问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。给出N,并以数组的形式给出加油站的个数及相邻距离,指出若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。要求:算法执行的速度越快越好。(二)问题分析(前提行驶前车里加满油)对于这个问题我们有以下几种情况:设加油次数为k,每个加油站间距离为a[i];i=0,1,2,3……,则加油次数k=0;,A加油站间的距离相等,即a[i]=a[j]=L=N,则加油次数最少k=n;B加油站间的距离相等,即a[i]=a[j]=L>N,则不可能到达终点;C加油站间的距离相等,即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通过以下算法求解。(三),即求最优解的问题,可分成几个步骤,一般来说,每个步骤的最优解不一定是整个问题的最优解,然而对于有些问题,局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择,从问题的某一个初始解出发,向给定目标推进。推进的每一阶段不是依据某一个固定的递推式,而是在每一个阶段都看上去是一个最优的决策(在一定的标准下)。不断地将问题实例归纳为更小的相似的子问题,并期望做出的局部最优的选择产生一个全局得最优解。贪心算法的适用的问题贪心算法适用的问题必须满足两个属性:贪心性质:整体的最优解可通过一系列局部最优解达到,并且每次的选择可以依赖以前做出的选择,但不能依赖于以后的选择。最优子结构:问题的整体最优解包含着它的子问题的最优解。贪心算法的基本步骤分解:将原问题分解为若干相互独立的阶段。解决:对于每一个阶段求局部的最优解。合并:将各个阶段的解合并为原问题的解。[问题分析]由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。,取得最优方案。我们可以假设不到万不得已我们不加油,即除非我们油箱里的油不足以开到下一