第三次課貪心算法

第三次課貪心算法第一頁，共七十三頁，編輯于2023年，星期四第3章內(nèi)容提綱3.1貪心算法的基本思想3.2刪數(shù)問題3.3裝箱問題第二頁，共七十三頁，編輯于2023年，星期四 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。第三頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題

活動(dòng)安排問題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。第四頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題設(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í)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。第五頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面給出解活動(dòng)安排問題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

第六頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題 由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。

第七頁，共七十三頁，編輯于2023年，星期四算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。第八頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題

例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314第九頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題

算法greedySelector的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。第十頁，共七十三頁，編輯于2023年，星期四活動(dòng)安排問題若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。第十一頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

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

對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。第十三頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素

當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、最優(yōu)子結(jié)構(gòu)性質(zhì)第十四頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異第十五頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素0-1背包問題：

給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。第十六頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

第十七頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素

首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：第十八頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。第十九頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 對(duì)于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。第二十頁，共七十三頁，編輯于2023年，星期四3.2刪數(shù)問題 給定一個(gè)高精度的正整數(shù)N（不超過240位），去掉任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(shù)。編程對(duì)于給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小示例：

N=178543，S=4

則結(jié)果為：13第二十一頁，共七十三頁，編輯于2023年，星期四算法分析N的存儲(chǔ)只能采用數(shù)組，可選擇字符數(shù)組；可采用貪心算法，即：共刪掉S個(gè)數(shù)，每一步刪掉一個(gè)數(shù)，并且總選擇一個(gè)使剩下的數(shù)最小的數(shù)符刪去。為了保證刪1個(gè)數(shù)符后的數(shù)最小，可以按照從高位到低位的方向收縮遞減區(qū)間，如果不存在遞減區(qū)間則刪尾數(shù)符；否則刪掉遞減區(qū)間的首字符，這樣形成一個(gè)新的數(shù)串。然后回到串首，重復(fù)上面的規(guī)則，刪下一個(gè)數(shù)符，。。。，直至刪除S個(gè)數(shù)符為止。第二十二頁，共七十三頁，編輯于2023年，星期四17854317543154314313第二十三頁，共七十三頁，編輯于2023年，星期四17853417534153413413第二十四頁，共七十三頁，編輯于2023年，星期四程序#include<iostream.h>#include<math.h>usingnamespacestd;ints;classnode{public: charc; node*next;};classquee{public: node*first;};第二十五頁，共七十三頁，編輯于2023年，星期四quee*init(){ charstr[250];quee*n;node*tmp;node*tail; n=newquee;n->first=NULL;cin>>str;cin>>s;inti=0; while(str[i]!='\0') { tmp=newnode; tmp->c=str[i];tmp->next=NULL; if(n->first==NULL) { n->first=tmp;tail=tmp; } else { tail->next=tmp;tail=tmp; } i++; } returnn;};第二十六頁，共七十三頁，編輯于2023年，星期四voiddel(quee*start,node*p){ node*x; x=start->first; if(x->next) { while(x->next!=p)x=x->next; } x->next=p->next; deletep;};第二十七頁，共七十三頁，編輯于2023年，星期四voidprint(quee*start){ node*tmp; if(start->first==NULL)return; tmp=start->first; while(tmp) { printf("%c",tmp->c); tmp=tmp->next; } printf("\n");};第二十八頁，共七十三頁，編輯于2023年，星期四node*find(quee*start){ node*tmp; tmp=start->first; while(tmp->next!=NULL&&tmp->c<=tmp->next->c) tmp=tmp->next; returntmp;};第二十九頁，共七十三頁，編輯于2023年，星期四intmain(intargc,char*argv[]){ quee*n; node*p; n=init(); while(s!=0) { p=find(n); del(n,p); s--; } print(n); return0;}第三十頁，共七十三頁，編輯于2023年，星期四3.3POJ1017Packets第三十一頁，共七十三頁，編輯于2023年，星期四Packets題意已知：有6*6的大箱子和1*1，2*2，3*3，4*4，5*5，6*6的木塊(平面)問：給定各種木塊的數(shù)目，求最少需要多少個(gè)大箱子來裝？例如：輸入：004001-〉輸出2輸入：751000-〉輸出1第三十二頁，共七十三頁，編輯于2023年，星期四Packets解題思想：貪心準(zhǔn)則：先放大的，后放小的6*6的木塊每個(gè)占用一個(gè)箱子；5*5的木塊每個(gè)占用一個(gè)新箱子，余下11個(gè)1*1的空格；4*4的木塊每個(gè)占用一個(gè)新箱子，余下5個(gè)2*2的空格。4.3*3的木塊每4個(gè)占用新一個(gè)箱子，不足4個(gè)也占一個(gè)新箱子，分情況余下不同數(shù)目的空格；5.2*2的木塊先填空格，空格不足開新箱子，每9個(gè)2*2的木塊占一個(gè)新箱子；6.1*1的木塊先填空格，空格不足開新箱子，每36個(gè)占一個(gè)新箱子。第三十三頁，共七十三頁，編輯于2023年，星期四Packets假設(shè)6*6，5*5，4*4，3*3，2*2，1*1的箱子個(gè)數(shù)b6b5b4b3b2b1第三十四頁，共七十三頁，編輯于2023年，星期四Packets

