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);

　　}

　　貪心算法正確性證明：

　　貪心選擇性質

　　所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。對于一個具體的問題，要確定它是否具有貪心性質，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優(yōu)解。該題設在加滿油后可行駛的N千米這段路程上任取兩個加油站A、B，且A距離始點比B距離始點近，則若在B加油不能到達終點那么在A加油一定不能到達終點，因為m+N

　　最優(yōu)子結構性質：

　　當一個問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性質。由于(b[1],b[2],……b[n])是這段路程加油次數最少的一個滿足貪心選擇性質的最優(yōu)解，則易知若在第一個加油站加油時，b[1]=1,則(b[2],b[3],……b[n])是從 a[2]到a[n]這段路程上加油次數最少且這段路程上的加油站個數為(a[2],a[3],……a[n])的最優(yōu)解,即每次汽車中剩下的油不能在行駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當于與起點具有相同的條件，每個過程都是相同且獨立，也就是說加油次數最少具有最優(yōu)子結構性質。

　　貪心算法時間復雜度分析

　　由于若想知道該在哪個加油站加油就必須遍歷所有的加油站，且不需要重復遍歷，所以時間復雜度為O(n)。

　　2011計算機等級二級C語言五套模擬試題及答案

　　計算機等級考試二級C語言歷年真題匯總(2005-2010)

　　2011年計算機等級考試二級C語言常見問題匯總

　　計算機等級考試二級C語言常見知識點總結