第3篇 核心篇-貪婪算法

算法設(shè)計(jì)與分析

Design

and

AnalysisofComputerAlgorithms

第3篇核心篇貪婪算法貪婪算法（貪心法）的設(shè)計(jì)思想貪婪算法的求解過(guò)程貪婪算法的基本要素貪婪算法的應(yīng)用舉例教學(xué)內(nèi)容：貪婪算法的設(shè)計(jì)思想【基本思想】將問(wèn)題的求解過(guò)程看作是一系列選擇，每次選擇一個(gè)輸入，每次選擇都是當(dāng)前狀態(tài)下的最好選擇（局部最優(yōu)解），每作一次選擇后，所求問(wèn)題會(huì)簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，從而通過(guò)每一步的最優(yōu)解逐步達(dá)到整體的最優(yōu)解。

貪心法在解決問(wèn)題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（OptimalSolution），但通常能獲得近似最優(yōu)解（Near-OptimalSolution）。引例[找零錢(qián)]一個(gè)小孩買(mǎi)了價(jià)值少于1美元的糖，并將1美元的錢(qián)交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢(qián)數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：

每一次選擇應(yīng)使零錢(qián)數(shù)盡量增大。為保證解法的可行性（即：所給的零錢(qián)等于要找的零錢(qián)數(shù)），所選擇的硬幣不應(yīng)使零錢(qián)總數(shù)超過(guò)最終所需的數(shù)目。算法思想為使找回的零錢(qián)的硬幣數(shù)最小，不考慮找零錢(qián)的所有各種方案，而是從最大面值的幣種開(kāi)始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，只當(dāng)不足大面值幣種的金額才會(huì)去考慮下一種較小面值的幣種，這就是在采用貪婪法。這種方法在這里之所以總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類(lèi)和硬幣面值的巧妙安排。如果只有面值分別為1，5和11單位的硬幣，而希望找回總額為15單位的硬幣，按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。但最優(yōu)的解答應(yīng)是3個(gè)5單位面值的硬幣。幣種統(tǒng)計(jì)問(wèn)題【例】某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢(qián)，且取款的張數(shù)最少，去工資錢(qián)要統(tǒng)計(jì)所以職工的工資所需各種幣種（100,50,20,10,5,2,1共7種）的張數(shù)，請(qǐng)編程完成?！舅惴ㄔO(shè)計(jì)】1、為了保證不要臨時(shí)兌換零錢(qián)，且取款的張數(shù)最少，應(yīng)該對(duì)每一個(gè)人的工資，用“貪婪”的思想，先盡量多地取大面額的幣種，由大面額到小面額幣種逐步統(tǒng)計(jì)。2、利用數(shù)組應(yīng)用技巧，將7種幣值存儲(chǔ)在數(shù)組中，從大面額的幣種到小面額的幣種依次存儲(chǔ)。幣種統(tǒng)計(jì)問(wèn)題幣種統(tǒng)計(jì)問(wèn)題inti,j,n,GZ,A,B[7]={100,50,20,10,5,2,1}; staticintS[7]; cin>>n;//輸入人數(shù) for(i=0;i<n;i++) { cin>>GZ;//輸入每人的工資 for(j=0;j<7;j++) { A=GZ/B[j]; S[j]+=A; GZ=GZ-A*B[j]; } } for(i=0;i<7;i++) cout<<B[i]<<"-----"<<S[i]<<endl;//輸出每種幣種的張數(shù)2貪心法的求解過(guò)程

用貪心法求解問(wèn)題應(yīng)該考慮如下幾個(gè)方面：（1）候選集合C：為了構(gòu)造問(wèn)題的解決方案，有一個(gè)候選集合C作為問(wèn)題的可能解，即問(wèn)題的最終解均取自于候選集合C。例如，在付款問(wèn)題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著貪心選擇的進(jìn)行，解集合S不斷擴(kuò)展，直到構(gòu)成一個(gè)滿足問(wèn)題的完整解。例如，在付款問(wèn)題中，已付出的貨幣構(gòu)成解集合。

