汽车加油问题之贪心算法计算机等级考试

文章作者 100test 发表时间 2010:01:02 07:00:15
来源 100Test.Com百考试题网

　　（一） 问题描述

　　一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。

　　给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。

　　（二） 问题分析（前提行驶前车里加满油）

　　对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n

　　1.始点到终点的距离小于Ｎ，则加油次数k=0；

　　2.始点到终点的距离大于N，

　　A　加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；

　　B　加油站间的距离相等，即ａ[i]=a[j]=L