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

　　}

　　if(a[i]!=a[j])

　　{ //如果每相邻的两个加油站间的距离不相等且都小于N

　　if( add(a[i],m,k) < N && add(a[i],m,k+1) > N )

　　{

　　b[k]=1;

　　m+=k;

　　}

　　return add(b[i],0,n);

　　}

　　viod main( )

　　{

　　int a[ ];

　　scanf("%d",a);

　　scanf("/n");

　　scanf("/d",&N);

　　Tanxin(a[ ],0,n);

　　}

　　贪心算法正确性证明：

　　贪心选择性质

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

　　最优子结构性质：

　　当一个问题大的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。由于(b[1],b[2],……b[n])是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1,则(b[2],b[3],……b[n])是从 a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为(a[2],a[3],……a[n])的最优解,即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。

　　贪心算法时间复杂度分析

　　由于若想知道该在哪个加油站加油就必须遍历所有的加油站，且不需要重复遍历，所以时间复杂度为O(n)。

　　2011计算机等级二级C语言五套模拟试题及答案

　　计算机等级考试二级C语言历年真题汇总(2005-2010)

　　2011年计算机等级考试二级C语言常见问题汇总

　　计算机等级考试二级C语言常见知识点总结