（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問(wèn)題的完整解。例如，在付款問(wèn)題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。

（4）選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個(gè)候選對(duì)象最有希望構(gòu)成問(wèn)題的解，選擇函數(shù)通常和目標(biāo)函數(shù)有關(guān)。例如，在付款問(wèn)題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個(gè)候選對(duì)象是否可行，即解集合擴(kuò)展后是否滿足約束條件。例如，在付款問(wèn)題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過(guò)應(yīng)付款。

貪心法的一般過(guò)程Greedy(C)//C是問(wèn)題的輸入集合即候選集合{S={};//初始解集合為空集while(notsolution(S))//集合S沒(méi)有構(gòu)成問(wèn)題的一個(gè)解{x=select(C);//在候選集合C中做貪心選擇iffeasible(S,x)//判斷集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}活動(dòng)安排問(wèn)題

活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源?；顒?dòng)安排問(wèn)題【例】設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間begin[i]和一個(gè)結(jié)束時(shí)間end[i],且begin[i]<end[i]。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間[begin[i],end[i])內(nèi)占用資源。若區(qū)間[begin[i],end[i])與區(qū)間[begin[j],end[j])不相交，則稱(chēng)活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)begin[i]≥end[j]或begin[j]≥end[i]時(shí)，活動(dòng)i與活動(dòng)j相容?！締?wèn)題】找出時(shí)間上不重疊的事件【算法設(shè)計(jì)思想】a和b活動(dòng)的開(kāi)始時(shí)刻小于結(jié)束時(shí)刻Begin[a]<End[a]Begin[b]<End[b]b活動(dòng)的開(kāi)始時(shí)刻大于等于a活動(dòng)的結(jié)束時(shí)刻,即Begin[b]>=End[a]記為b>a這時(shí)b活動(dòng)與a活動(dòng)不重疊,則選擇活動(dòng)b加入集合中，否則不選擇該活動(dòng)。活動(dòng)安排問(wèn)題【例】設(shè)待安排的12個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i01234567891011begin[i]130325641081515end[i]3478910121415181920constintN=12;voidGreedySelector(intBegin[],intEnd[],intSelect[]){ inti,j; Select[0]=1; j=0; for(i=1;i<N;i++) {

if(Begin[i]>=End[j]) { Select[i]=1; j=i; } else Select[i]=0; }}//輸出選擇的活動(dòng)voidOutputResult(intSelect[N]){ cout<<"{0";for(inti=1;i<N;i++)

if(Select[i]==1)

cout<<","<<i;cout<<"}"<<endl;}voidmain(){ intBegin[N]={1,3,0,3,2,5,6,4,10,8,15,15};//活動(dòng)的最早開(kāi)始時(shí)間intEnd[N]={3,4,7,8,9,10,12,14,15,18,19,20};//活動(dòng)的最早結(jié)束的事件 staticintSelect[N]; intTimeStart=0; GreedySelector(Begin,End,Select); OutputResult(Select);}運(yùn)行結(jié)果：3、貪心算法的基本要素 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。3貪心算法的基本要素【貪心選擇性質(zhì)】

所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。

【算法缺點(diǎn)】對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。3貪心算法的基本要素【最優(yōu)子結(jié)構(gòu)性質(zhì)】

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。0-1背包問(wèn)題：整數(shù)背包

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問(wèn)題(KnapsackProblem)背包問(wèn)題：分?jǐn)?shù)背包

與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。相同：這2類(lèi)問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。區(qū)別：背包問(wèn)題具有貪心選擇性質(zhì)，而0-1背包問(wèn)題卻不具有貪心選擇性質(zhì)，不能用貪心算法求解。背包問(wèn)題(KnapsackProblem)24背包問(wèn)題(KnapsackProblem)【問(wèn)題描述】已知有n種物品和一個(gè)可容納W重量的背包，每種物品I的重量為wi，假定將物品I的某一部分xi放入背包就會(huì)得到pixi的效益(0≤xi≤1,pi>0)，采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益為最大呢？【問(wèn)題的形式描述】極大化： ∑pixi

