基礎(chǔ)班算法設(shè)計策略

1、第十四章 算法設(shè)計策略1第一節(jié)第二節(jié)第三節(jié)第四節(jié)歸納與遞推1分治法7枚舉算法12貪心算法16習(xí)題22習(xí)題解答24第十四章算法設(shè)計策略著明的計算機(jī)科學(xué)家（N.Wirth)教授提出“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，由此可以看出算法的重要性。本章將介紹一些程序設(shè)計中最常用的基本算法，并通過例題來加深讀者的理解。這些常用的基本算法是歸納和遞推、分治、枚舉、貪心等。第一節(jié) 歸納與遞推一、引例【引例】Hanoi 塔【問題描述】Hanoi 塔由 n 個大小不同的圓盤和 3 根木柱 1,2,3 組成。開始時，這 n 個圓盤由大到小依次套在 1 柱上，如圖 14-1 所示。圖 14-1現(xiàn)在要求用最少的移動次數(shù)把 1 柱

2、上 n 個圓盤按下述規(guī)則移到 3 柱上：(1)(2)(3)一次只能移一個圓盤；圓盤只能在 3 個柱上存放；在移動過程中，不允許大盤壓小盤。請編程輸出最少的移動次數(shù)?！据斎搿恳粋€整數(shù) n(圓盤的數(shù)目，n3121-2 ,1-3,2-3331-3 , 1-2 , 3-2 , 1-3 , 2-1,2-3,1-37三、遞推的應(yīng)用例 14-1 走樓梯【問題描述】樓梯有 N 階，上樓可以一步上一階，也可以一步上二階，還可以一步上三階。編程求出共有多少種不同的走法?！据斎搿?N【輸出】 不同走法的數(shù)目【輸入樣例】 4【輸出樣例】 7【分析】可以從簡單情況開始入手，如表 14-2 所示。表 14-2假設(shè) f(n

3、)表示上 n 階臺階的不同走法種數(shù)，從上面的簡單情況可以分析出f(n)= f(n-3)+f(n-2)+f(n-1)，下面驗證一下該規(guī)律的正確性。假設(shè)當(dāng)前在第 n 階，那么可以由那些臺階一步能到達(dá)第 N 階哪？n-1 階，n-2 階或者 n-3 階都可以。則到達(dá)第 n 階方法數(shù) f(n)，為登上 n-1 階的方法數(shù) f(n-1)，與登上 n-2 階的方法數(shù) f(n-2)，以及登上 n-3 階的方法數(shù) f(n-3)，三者的和。即 f(n)= f(n-3)+f(n-2)+f(n-1)。由此可以說明【參考程序】的假設(shè)是正確的。var n:eger;function f(n:eger): beginif

4、 n=1 then f:=1eger;else if n=2 then f:=2else if n=3 then f:=4else f:=f(n-3)+f(n-2)+f(n-1);end; beginread(n);wriend.n(f(n);例 14-2 騎士:（noip1997）【問題描述】設(shè)有一個 n*m 的棋盤(2=n=50,2=m0)and(j-dyk0)and(j-dykm+1)。以（n,m）為起點向左遞推，當(dāng)遞推到（i-dxk,j-dyk）的位置是（1，1）時，就找到了一條從（1，1）到（n,m）的路徑。用二維數(shù)組a 表示棋盤，設(shè)初始值an,m為（-1，-1），如果從(i,j)一

5、步能走到(n,m)，就將(n,m)存放在ai,j中。比如 a2,2中可以存放（4，1），表示從這個點可以到達(dá)坐標(biāo)（4,1）。從（1,1）可到達(dá)（2，3）、（3，2）兩個點，所以a1,1存放兩個點中的任意一個即可。遞推 在，否則a1,1值就是馬走下一步的坐標(biāo)，以此遞推輸出路徑?！緟⒖汲绦颉縞onstmaxn=50; maxm=50;dx:array1.4 ofeger=(2,2,1,1);dy:array1.4 ofeger=(1,-1,2,-2); typenode=recordx,y:eger; end;var，如果 a1,1值為(0,0)說明路徑不存n,m,i,j,k,t:eger;a:a

6、rray-1.maxn+2,-1.maxm+2 of node; beginreadln(n,m); fillchar(a,sizeof(a),0); an,m.x:=-1;an,m.y:=-1; for i:=n downto 2 dofor j:=1 to m doif ai,j.x0 then for k:=1 to 4 doif (i-dxk0)and(j-dyk0)and(j-dykm+1) beginai-dxk,j-dyk.x:=i;ai-dxk,j-dyk.y:=j; end;thenif a1,1.x=0 then wri elsebegini:=1;j:=1;n(no)wr

7、ite(,i,j,); while ai,j.x-1 dobegint:=i; i:=ai,j.x;j:=at,j.y;write(-(,i,j,);end; end;end.【任務(wù) 2 分析】用數(shù)組 ai,j存放從起點(x1,y1)到（i,j）的路徑總數(shù)。根據(jù)馬走的規(guī)則，馬可以由(i,j)走到（i+dxk,j+dyk），則 ai+dxk,j+dyk=ai+dxk,j+dyk+ai,j。為了保證馬走的坐標(biāo)必須在棋盤上，在棋盤外面加一圈墻，即棋盤外全賦上-1，以（x1,y1）為起點向右遞推，當(dāng)遞推到（x2，y2）時，就找到了從（x1，y1）到（x2,y2）的路徑數(shù)目 ax2,y2。【參考程序】c

8、onstmaxn=50; maxm=50;dx:array1.4 ofdy:array1.4 of vareger=(2,2,1,1);eger=(1,-1,2,-2);n,m,i,j,k,x1,y1,x2,y2:eger;a:array-1.maxn+2,-1.maxm+2 of beginreadln(n,m,x1,y1,x2,y2); fillchar(a,sizeof(a),0); for i:=0 to n+1 dobegina-1,i:=-1;a0,i:=-1;an+1,i:=-1; an+2,i:=-1;end;for i:=0 to m+1 do beginai,0:=-1;

9、ai,m+1:=-1;ai,-1:=-1;ai,m+2:=-1;end;64;for i:=1 to 4f ax1+dxi,y1+dyi-1thenbegin ax1+dxi,y1+dyi:=1; end;for i:=x1 to x2 for j:=1 to mif ai,j0do dothenfor k:=1 to 4 doif (i+dxk0)and(j+dyk0)then beginai+dxk,j+dyk:=ai+dxk,j+dyk+ai,j ; end;n(ax2,y2);wriend.四、總結(jié)遞推法分為順推和逆推兩種方法，它們的程序?qū)懛ǘ加幸欢ǖ囊?guī)律可循。順推法（例 14-1 和

10、例 14-2 的任務(wù)二）它們一般寫成如下形式：If 求解目標(biāo)結(jié)果 fn then Begin由題意或遞推關(guān)系確定初始值 f1；求出順推關(guān)系式 fi=g(fi-1);For i:=2 to n do fi=g(fi-1);輸出順推結(jié)果 fn;End;逆推法（例 14-2 的任務(wù)一）它們一般寫成如下形式If求解初始值 f1 then Begin由題意或遞推關(guān)系確定目標(biāo)；求出逆推關(guān)系式 fi-1=g(fi);For i:= n downto 2 dofi-1=g(fi);輸出逆推結(jié)果 f1; End;第二節(jié) 分治法一、引例【引例】主油管的最優(yōu)位置【問題描述】Olay 教授正在為一家石油公司。該公司正

11、在設(shè)計建造一條由東向西的管道，該管道要穿過一個有n 口井的油田。從每口井中都有一條噴油管沿最短路徑與主管道直接相連（或南或北）。給定各個井的 X 和 Y 坐標(biāo)，Olay 教授如何才能選擇主管道的最優(yōu)位置（即使得各噴管長度總和最小的位置）。【輸入】第一行：n(=10000)。以下 n 行，每行兩個正整數(shù) x,y(噴油管的坐標(biāo) )?！据敵觥抗艿赖淖顑?yōu)位置（即使得各噴管長度總和最小的位置）?！据斎霕永?235374【輸出樣例】4【分析】圖 14-6由于管道是東西向的，那么管道位置只和噴管的縱坐標(biāo) Y 有關(guān)，為了使各噴管長度總和最小，那么管道應(yīng)該在各條噴管的中間。也就是對 n 條噴油管的 y 坐標(biāo)按

