汽车加油问题试验报告

1、一、实验名称 ：用贪心算法解决汽车加油次数最少问题。二、实验目的：一辆汽车加满油后 ,可行使 n 千米。旅途中有若干个加油站。 若要使沿途加油次数最少，设计一个有效算法，对于给定的n和k个加油 站位置，指出应在哪些加油站停靠加油才能使加油次数最少。输入数据 中，第一行有 2 个正整数，分别表示汽车加满油后可行驶 n 千米，且旅 途中有 k 个加油站。接下来的 1 行中，有 k+1 个整数，表示第 k 个加油 站与第 k-1 个加油站之间的距离。第 0 个加油站表示出发地，汽车已加 满油。第 k+1 个加油站表示目的地。输出为最少的加油次数，如果无法 到达目的地，则输出“ No Solution

2、 ”。实验提示：把两加油站的距离放在数组中， a1.k 表示从起始位置开始跑， 经 过k个加油站，ai表示第i 1个加油站到第i个加油站的距离。汽车 在运行的过程中如果能跑到下一个站则不加油，否则要加油。输入数据示例7 71 2 3 4 5 1 6 6输出数据4三、使用的策略：贪心算法、回溯算法等。四、实验内容：（一）问题描述一辆汽车加满油后可以行驶 N千米。旅途中有若干个加油站。指出若要使沿 途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加0 1 2油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油

3、。要求：算法执 行的速度越快越好。（二）问题分析（前提行驶前车里加满油）对于这个问题我们有以下几种情况：设加油次数为k,每个加油站间距离为 ai;i=0 , 1 , 2 , 3n1始点到终点的距离小于N,则加油次数k=0 ；2始点到终点的距离大于 N ,i=aj=L=N，则加油次数最少 k=n ;i=aj=L>N，则不可能到达终点;i=aj=L<N，则加油次数 k= n/N（n%N=O）i! =aj，则加油次数 k通过以下算法求A力啪站间的距离相等，即aB力啪站间的距离相等，即aC力啪站间的距离相等，即a或 k=n/N+1（n%N ! =0）;D力啪站间的距离不相等，即 解。（三）

4、算法描述1.贪心算法解决方案贪心算法的基本思想该题目求加油最少次数，即求最优解的问题，可分成几个步骤，一般来说，每 个步骤的最优解不一定是整个问题的最优解，然而对于有些问题，局部贪心可以得到全局的最优解。贪心算法将问题的求解过程看作是一系列选择，从问题的某一个初始解出发，向给定目标推进。推进的每一阶段不是依据某一个固定的递推式，而是在每一个阶段都看上去是一个最优的决策（在一定的标准下）。不断地将问题实 例归纳为更小的相似的子问题，并期望做出的局部最优的选择产生一个全局得最优 解。贪心算法的适用的问题贪心算法适用的问题必须满足两个属性：（1）贪心性质：整体的最优解可通过一系列局部最优解达到，并且

5、每次的 选择可以依赖以前做出的选择，但不能依赖于以后的选择。（2）最优子结构：问题的整体最优解包含着它的子问题的最优解。贪心算法的基本步骤(1)分解：将原问题分解为若干相互独立的阶段。(2)解决：对于每一个阶段求局部的最优解。(3)合并：将各个阶段的解合并为原问题的解。 问题分析 由于汽车是由始向终点方向开的 , 我们最大的麻烦就是不知道在哪个加油站加 油可以使我们既可以到达终点又可以使我们加油次数最少。提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油， 即除非我们油箱里的油不足以开到下一个加油站， 我 们才加一次油。 在局部找到一个最优的解。 却

6、每加一次油我们可以看作是一个新的 起点， 用相同的递归方法进行下去。 最终将各个阶段的最优解合并为原问题的解得 到我们原问题的求解。加油站贪心算法设计( C )：include<math.h>include<studio.h>int add(int b ,int m,int n) /求一个从 m 到 n 的数列的和int sb;for(int i=m;i<n;i+) sb+=bi;return sb;int Tanxin(int an, int N) /an 表示加油站的个数， N 为加满油能行驶的最远 距离int bn;若在ai加油站加油，则 bi为1，否则为0

7、int m=0;if(ai>N) return ERROR;/如果某相邻的两个加油站间的距离大于N,则不能到达终点if(add(ai, 0, n)<N) /如果这段距离小于N,则不需要加油bi=0;return add(bi,0,n);if(ai=aj&&ai=N) /如果每相邻的两个加油站间的距离都是N ，则每个加油站都需要加油bi=1;return add(bi,0,n);if(ai=aj&&ai<N) / 如果每相邻的两个加油站间的距离相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+

8、1) > N )bk=1;m+=k;return add(bi,0,n);if(ai!=aj) / 如果每相邻的两个加油站间的距离不相等且都小于Nif( add(ai,m,k) < N && add(ai,m,k+1) > N )bk=1;m+=k;return add(bi,0,n);viod main( )int a ;scanf("%d",a);scanf("/n");scanf("/d",&N);Tanxin(a ,0,n);贪心算法正确性证明：贪心选择性质所谓贪心选择性质是指所求问题

9、的整体最优解可以通过一系列局部最优的选 择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的 N千米这段路程上任取两个加油站A、E，且A距离始点比E距离始 点近，则若在E加油不能到达终点那么在A加油一定不能到达终点，如图：由图知：因为m+N<n+N ,即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。最优子结构性质：当一个

10、问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于(b1,b2,bn)是这段路程加油次数最少的一个满足贪心选择 性质的最优解，则易知若在第一个加油站加油时，b1=1,则(b2,b3,bn)是从a2到an这段路程上加油次数最少且这段路程上的加油站个数为 (a2,a3,an)的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站 时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。贪心算法时间复杂度分析由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为0( n)。五、实验心得：在贪心算法中，每次做出的选择仅在当前的状态下做出的最好的选择，即局部 最优选择。然后再去解做出这个选择后产生的相应的子问题。