4*4，5*5，6*6的塊單獨(dú)開新的箱子。每一個(gè)5*5的塊還能放下11個(gè)1*1的箱子。每一個(gè)4*4的塊還能放下5個(gè)2*2的箱子，或者放下20個(gè)1*1的箱子。4*4塊5*5塊6*6塊第三十五頁，共七十三頁，編輯于2023年，星期四

3*3的塊1-4塊占一個(gè)新箱子，一個(gè)箱子可放下4個(gè)3*3的塊。如果一個(gè)箱子放下了1個(gè)3*3的塊，則還可放下5個(gè)2*2的塊和7個(gè)1*1的塊?；蛘呖梢苑畔?7個(gè)1*1的塊。如果一個(gè)箱子放下了2個(gè)3*3的塊，則還可放下3個(gè)2*2的塊和6個(gè)1*1的塊?；蛘呖梢苑畔?8個(gè)1*1的塊。如果一個(gè)箱子放下了3個(gè)3*3的塊，則還可放下1個(gè)2*2的塊和5個(gè)1*1的塊?；蛘呖梢苑畔?個(gè)1*1的塊。第三十六頁，共七十三頁，編輯于2023年，星期四PacketsnTotal-箱子數(shù)1）先放好所有6*6,5*5,4*4和3*3的木塊

nTotal=b6+b5+b4+(b3+3)/44*4,5*5,6*6單獨(dú)開新的箱子

3*3每1-4個(gè)占一個(gè)新箱子2）再把2*2的塞到放有3*3木塊的箱子里 intContain2[4]={0,5,3,1}; Contain2[i]表示當(dāng)箱子里有i個(gè)3*3的木塊時(shí)，還能放下多少個(gè)2*2的木塊 3）考慮放有3*3的木塊的箱子在塞滿2*2的木后還能放多少個(gè)1*1的木塊： intContain1[4]={0,7,6,5};

Contain1[i]表示當(dāng)箱子里有i個(gè)3*3的木塊，并且還填滿了2*2的木塊后，還能放下多少個(gè)1*1的木塊。第三十七頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放1個(gè)3*3木塊，那么還能放5個(gè)2*2木塊,以及7個(gè)1*1木塊第三十八頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放2個(gè)3*3木塊，那么還能放3個(gè)2*2木塊,以及6個(gè)1*1木塊第三十九頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放3個(gè)3*3木塊，那么還能放1個(gè)2*2木塊,以及5個(gè)1*1木塊第四十頁，共七十三頁，編輯于2023年，星期四Packets 4)計(jì)算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2

c2=b4*5+Contain2[b3%4];留下多少空格能放1*1 c1=b5*11+Contain1[b3%4](能放2*2的地方暫不考慮放1*1，因?yàn)槿绻鹀2〉b2則多余的b2-c2個(gè)位置可以放4*(b2-c2)個(gè)1*1的箱子)第四十一頁，共七十三頁，編輯于2023年，星期四Packets

5)放2*2，如果不夠放，就開新箱子，放完2*2，計(jì)算還剩多少空格能放1*1。

if(b2<=c2) c1+=(c2-b2)*4; else{ nTotal+=(b2-c2)/9;//每個(gè)空箱子可以放9個(gè)2*2 intr2=(b2-c2)%9; if(r2){ nTotal++; c1+=36-r2*4; } }第四十二頁，共七十三頁，編輯于2023年，星期四

6)放1*1并輸出結(jié)果

if(b1>c1){ nTotal+=(b1-c1)/36; if((b1-c1)%36) nTotal++; } cout<<nTotal<<endl;Packets第四十三頁，共七十三頁，編輯于2023年，星期四#include<iostream.h>intContain1[4]={0,7,6,5};intContain2[4]={0,5,3,1};intnTotal;voidmain(){intb1,b2,b3,b4,b5,b6;for(;;){cin>>b1>>b2>>b3>>b4>>b5>>b6;if(b1==0&&b2==0&&b3==0&&b4==0&&b5==0&&b6==0) break; nTotal=b6+b5+b4+b3/4; if(b3%4)nTotal++; intc1; //當(dāng)前能放1*1木塊的空格數(shù)目