12、從小到大的順序排序后，n 為偶數(shù)時，管道放在 an div 2的位置，n 為奇數(shù)時，管道放在 an div 2 到 an div 2+1之間的任何一個位置都可以。如果用冒泡或者選擇排序，時間復(fù)雜度為 O（n2）,當(dāng)n=10000 時會超時，這里度為 O(nlogn)的排序方法合并排序。合并排序是又一類不同的排序方法。“合并”的含義是將兩個或兩個以上的有序序列組介紹一種時間復(fù)雜一個新的有序序列。假設(shè)初始序列含有 n 個元素，則可看成是n 個有序的子序列，每個子序列的長度為一。然后兩兩合并，得到 n div 2 個長度為 2 或 1 的有序子序列；再兩兩合并， ，如此重復(fù)，直至得到一個長度為 n

13、的有序序列為止。例 12 個元素的排序碼為：（36 25 47 66 15 31 89 72 59 67 81 55）則進(jìn)行合并排序的過程如下所示（0）36 25 18 66 15 31 89 27 59 67 81 55（1）25 36 18 66 15 31 27 89 59 67 55 81（2）18 25 36 66 15 27 31 89 55 59 67 81（3）15 18 25 27 31 36 66 89 55 59 67 81（4）15 18 25 27 31 36 55 59 66 67 81 89【參考程序】varnteger;a:array1.10000 of pro

