}

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

　　{ //如果每相鄰的兩個(gè)加油站間的距離不相等且都小于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);

　　}

　　貪心算法正確性證明：

　　貪心選擇性質(zhì)

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

　　最優(yōu)子結(jié)構(gòu)性質(zhì)：

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

　　貪心算法時(shí)間復(fù)雜度分析

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

　　2011計(jì)算機(jī)等級(jí)二級(jí)C語(yǔ)言五套模擬試題及答案

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言歷年真題匯總(2005-2010)

　　2011年計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見(jiàn)問(wèn)題匯總

　　計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常見(jiàn)知識(shí)點(diǎn)總結(jié)