約束條件：∑wixi≤W

0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n解的意義:xi表示物品i裝入背包的部分占該物品全部的比例（1）選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（2）選擇重量最輕的物品，因?yàn)檫@可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒(méi)能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。（3）選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。至少有三種看似合理的貪心策略：背包問(wèn)題(KnapsackProblem)背包問(wèn)題(KnapsackProblem)方案1：按物品價(jià)值降序裝包方案2：按物品重量升序裝包方案3：按物品價(jià)值與重量比值的降序裝包

應(yīng)用第三種貪心策略，每次從物品集合中選擇單位重量?jī)r(jià)值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個(gè)最優(yōu)子問(wèn)題——它同樣是背包問(wèn)題，只不過(guò)背包容量減少了，物品集合減少了。因此背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

背包問(wèn)題(KnapsackProblem)

首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 用貪心算法解背包問(wèn)題的基本步驟：3貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//改變數(shù)組w和v的排列順序，使其按單位重量?jī)r(jià)值v[i]/w[i]降序排列inti;for(i=1;i<=n;i++)x[i]=0;////初始化解向量floatc=M;//背包剩余容量for(i=1;i<=n;i++){if(w[i]>c)break;//當(dāng)該物品重量大于剩余容量跳出x[i]=1;c-=w[i];//確定背包新的剩余容量}if(i<=n)x[i]=c/w[i];}//選擇物品的一部分將背包填滿3貪心算法的基本要素算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)。

對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。3貪心算法的基本要素應(yīng)用--貨箱裝船

貨箱裝船問(wèn)題：設(shè)有編號(hào)為0…n-1的n種物品，重量分別為w0…wn-1，船載重為c，如何裝載，使船可以裝載更多的貨箱。1、算法設(shè)計(jì)采用貪婪算法船可以分步裝載，每步裝一個(gè)貨箱，且需要考慮裝載哪一個(gè)貨箱。根據(jù)這種思想可利用如下貪婪準(zhǔn)則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。貨箱裝船#include<iostream.h>voidIndirectSort(intw[],intt[],intn){//Clugetotestwhenweightsalreadyinorder.for(inti=1;i<=n;i++)t[i]=i;}template<classT>voidContainerLoading(intx[],Tw[],Tc,intn){//Greedyalgorithmforcontainerloading.//Setx[i]=1iffcontaineri,1<=i<=nisloaded.//cisshipcapacity,wgivescontainerweights.//doindirectaddressingsortofweights

//tistheindirectaddressingtable

貨箱裝船

int*t=newint[n+1];IndirectSort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;//selectobjectsinorderofweightfor(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}//remainingcapacitydelete[]t;}貨箱裝船voidmain(void){intw[13]={0,20,50,50,80,90,100,150,200},x[13];ContainerLoading(x,w,400,8);cout<<"Loadingvectoris"<<endl;for(inti=1;i<=8;i++)cout<<x[i]<<'';cout<<endl;}2、貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法ContainerLoading的正確性。 算法ContainerLoading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

多機(jī)調(diào)度問(wèn)題【多機(jī)調(diào)度問(wèn)題】設(shè)有

n個(gè)獨(dú)立的作業(yè){1,2,..,n}，由m

臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti

。現(xiàn)約定，任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理，任何作業(yè)不能拆分成更小的作業(yè)。要求：給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。

多機(jī)調(diào)度問(wèn)題

【分析】：這個(gè)問(wèn)題是一個(gè)NP完全問(wèn)題（(Non-deterministicPolynomial)，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題），到目前為止還沒(méi)有一個(gè)有效的解法。對(duì)于這一類(lèi)問(wèn)題，用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。

按此策略，當(dāng)n<=m時(shí)，只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可。

當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。多機(jī)調(diào)度問(wèn)題

【例如】設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺(tái)機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。用貪心選擇策略產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時(shí)間為17。

【問(wèn)題描述】

鍵盤(pán)輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。輸入數(shù)據(jù)均不需判錯(cuò),輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)。