14、cedure init;var x,i:eger; beginreadln(n);for i:=1 to n doeger;read(x,ai);/將 y 坐標(biāo)到 a 數(shù)組中，x 不需要。end;procedure merge(L,mid,r:eger);已知 aL,mid和 amid+1,r已經(jīng)排好序，本過程將它們合并成一個有序的序列，并存放在aL,r中 varb:array1.10000 of i,j,k,t:eger;beginb:=a; i:=L;j:=mid+1;k:=L-1;eger;while (i=mid)and(j=r) do begink:=k+1;if ai=aj the

15、n begin bk:=ai;inc(i);endelse begin bk:=aj; inc(j);end;end;if i=mid then fort:=i to mid do begin inc(k); bk:=at; end; if j=r then for t:=j to r do begin inc(k);bk:=atend;a:=b; end;procedure mergesort(s,t:eger);/對 as,t中的數(shù)進(jìn)行合并排序var mid:eger; beginmid:=(s+t)div 2 ; if st thenbeginmergesort(s,mid); merg

16、esort(mid+1,t); merge(s,mid,t);end;end;procedure pr; var sum:real; beginif odd(n) thenwrin(a(n+1) div 2) elsewrin(,an div 2, ,an div 2+1 ,);end; begininit; mergesort(1,n); pr;end.二、分治策略對于引例這種規(guī)模比較大，不容易直接求解，可以考慮將該問題分割成一些規(guī)模較小的相同或相似的子問題，然后分別求解這些子問題，最后將子問題的解合并得到原問題的解。這就是分治的。具體來說，分治法是指把一個復(fù)雜分成兩個或個相同或相似的子問題

17、，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，然后將子問題的解的合并即得到原問題的解。分治法所能解決一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以直接求解；該問題可以分解為若干個規(guī)模較小的子問題，這些子問題與原問題相比只是規(guī)模有所降低，但是其結(jié)構(gòu)和求解方法與原問題相同或相似；利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的減小而減少；第二條特征是應(yīng)用分治法的前提，此特征反映了遞歸的應(yīng)用；第三條特征是關(guān)鍵，能否利用