c1=b5*11; //每個(gè)放5*5的箱子，還能放11個(gè)1*1的木塊c1+=Contain1[b3%4]; //加上3*3箱子里能放的數(shù)目

intc2;//當(dāng)前能放2*2木塊的空格數(shù)目（先不考慮將1*1的木塊放在 //2*2的空格里）

c2=b4*5; //每個(gè)放5*4的箱子，還能放5個(gè)2*2的木塊

c2+=Contain2[b3%4]; //加上3*3箱子里能放的數(shù)目第四十四頁，共七十三頁，編輯于2023年，星期四

if(b2<=c2) c1+=(c2-b2)*4; else{ nTotal+=(b2-c2)/9;//每個(gè)空箱子可以放9個(gè)2*2 intr2=(b2-c2)%9; if(r2){ nTotal++; c1+=36-r2*4; } } if(b1>c1){ nTotal+=(b1-c1)/36; if((b1-c1)%36) nTotal++; } cout<<nTotal<<endl;}}第四十五頁，共七十三頁，編輯于2023年，星期四〖案例3〗水位為使房屋買主可以評(píng)估洪水保險(xiǎn)的開銷，一家真實(shí)的房地產(chǎn)公司提供了一種客戶端程序，此程序現(xiàn)實(shí)了可能被購(gòu)買得房屋所在地區(qū)以100平方米為單位的海拔高度。雨水、雪水和管道破裂流出的水將會(huì)匯聚到海拔最低，因?yàn)樗畷?huì)從高處流向低處。為簡(jiǎn)化問題，我們假設(shè)水沿著排水溝從高出流向低處，并且水不會(huì)被土地所吸收。第四十六頁，共七十三頁，編輯于2023年，星期四從天氣信息的檔案中，我們得知了一個(gè)區(qū)域的典型儲(chǔ)水量。作為預(yù)期的購(gòu)房者，我們希望知道低處積水后的水位，以及完全被淹沒在水中的面積占此地區(qū)的百分比(也就是，10平方米的海拔高度嚴(yán)格低于水平面)。你被要求寫一個(gè)程序來給出結(jié)果。第四十七頁，共七十三頁，編輯于2023年，星期四輸入數(shù)據(jù)輸入包括區(qū)域描述所構(gòu)成的一個(gè)序列。每個(gè)由一對(duì)整數(shù)m和n開始，每個(gè)都小于30，給定的區(qū)域都是100平方米。緊隨其后的是m行，每行n個(gè)整數(shù)，給出地區(qū)海平面，以主行序給出。高度的單位是米，分別用正數(shù)或者負(fù)數(shù)表明高于或低于海平面。每個(gè)區(qū)域最后一個(gè)值是一個(gè)整數(shù)，用以指出有多少立方米的水聚集到此區(qū)域。m和n為兩個(gè)0代表輸入結(jié)束。第四十八頁，共七十三頁，編輯于2023年，星期四輸出描述對(duì)每個(gè)區(qū)域，顯示區(qū)域編號(hào)(1,2,…)，水平面(以米為單位表示高于或低于海平面)以及此區(qū)域被水淹沒的面積，每個(gè)占一行。水位和被水淹沒面積的百分率顯示時(shí)保留2位小數(shù)每個(gè)區(qū)域輸出后跟一個(gè)空行。第四十九頁，共七十三頁，編輯于2023年，星期四樣例332537455112349483271000000Region1Waterlevelis46.67meters.66.67percentoftheregionisunderwater.第五十頁，共七十三頁，編輯于2023年，星期四解題思路由于題目中特別聲明水無論如何都會(huì)流到當(dāng)前水面最低的地方，使得問題一下子簡(jiǎn)化了。很容易想到以下貪心算法：（1）把每個(gè)格子的高度排序；（2）以低格子到高格子的順序填水，把水均勻的鋪在當(dāng)前的水面上，并不斷更新當(dāng)前水面面積，和剩余水量；（3）若剩余水量為0，輸出當(dāng)前水面高度和水面覆蓋率。第五十一頁，共七十三頁，編輯于2023年，星期四注意1．水面每達(dá)到一個(gè)格子的高度，水面的面積也要隨之?dāng)U大；2．高度有負(fù)值，水面的初始高度是最低格子的高度而不是0；3．考慮好若干個(gè)格子高度相等的情況；4．每個(gè)格子的面積是100；5．沒有水時(shí)，覆蓋率為0；6．水若剛好達(dá)到一個(gè)格子的高度，此格子不算被水覆蓋；7．水面達(dá)到最高格子后，要把剩下的水均勻的鋪在整個(gè)區(qū)域上；8．注意浮點(diǎn)數(shù)的計(jì)算誤差，因?yàn)檫@個(gè)原因大家在POJ上都沒有通過此題:-<第五十二頁，共七十三頁，編輯于2023年，星期四#include<stdio.h>#include<stdlib.h>inth[1000000];//保存每個(gè)格子的高度值，因不知m和n的范圍，故設(shè)的比較大intcmp(constvoid*a,constvoid*b){return*((int*)a)-*((int*)b);}第五十三頁，共七十三頁，編輯于2023年，星期四main(){intt,m,n,nn; doublex,hw;inti;t=0;第五十四頁，共七十三頁，編輯于2023年，星期四

while(1){//輸入

scanf("%d%d",&n,&m);if(n==0&&m==0)break; t++;nn=m*n;for(i=0;i<nn;i++){scanf("%d",&h[i]);}scanf("%lf",&x);//排序

qsort(h,nn,sizeof(int),cmp);第五十五頁，共七十三頁，編輯于2023年，星期四

i=0;hw=h[0];if(x>0){for(i=1;i<nn;i++){//在高度相等的情況下，擴(kuò)大水面面積

while(i<nn&&h[i]==h[i-1]){i++;}if(i==nn||x<=100*i*(h[i]-h[i-1]))break;//若剩

下的水不夠使水面達(dá)到下一格子的高度，退出

x-=i*(h[i]-h[i-1])*100;}hw=h[i-1];}第五十六頁，共七十三頁，編輯于2023年，星期四if(x>0){//若剩下水，就把它鋪在當(dāng)前的范圍上

while(i<nn&&h[i]==h[i-1]){i++;}hw+=x/i/100;}//輸出結(jié)果

printf("Region%d\n",t);printf("Waterlevelis%.2fmeters.\n",hw);printf("%.2fpercentoftheregionisunderwater.\n\n",i*100/double(nn));}}第五十七頁，共七十三頁，編輯于2023年，星期四〖案例4〗埃及分?jǐn)?shù)埃及同中國(guó)一樣，也是世界上文明的古國(guó)之一。古埃及人處理分?jǐn)?shù)與眾不同，他們一般只用分子為1的分?jǐn)?shù)，例如：用1／3＋1／15來表示2／5，用1／4＋1／7＋1／28表示3／7，等等。設(shè)計(jì)一個(gè)程序，把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的形式。第五十八頁，共七十三頁，編輯于2023年，星期四Input第一行:N表示有N組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)為一行包含a,b(0〈a〈b〈1000)。Output每組測(cè)試數(shù)據(jù)若干個(gè)數(shù)，自小到大排列，依次是單位分?jǐn)?shù)的分母。SampleInput11945SampleOutput5618第五十九頁，共七十三頁，編輯于2023年，星期四所謂埃及分?jǐn)?shù)，是指分子為1的形式。古代埃及有一個(gè)非常奇怪的習(xí)慣，他們喜歡把一個(gè)分?jǐn)?shù)表示為若干個(gè)分子為1的分?jǐn)?shù)之和的形式。如，7/8=1/2+1/3+1/24。下面介紹其中一種算法――貪心算法。貪心算法是由數(shù)學(xué)家菲波那契提出的，基本思想是：設(shè)某個(gè)真分?jǐn)?shù)的分子為A，分母為B；把B除以A的商的整數(shù)部分加1后的值作為埃及分?jǐn)?shù)的某一個(gè)分母；將A乘以C減去B作為新的A；將B乘以C作為新的B；如果A大于1且能整除B，則最后一個(gè)分母為B/A；如果A＝1，則最后一個(gè)分母為B；否則轉(zhuǎn)步驟（2）。如：7/8=1/2+1/3+1/24第六十頁，共七十三頁，編輯于2023年，星期四解題步驟：用變量A表示分子，變量B表示分母；C=B\A+1A=A*C-B,B=B*C打印1/C若A>1且B/A=B\A，則C=B/A若A＝1，則C=B,打印1/C轉(zhuǎn)步驟（2）。第六十一頁，共七十三頁，編輯于2023年，星期四#include<stdio.h>#include<stdlib.h>intnum;inta,b;intc;intzc(inta,intb){intxx;xx=b/a;if(xx*a==b)return1;return0;};第六十二頁，共七十三頁，編輯于2023年，星期四voidcalab(){while(1){c=(b/a)+1;a=a*c-b;b=b*c;printf("%d",c);if(a>1&&zc(a,b)){printf("%d\n",b/a);break;}elseif(a==1){