刪數(shù)游戲【算法分析】這是一道運(yùn)用貪心策略求解的典型問(wèn)題。在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)此貪婪策略就可以解決這個(gè)問(wèn)題。怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標(biāo)是刪除高位較大的數(shù)字，具體地相鄰兩位比較若高位比低位大則刪除高位。每次刪除一個(gè)數(shù)字,選擇一個(gè)使剩下的數(shù)最小的數(shù)字作為刪除對(duì)象,之所以選擇這樣”貪心”的操作,是因?yàn)閯hS個(gè)數(shù)字的全局最優(yōu)解包含了刪一個(gè)數(shù)字的子問(wèn)題的最優(yōu)解。

刪數(shù)游戲【例如】N=175438,S=4;可以刪去7,5,4,8,得到13。刪除S次，每次刪的數(shù)要使剩下的數(shù)盡量小。例如上面的例子，第一次刪7,至少比第一次刪1,5,4,3,8好！

這樣，刪數(shù)過(guò)程是：175438

15438

1438

138

13【算法思想】從左向右找到第一個(gè)i,使n[i]>n[i+1]，如果找到了，就刪除第i個(gè)數(shù)字，否則刪除刪除了若干個(gè)最右邊的大數(shù)字。

刪數(shù)游戲當(dāng)S=1時(shí),在N中刪除哪一個(gè)數(shù)字能達(dá)到最小的目的?從左到右每相鄰的兩個(gè)數(shù)字比較:若出現(xiàn)左邊大于右邊,則刪除左邊的大數(shù)字.若不出現(xiàn)降序排列,即所有數(shù)字全部升序,則刪除最右邊的大數(shù)字.當(dāng)S>1,按上述操作一個(gè)一個(gè)刪除,刪除一個(gè)達(dá)到最小后,再?gòu)念^即從串首開(kāi)始,刪除第2個(gè),依次分解為S次完成.若刪除不到S個(gè)后已無(wú)左邊大于右邊的減序,則停止刪除操作,打印剩下串的左邊L-S個(gè)數(shù)字即可(相當(dāng)于刪除了若干個(gè)最右邊的大數(shù)字,這里L(fēng)為原數(shù)字N的位數(shù)).

刪數(shù)游戲#include<iostream>#include<string>usingnamespacestd;intmain(){ stringn;//利用字符串?dāng)?shù)組保存高精度數(shù)字 ints,i,x,m,l;cout<<"inputdataanddeletedatalength:"; cin>>n>>s; i=-1; m=0; x=0;//x統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù) l=n.length(); while(x<s&&m==0) { i++; if(n[i]>n[i+1])//出現(xiàn)遞減,刪除遞減的首數(shù)字 {n=n.erase(i,1); x++; i=-1;//從頭開(kāi)始查遞減區(qū)間 } if(i==1-x-2&&x<s) m=1;//已經(jīng)無(wú)遞減區(qū)間,循環(huán)結(jié)束 }

if(x<s)cout<<n.substr(0,l-s+x);//只打印剩下的左邊l-(s-x)個(gè)數(shù)字elsecout<<n<<endl;return0;}運(yùn)行結(jié)果：設(shè)計(jì)一個(gè)算法，把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的形式?！締?wèn)題分析】

所謂埃及分?jǐn)?shù)，是指分子為1的形式。古代埃及有一個(gè)非常奇怪的習(xí)慣，他們喜歡把一個(gè)分?jǐn)?shù)表示為若干個(gè)分子為1的分?jǐn)?shù)之和的形式。如：7/8=1/2+1/3+1/24

埃及分?jǐn)?shù)【算法思想】逐步選擇分?jǐn)?shù)所包含的最大埃及分?jǐn)?shù)，這些埃及分?jǐn)?shù)之和就是問(wèn)題的一個(gè)解。數(shù)學(xué)家斐波那契提出的一種求解埃及分?jǐn)?shù)的貪心算法，基本思想是：

(1)設(shè)某個(gè)真分?jǐn)?shù)