18、分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題不是獨立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好。分治法在每一層遞歸上都有三個步驟：分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；解決：遞歸地解各個子問題，若子問題規(guī)模較小而容易被解決則直接求解；合并：將子問題的解合并為原問題的解。人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，問題的規(guī)模大致相同時，效率比較高。換句話說，將一個問題分成大小相等的 k 個子

19、問題的處理方法是行之有效的。一般情況下 k =2（因為 k 增大，就要增加分析子問題和合并子問題結(jié)果的復(fù)雜度）。K=2 時，又稱為二分法。三、分治法的應(yīng)用例 14-3 分蘋果【問題描述】有n 個蘋果，他想把這些蘋果分給他的同學(xué)。首先他要找出最大的一個蘋果送給和他關(guān)系最好的同學(xué)，然后再找出一個最小的蘋果送給他最不喜歡的同學(xué)。因為蘋果的數(shù)量太多了，最大和最小的蘋果。【輸入】第一行 一個正整數(shù) n(蘋果的數(shù)量，n=104)；第二行 n 個正整數(shù)（蘋果的體積），中間用空格隔開?！据敵觥肯胝埬銕兔φ页鲎畲筇O果的體積和最小蘋果的體積，中間用空格隔開。【輸入樣例】5【輸出樣例】11910【分析】該題可以直接

20、枚舉，從頭找到尾，最大的和最小的蘋果就直接找出來了。這里換一種思路解決該問題，用分治法來解決。分治法的思路：將n 個數(shù) a1.n分成兩部分 a1.n/2和 an/2+1.n，找出左半部分 a1.n/2的最大值 max1 和最小值 min1，同樣找出右半部分an/2+1.n的最大值 max2 和最小值 min2。那么該題的最大值就是 max1 和 max2 中的最大者，最小值就是 min1 和 min2 中的最小者。同理將左半部分和右半部分分別進(jìn)行劃分，直到最后每一部分只剩下一個數(shù)停止，這時候該數(shù)既是最大值又是最小值，然后再依次合并?！緟⒖汲绦颉縱arn,max:eger;a:array1.10

21、000 ofeger; procedure init;var i:eger; beginreadln(n);for i:=1 to n do read(ai);end;procedure main(L,r:eger;var min:eger;var max:eger); var mid,min1,min2,max1,max2:eger;beginif L=r then beg if Lr thenbeginmin1:=max min2:=maxin:=aL; max:=aL ;exit; end; max1:=0; max2:=0;mid:=(L+r) div 2;main(L,mid,min

22、1,max1);maid+1,r,min2,max2);if min1max2 then max:=max1 else max:=max2; end;end; begininit;main(1,n,max);wrin(max, ,min); end.此題很簡單，用分治法好像“殺雞用了求最接近點對等問題?！?，但是解題思路很重要，很多題用到該解題思路，比如例 14-4 一元三次方程求解（noip2001 提高）【問題描述】有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b， c，d 均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100 至 100

23、之間)，且根與根之差的絕對值=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后 2 位。提示：記方程 f(x)=0，若存在 2 個數(shù) x1 和 x2，且 x1x2，f(x1)*f(x2)0，則在(x1，x2)之間一定有一個根?！据斎搿恳恍兴膫€實數(shù) a，b，c，d（該方程中各項的系數(shù))?！据敵觥恳恍?三個實根(根與根之間留有空格)，并精確到小數(shù)點后 2 位?！据斎霕永?-5【輸出樣例】 -2.00【分析】-4202.005.00求一元三次方程問題，可以用求根公式，但是極為復(fù)雜，另外，大部分同學(xué)，對求根公式并不熟悉，考慮用分治法來解決本題。1、求方程的根假設(shè)區(qū)間

