2011年计算机等级考试二级C辅导实例编程(2)

会计考友

　　汽车加油问题之贪心算法
　　(一) 问题描述
　　一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。
+ Q- V8 Y6 P' @% f- C4 U　　给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。
% ~( Q: h+ \+ c& `1 K+ Q8 @　　(二) 问题分析(前提行驶前车里加满油)
　　对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a;i=0，1，2，3……n
　　1.始点到终点的距离小于N，则加油次数k=0;
　　2.始点到终点的距离大于N，
　　A 加油站间的距离相等，即a=a[j]=L=N，则加油次数最少k=n;
　　B 加油站间的距离相等，即a=a[j]=L>N，则不可能到达终点;
# J+ O- a" S6 u0 a2 b: n. i8 C/ I
& o# w7 c4 Z$ }　　C 加油站间的距离相等，即a=a[j]=L

会计考友

　[问题分析]　　由于汽车是由始向终点方向开的,我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。
! m, w! z) P6 m) S9 r　　提出问题是解决的开始.为了着手解决遇到的困难,取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。却每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。
　　加油站贪心算法设计(C)：
# ~$ [2 P- ]" P/ J$ E6 \　　include
　　include
, Q& n9 x' h1 m5 J: Q　　int add(int b[ ],int m,int n)
　　{ //求一个从m到n的数列的和
　　int sb;
5 r* \0 L2 k  L! G; A+ r& s　　for(int i=m;iN) return ERROR; //如果某相邻的两个加油站间的距离大于N，则不能到达终点
0 c7 ?( @  o, P( N# x" ]
% o6 B' Q% Q. u2 W3 z6 ?/ E4 p　　if(add(a, 0, n)

会计考友

　}　　if(a!=a[j])
6 M! ?% p  s" C2 T, [　　{ //如果每相邻的两个加油站间的距离不相等且都小于N
　　if( add(a,m,k) < N && add(a,m,k+1) > N )
　　{
　　b[k]=1;
　　m+=k;
　　}
/ m* f; ?) Q. V2 o. O* t　　return add(b,0,n);
% b0 ^/ P  ?8 E9 Y2 D　　}
; x' Y% }4 e  q5 o1 j　　viod main( )
: g  ~8 N+ e; s$ W/ V　　{
& H6 e2 h  r" j　　int a[ ];
$ I8 t9 e" h# \　　scanf("%d",a);
　　scanf("/n");
/ t3 @$ Q, l5 s/ F' j　　scanf("/d",&N);
# K" i+ x! C! f* H　　Tanxin(a[ ],0,n);
　　}
" r$ }. ^6 D3 W7 \# `3 T2 U9 x- `$ r　　贪心算法正确性证明：
　　贪心选择性质

+ h! P# Y! g( \* k! u7 z# J; |　　所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体的问题，要确定它是否具有贪心性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。该题设在加满油后可行驶的N千米这段路程上任取两个加油站A、B，且A距离始点比B距离始点近，则若在B加油不能到达终点那么在A加油一定不能到达终点，因为m+N