24、a,b 內(nèi)存在其只存在方程的一個根 x，則 f(a)*f(b)=0。當(dāng) f(a)*f(b)=0 時，x=a 或 x=b；當(dāng) f(a)*f(b)0 時，則可推出 axb,則解為（a+b）/2;如果 f(a)*f(x)0,則根 x 在區(qū)間a,(a+b)/2否則在區(qū)間(a+b)/2+1,b。對存在解的區(qū)間重復(fù)上述過程，就可以得到解。2、確定根的區(qū)間由于題目規(guī)定所有根的范圍都在-100 到 100 之間，且跟與根之差的絕對值大于等于 1，由此可知，在 -100,-99、-99，-98、99，100、100,100，這 201 個區(qū)間內(nèi)，每個區(qū)間內(nèi)至多只能存在一個根。除去區(qū)間100,100,其它區(qū)間a,

25、a+1，要么 f(a)=0,此時 a 即為解，要么 f(a)*f(a+1)0，則可利用 1 中所述的方法找出解?！緟⒖汲绦颉縱ara,b,c,d:real; x:array1.3 of real; procedure init; beginreadln(a,b,c,d); end;function f(x:real):real; beginf:=(a*x+b)*x+c)*x+d; end;function find(i:real):real;/找i,i+1中的根var s,t:real; begins:=i; t:=i+0.999999;/將區(qū)間i,i+1近似的表示為i,i+0.999999i

26、f abs(f(s)=0.000001 then exit(s); while (s+0.001t)and(f(a+b)/2)0) doif f(s)*f(s+t)/2)0 then t:=(s+t)/2else s:=(s+t)/2;exit(s+t)/2); end;procedure main; vari,j:eger; beginj:=0;for i:=-100 to 100 doif (abs(f(i)0.000001) or (f(i)*f(i+0.999999)=0) then begininc(j); xj:=find(i);end;end;procedure pr; var

27、i:eger; beginfor i:=1 to 3 do write(xi:0:2, );end; begininit; main; pr;end.注意： 由于實數(shù)運(yùn)算存在誤差， 判斷 x 是否為方程的根， 即abs(f(x)=0.000001,否則將失根，（此題也可使用枚舉法）。f(x)=0 時， 改用條件表達(dá)式第三節(jié) 枚舉算法一、 引例【引例】換錢問題【問題描述】要將一張 100 元的大鈔票，換成等值的 10 元、5 元、2 元、1 元一張的小鈔票，每次換成 40每種至少 1 張。一種換法：鈔票，10 元：5 元：2 元：1 元：1 張5 張31 張3 張問：一共有多少種換法?！痉治觥考?/p>

28、設(shè)四種錢幣的數(shù)量分別為 x1,x2,x3,x4 。又根據(jù)題意可知， 每種錢幣的取值范圍分別為1=x1=100/10,1=x2=100/5,1=x3=100/2,1=x4=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后 2 位。提示：記方程 f(x)=0，若存在 2 個數(shù) x1 和 x2，且 x1x2，f(x1)*f(x2)0，則在(x1，x2)之間一定有一個根?！据斎搿恳恍兴膫€實數(shù) a，b，c，d（該方程中各項的系數(shù))?！据敵觥恳恍?三個實根(根與根之間留有空格)，并精確到小數(shù)點后 2 位?！据斎霕永?-5【輸出樣例】 -2.00-4202.005.00分

29、析： 本題最簡單的方法是枚舉法：將 x 從-100 枚舉到 100（步長為 0.01）逐一枚舉，得到的 f(x)=0的值即為方程的解?！緟⒖汲绦颉縱ara,b,c,d:real; i:eger;function f(x:real):real; beginf:=(a*x+b)*x+c)*x+d; end;beginreadln(a,b,c,d);for i:=-10000 to 10000 do枚舉所有可能的解if abs(f(i/100)1e-5 then write(i/100:0:2,);end.例 14-6 最大公約數(shù)和最小公倍數(shù)問題（noip2001p）【問題描述】輸入二個正整數(shù) x0

30、,y0(2=x0100000,2=y0=1000000),求出滿足下列條件的 p,q 的個數(shù)：條件：p,q 是正整數(shù)；要求 p,q 以 x0 為最大公約數(shù),以 y0 為最小公倍數(shù)。試求：滿足條件的所有可能的兩個正整數(shù)的個數(shù)。【輸入樣例】x0=3yo=60【輸出樣例】4說明以下不用輸出此時的 P Q分別為：360所以，滿足條件的所有可能的兩個正整數(shù)的個數(shù)共 4 種。【分析】本題最容易想到的方法就是一一枚舉所有可能的情況，當(dāng)數(shù)據(jù)的規(guī)模比較小的時候還可以，但是數(shù)據(jù)規(guī)模大的時候很容易超時，下面【參考程序 1】 varp,q,x0,y0,sum:long; beginreadln(x0,y0); sum

31、:=0;for p:=1 to y0 do for q:=1 to y0 dobegin分析一下下列算法的時間復(fù)雜度。求p 與 q 的最大公約數(shù) x;求p 與 q 的最小公倍數(shù) y; If(x=x0)and(y=y0) then inc(sum);end;end.本算法分別枚舉 p,q，它們的取值都在 1 到y(tǒng)0 之間，這樣直接枚舉的時間復(fù)雜度為O（n2），當(dāng) n=103時還可接受，但是題意要求 2=x0100000,2=y0=1000000，當(dāng) y0=1000000 時，時間復(fù)雜度為 1012，很明顯會超時?？礃幼樱苯用つ棵杜e是量減少枚舉量。，那么能否根據(jù)題目給出的條件，找出數(shù)據(jù)之間的關(guān)系

32、，盡由數(shù)學(xué)知識知道，若 p、q 的最大公約數(shù)為 x0，則：p mod x0=0 ; q mod x0=0;假設(shè) s=p div x0;t:=q div x0;那么可以推出以下規(guī)律：根據(jù)最小公倍數(shù)的定義，y0=p*q/x0,又 s=p/x0,t=q/x0，則可以推出 s*t=y0/x0; 由此可進(jìn)一步推出如果 y0 mod x00,那么 p，q 不存在;如果 st，那么 s 和 t 互質(zhì)，即 s 和 t 的最大公約數(shù)為 1，否則，p 和 q 的最大公約數(shù)就不是 x0了。也就是說此時可以在 1y0/x0 之間查找滿足 s*t=y0/x0，且 s 和 t 互質(zhì)的數(shù)對。每對 s,t 對應(yīng)的 p,q 就

33、是問題的一組解。又 s,t 互質(zhì)的數(shù)對是對稱的，只要找出前半部分（st 的部分）的數(shù)對的個數(shù)，然后乘以 2就是所求的結(jié)果。比如樣例 x0=3,y0=60,則在 120 中，查找乘積為 20，且互質(zhì)的 s,t 數(shù)對，不難找出滿足條件的只有四組（1，20），（4，5），（5，4），（20，1），并且前半部分的數(shù)對和后半部分的數(shù)對是對稱的。如果 s=t，那么 s 和 t 的公約數(shù)為其自身，即 s=t=x0,同樣它們的最小公倍數(shù)也是自身，即 s=t=y0。也就是說如果 x0=y0，那么只存在一組解，即 p=q=x0=y0.【參考程序 2】varp,q,x0,y0,s,t,n,sum:long;func

34、tion check(p,q:long): vari:long; beginfor i:=2 to p do;if (p mod i=0)and(q mod i=0) then exit(false); exit(true);end; beginreadln(x0,y0);if (y0 mod x0=0)and (x0y0)then beginsum:=0; n:=y0 div x0;for p:=1 to trunc(sqrt(n) dobegin/第二種情況if (n mod p=0) then beginq:=n div p;/找到第一個因子/直接確定第二個因子if check(p,q)

35、 then sum:=sum+2;end;end;end;if y0 mod x00 then wrin(0) else if x0=y0 then write(1)else write(sum) ;end.總結(jié) ：/條件一/條件三上例是非常簡單的一個問題，但是充分體現(xiàn)了如何減少問題的枚舉總量的，在解題過程中，應(yīng)盡可能的排除那些明顯冗余或不可能屬于問題解的情況，但同時也應(yīng)該注意，在減少枚舉量的時候，必須保證不遺漏問題的解的可能情況，否則有可能導(dǎo)致漏掉部分解。第四節(jié) 貪心算法一、引例【引例】刪數(shù)問題【問題描述】鍵盤輸入一個正整數(shù) n，去掉其中任意 s 個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的

36、正整數(shù)。編程對給定的 n 和 s，尋找【輸入】案使得剩下的數(shù)字組成的新數(shù)最小。（n 不超過 240 位）兩行，第一行：正整數(shù) n，第二行：正整數(shù)S。【輸出】n 去掉的 s 個數(shù)字后組成的新的最小的正整數(shù) m?！据斎霕永?230062【輸出樣例】1006【分析】首先試題中n 不超過 240 位，為此n 應(yīng)為字符串類型。為了找到問題的解法，先從簡單的數(shù)據(jù)開始入手，比如從 428760005 中刪除 4 個數(shù)，通過嘗試可以發(fā)現(xiàn)第一數(shù)應(yīng)刪除 4，第二個刪 8，第三個刪 7，最后刪掉 6，此時得到的 20005 是最小的。再比如從 40002876 中刪 2 個數(shù)，應(yīng)該依次刪除 4 和 8，最后得到的

37、數(shù) 276 是最小的。再比如從 672397104 中刪除 5 個數(shù)，應(yīng)該依次刪除 7、6、9、7、3，最后得到的數(shù) 2104 是最小的。仔細(xì)分析會發(fā)現(xiàn)刪 s 個數(shù)的全局最優(yōu)解，也包含了刪一個數(shù)字的子問題的最優(yōu)解（可以用反 證明）。通過上面的樣例可以發(fā)現(xiàn)：刪數(shù)的過程中每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，也即每一步都做當(dāng)前看來的最優(yōu)解。為了保證刪 1 個數(shù)字后得到的數(shù)最小，總是按從到低位的順序搜索遞增區(qū)間，若遞增區(qū)間不存在，則刪最數(shù)字，否則刪遞增區(qū)間的末尾數(shù)字，這樣得到了一個新數(shù)串。然后回到串首，重復(fù)上述規(guī)則，刪下一個數(shù)字依次類推，直至刪除 s 個數(shù)字為止。總之，每一次刪除的一個數(shù)字都是

38、從首位開始的最長連續(xù)上升序列的最末位數(shù)字?！緟⒖汲绦颉縱arn:string;s,i:eger; beginreadln(n); read(s); while s0 dobegini:=1;讀入數(shù)字讀入刪除的數(shù)字個數(shù)while (ilength(n)and(ni1)and(n1=0) d wrin(n);刪除不下降序列的末位ete(n,1,1);刪除處理后開頭的 0，n 不為空end.二、貪心的從問題的某一個初始解出發(fā)，向給定的目標(biāo)推進(jìn)，推進(jìn)的每一步都是做一個當(dāng)前看起來最佳的貪心選擇，不斷的將問題實例歸納為更小的相似的子問題，并期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解。這就是貪心的。貪心

39、法并不是從全局考慮，而是每一步選擇一個當(dāng)前看來的最優(yōu)解，那么是不是所有問題都適宜于這種策略哪，顯然不是，下面看一下適用于貪心法來求解（1）貪心選擇性質(zhì)具有那些特點。所謂貪心選擇性質(zhì)是指應(yīng)用同一規(guī)則 f，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題、而后的每一步都是當(dāng)前看似最佳的選擇。這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。從全局來看，運(yùn)用貪心策略解決在程序的運(yùn)行過程中無回溯過程，因此貪心法有較高的時間效率。比如【引例】中，設(shè)正整數(shù) n 有 m 位，第一步刪除一個數(shù)字使剩下的 m-1 位數(shù)字最小，把問題變成從 m-1 位的整數(shù)中去掉 s-1 個數(shù)字后的新數(shù)最小的子問題；第二步再選擇一個

40、使得剩下的新數(shù)最小的數(shù)字刪去，又把問題歸納為在 m-2 位正整數(shù)中去掉 s-2 個數(shù)字后的新數(shù)最小的子問題每次選擇中，已經(jīng)刪掉的數(shù)不允許再刪，并且當(dāng)前選擇不會受將來刪數(shù)的影響。依照上述方法不斷將問題歸納為更小的互為獨立的子問題，直到 s 個數(shù)字全部刪掉為止。由此可以看出刪數(shù)問題符合貪心選擇性質(zhì)。（2）最優(yōu)子結(jié)構(gòu)性質(zhì)所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指一個問題的最優(yōu)解包含了其子問題的最優(yōu)解。比如【引例】中，n=428760005,s=4.第一步的貪心選擇為刪 4，即第一個子問題的最優(yōu)解為刪 4 后得到的數(shù) 28760005,第二的貪心選擇為刪 8，即第二個子問題的最優(yōu)解為刪 8 后得到的數(shù) 2760005，隨

41、后的第三個和第四個應(yīng)該刪除的數(shù)分別是 7 和 6，得到的最優(yōu)解依次為 260005，20005。顯然該問題的全局最優(yōu)解包含了 4 個子問題的最優(yōu)解，因此該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。三、貪心的應(yīng)用例 14-7 部分背包問題【問題描述】第一次去姑媽家做客，姑媽很高興，決定送給n 件。但是的背包太小，只能裝下容量為 V 的物品?，F(xiàn)在知道物越值錢越好?！据斎搿靠梢苑指畛扇我獯笮?，并且知道每件的體積和價值，希望帶走的禮第一行兩個數(shù)：物品總數(shù) N（100），背包的體積 V(100)；兩個數(shù)之間用空格分隔；第二行 N 個數(shù),為N 種物品體積 vi；兩個數(shù)之間用空格分隔；第三行 N 個數(shù),為N 種物品價值 pi

42、; 兩個數(shù)之間用空格分隔；【輸出】若干行，每行為取走的標(biāo)號和體積。最后一行輸出最大價值?！据斎霕永?5010 20 3060 100 120【輸出樣例】1 102 203 30240【分析】先從簡單問題入手，假設(shè)有兩件，第一件價值為 20，體積為 100，第二件價值為 10，體積為 1。選那個哪，肯定選第二件物品，也就是說每次選取容量價值最大的物品，這就是本題的貪心策略。選擇的約束條件是是裝入的物品總體積不超過背包容量：vimidnc(i);while aj.ppmid do dec(j); if ij;if lj then qsort(l,j); if iai.v thenbegin/依次

43、取走容量價值最大的sumv:=sumv-ai.v; sump:=sump+ai.p;wrin(ai.t, ,ai.v:0:0); endelsebegin/帶走最后一件物品的一部分sump:=sump+ai.pp*sumv;wrin(ai.t, ,sumv:0:0);break; /背包裝滿則退出 end;n(sump:0:0);wri end;begininit;qsort(1,n); main;end.在該背包問題中，如果規(guī)定每件要么全裝上，要么不裝，但不能裝一部分，這就變成了 0-1 背包問題。此時還能不能采用貪心算法來求解哪？對于樣例繼續(xù)用貪心的話應(yīng)該會選擇第一件物品和第二件物品，總價值為 160，或者第一件和第三件，總價值為 180。但是最優(yōu)解應(yīng)該是選擇第二件和第三件物品，總價值為 220。此時貪心就不適用了，應(yīng)該用前一章講過的動態(tài)規(guī)劃來求解。例 14-8 潛水比賽【問題描述】在馬其頓王國舉行了一次潛水比賽。其中一個項目是從高山上跳下水，再潛水達(dá)到終點。這是一個團(tuán)體項目，一支隊伍由 n 人組成。在潛水時必須使用氧氣瓶，但是每只隊伍只有一個氧氣瓶。最多兩人同時使用一個氧氣瓶，但此時兩人必須同步游泳，因此兩人達(dá)到終點的時間等于較慢的一個人單獨游到終點所需要的時間。好在大家都很友好，因此任何兩個人后都愿意一