論分治算法在信息學(xué)競(jìng)賽中的應(yīng)用

1、論分治算法在信息學(xué)競(jìng)賽中的應(yīng)用紹興縣魯迅中學(xué)教技處 夏紅軍一、問(wèn)題的提出【例1】尋找假幣（Noip2006初賽普及組問(wèn)題求解第二題）【問(wèn)題描述】現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍輕，所有真幣的重量都相同，如果使用不帶砝碼的天平稱(chēng)重，最少需要稱(chēng)幾次，就可以找出假幣？你還要指出第1次的稱(chēng)重方法。二、問(wèn)題的分析1、直接的想法是將這些硬幣2枚一組分為40組，每次只稱(chēng)一組硬幣，若發(fā)現(xiàn)輕的則為假幣，最壞情況下稱(chēng)40次才可找出假幣。2、仔細(xì)思考上面的分法比較一次只能排除2枚硬幣，利用只有一枚假幣的性質(zhì)，我們?cè)囍淖円幌路椒ǎ簩⑺杏矌牌骄譃閮山M，每次稱(chēng)兩組硬幣，這樣比較一次可排除一半硬幣，最壞情況

2、下只需稱(chēng)7次。3、顯然每比較一次能排除的硬幣越多越好，朝著這個(gè)目標(biāo)對(duì)怎樣分組進(jìn)一步思考。三、問(wèn)題的解決把所有的硬幣盡量平均地分成三組，至少有兩組硬幣數(shù)是相同的，每次稱(chēng)相同的兩組，這樣每比較一次可排除約2/3的硬幣數(shù)，最壞情況下只需稱(chēng)4次。四、算法的引入通常我們將這種以大化小的設(shè)計(jì)思想稱(chēng)之為分治算法，即“分而治之”的意思。也就是說(shuō)，當(dāng)我們處理大規(guī)模問(wèn)題時(shí)，可以將原問(wèn)題分解成k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，而且在求出了這些子問(wèn)題的解之后，還可找到適當(dāng)?shù)姆椒ò阉鼈兒喜⒊烧麄€(gè)問(wèn)題的解。分治算法一般分為三個(gè)步驟：分解(Divide)：將原問(wèn)題分成一系列子問(wèn)題。求解(Conqu

3、er)：若子問(wèn)題足夠小，則可直接求解。合并(combine)；將子問(wèn)題的結(jié)果合并成原問(wèn)題的解?？梢钥闯?，為實(shí)現(xiàn)分治算法，一個(gè)方法是借助遞歸結(jié)構(gòu)，另一個(gè)方法是從已知的小問(wèn)題出發(fā)進(jìn)行遞推，小問(wèn)題層層合并成大問(wèn)題后解決。遞歸大致過(guò)程如下：Divide-and-Conquer(P)1. if |P|n0 2. then return(ADHOC(P)3. 將P分解為較小的子問(wèn)題 P1 ,P2 ,.,Pk 4. for i1 to k 5. do yi Divide-and-Conquer(Pi) 遞歸解決Pi6. T MERGE(y1,y2,.,yk) 合并子問(wèn)題7. return(T)其中|P|表示

4、問(wèn)題P的規(guī)模；n0為一閾值，表示當(dāng)問(wèn)題P的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。因此，當(dāng)P的規(guī)模不超過(guò)n0時(shí)，直接用算法ADHOC(P)求解。算法MERGE(y1,y2,.,yk)是該分治法中的合并子算法，用于將P的子問(wèn)題1 ,P2 ,.,Pk的相應(yīng)的解y1,y2,.,yk合并為P的解。經(jīng)過(guò)上面的分析，我們應(yīng)該考慮原問(wèn)題分多少個(gè)子問(wèn)題才較適宜？各個(gè)子問(wèn)題的規(guī)模應(yīng)該怎樣才為適當(dāng)？這些問(wèn)題很難予以肯定的回答。但大量實(shí)踐發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。許多問(wèn)題可以取k=2，又稱(chēng)二分法，大家熟悉

5、的二分查找，快速排序，歸并排序都是基于這種算法的應(yīng)用。五、算法的應(yīng)用下面我再例談幾個(gè)問(wèn)題，以幫助大家能夠徹底地掌握這種算法?！纠?】循環(huán)比賽【問(wèn)題描述】設(shè)有n支(n=2m,m=2）表示第i個(gè)隊(duì)員在第j-1天的比賽對(duì)手。仔細(xì)觀察發(fā)現(xiàn)這張表是中心對(duì)稱(chēng)的，這給我們一個(gè)啟示，我們要設(shè)計(jì)一張88的比賽安排表a1.8,1.8，只需要設(shè)計(jì)出表的上半部分，即兩張44的安排表a1.4,1.4和a1.4,5.8即可。之后，通過(guò)已經(jīng)設(shè)計(jì)出來(lái)的表的左上角a1.4,1.4復(fù)制出表的右下角a5.8,5.8，通過(guò)右上角a1.4,5.8制出表的左下角a5.8,1.4。同樣，任一張44的比賽安排表可以通過(guò)兩張22的比賽安排表產(chǎn)

6、生。繼續(xù)直到兩張11的比賽安排表，這是問(wèn)題的最小規(guī)模，即可賦初值解決。根據(jù)分析的規(guī)律，這完全符合分治算法?！痉椒ㄒ弧坎捎眠f歸結(jié)構(gòu)，完整程序如下：Program ex2;type arr=array1.1000,1.1000 of integer;var a:arr;i,j,m,n:integer;procedure arrange(var a:arr;n,left,right:integer);n表示方陣的大小，即球隊(duì)的數(shù)量 var i,j,mid:integer;begin if n2 then exit; mid:=(left+right) div 2;把方陣分為兩半 n:=n div 2

7、; arrange(a,n,left,mid);遞歸處理左上角方陣 arrange(a,n,mid+1,right);遞歸處理右上角方陣 for i:=1 to n do begin for j:=left to mid do ai+n,j+n:=ai,j; 從已得方陣的左上角推出右下角 for j:=mid+1 to right do ai+n,j-n:=ai,j; 從已得方陣的右上角推出左下角 end;end;begin readln(m); n:=1; for i:=1 to m do n:=n*2; fillchar(a,sizeof(a),0); for i:=1 to n do a

8、1,i:=i;先確定第一行球隊(duì)的編號(hào) arrange(a,n,1,n);遞歸產(chǎn)生各個(gè)方陣 for i:=1 to n do begin for j:=1 to n do write(ai,j:5); writeln; end;end.【方法二】采用非遞歸結(jié)構(gòu)，核心程序段如下：procedure arrange(var a:arr;max:integer); max表示方陣的大小，即球隊(duì)的數(shù)量 var i,j,k,n,left,right,mid:integer;begin n:=2; while n=max do 依次安排2、4、8支球隊(duì) begin left:=1;left當(dāng)前被按排球隊(duì)的左

9、邊界 while leftmax do begin right:=left+n-1; right當(dāng)前被按排球隊(duì)的右邊界 mid:=(left+right) div 2; k:=n div 2; 將球隊(duì)分成左右兩半處理，每半有k個(gè)球隊(duì) for i:=1 to k do begin for j:=left to mid do ai+k,j+k:=ai,j; 由左上角推出右下角 for j:=mid+1 to right do ai+k,j-k:=ai,j; 由右上角推出左下角 end; left:=left+n; end; n:=n*2; end;end;通過(guò)上例我們得出分治算法可以使用遞歸結(jié)構(gòu)和

10、非遞歸結(jié)構(gòu)解決，非遞歸編寫(xiě)的程序時(shí)間、空間復(fù)雜度低，而遞歸編寫(xiě)的程序具有容易設(shè)計(jì)，結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)。 【例3】貸款利率【問(wèn)題描述】當(dāng)一個(gè)人從銀行貸款后，在一段時(shí)間內(nèi)他(她)將不得不每月償還固定的分期付款。這個(gè)問(wèn)題要求計(jì)算出貸款者向銀行支付的利率。假設(shè)利率按月累計(jì)?！据斎搿枯斎胛募H一行包含三個(gè)用空格隔開(kāi)的正整數(shù)。第一個(gè)整數(shù)表示貸款的原值a，第二個(gè)整數(shù)表示每月支付的分期付款金額b，第三個(gè)整數(shù)表示分期付款還清貸款所需的總月數(shù)m。(1a,b109,1m104)【輸出】輸出文件應(yīng)該是一個(gè)實(shí)數(shù)，表示該貸款的月利率(用百分?jǐn)?shù)表示)，四舍五入精確到0.1%?！緲永斎搿?000 100 12【樣例輸

11、出】2.9【分析】顯然這是一道數(shù)學(xué)題，假設(shè)月利率為x，f(x)=，求解這個(gè)一元高階方程，考慮到時(shí)間復(fù)雜度，采用窮舉法似乎不太可行。聯(lián)想noip2001復(fù)賽提高組第一題一元三次方程求解，我們采用的是分治法，這題的思路就來(lái)了。我們可以先確定月利率的大致區(qū)間x1.x2，然后將該區(qū)間分成左右兩個(gè)子區(qū)間：左子區(qū)間x1.xm，右子區(qū)間xm.x2（其中xm=）。如果f(xm)0，假設(shè)的月利率就低了，x1就調(diào)整為xm；否則x2調(diào)整為xm上述對(duì)分過(guò)程一直進(jìn)行到abs(x1-x2)=1e10為止，此時(shí)可以確定x1為f(x)的根。源程序參考如下： program ex3; var a,b,m:longint; xm

12、,x1,x2,xu:extended;function mi(x:extended):extended; var i:longint; t:extended; begin t:=1; for i:=1 to m do t:=t*x; mi:=t; end; beginread(a,b,m); if a=b*m then begin writeln(0.0);halt;end; x1:=1; x2:=2; xu:=mi(x2); while a*xu-b*(1-xu)/(1-x2)1e-10 do begin xm:=(x1+x2)/2 ; xu:=mi(xm); if a*xu-b*(1-xu

13、)/(1-xm) 1 do begin nl:=nl div 3;把數(shù)據(jù)平均分成三組 s1:=0;s2:=0;for i:=k+1 to k+nl do s1:=s1+ai; for i:=k+nl+1 to k+2*nl do s2:=s2+ai;分別求前兩組數(shù)據(jù)和if s1max then max:=ai; If ai2）個(gè)數(shù)據(jù)，先分成兩組，分別求其最大值、最小值，然后分別將這兩組的最大值、最小值相比較，求出全部元素的最大值和最小值。若分組后元素個(gè)數(shù)仍大于2，則再次分組，直至組內(nèi)元素小于等于2。 下面我們通過(guò)具體程序，對(duì)該算法作進(jìn)一步闡述。算法通過(guò)調(diào)用一個(gè)maxmin(n,n,max,mi

14、n)的遞歸過(guò)程來(lái)從已知n個(gè)元素的集合a中找出最大值max和最小值min。數(shù)組a表示集合，元素個(gè)數(shù)用n表示。若a=2，則它們分別為max和min，而max1，max2，min1，min2分別來(lái)存放兩個(gè)子集的最大值和最小值。下面是完整的參考程序：Program ex5;Var n,i:integer;max,min:real;a:array1.100 of real;Procedure maxmin(i,j:integer;var max,min:real); Var mid:integer;max1,max2,min1,min2:real;Begin Case j-I of 0:begin ma

15、x:=ai;min:=aj;end; 集合中只有一個(gè)元素 1:if aimax2 then max:=max1 else max:=max2; 歸并 If min1min2 then min:=min2 else min:=min1; End; End;End;begin readln(n); for i:=1 to n do read(ai); maxmin(1,n,max,min); writeln; writeln(max number is,max, ;,min number is,min);end.【例6】一元三次方程求解(noip2001提高組復(fù)賽第一題)【問(wèn)題描述】有形如：ax3

16、+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。提示：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1x2，f(x1)*f(x2)0，則在(x1，x2)之間一定有一個(gè)根?！据斎搿縜，b，c，d【輸出】三個(gè)實(shí)根（根與根之間留有空格）【樣例輸入】1 -5 -4 20【樣例輸出】-2.00 2.00 5.00【算法分析】此題可以用枚舉法求解，但如果求解的精度進(jìn)一步提高，使用枚

17、舉法就無(wú)能為力了，在此我們討論如何用二分法求解此題。由題意知（i,i+1）中若有根，則只有一個(gè)根，我們枚舉根的值域中的每一個(gè)整數(shù)x(-100x100),設(shè)定搜索區(qū)間x1，x2，其中x1=x，x2=x+1。若：f(x1)=0，則確定x1為f(x)的根；f(x1)*f(x2)0，則確定根x不在區(qū)間x1，x2內(nèi)，設(shè)定x2，x2+1為下一個(gè)搜索區(qū)間；若確定根x在區(qū)間x1，x2內(nèi)，采用二分法，將區(qū)間x1，x2分成左右兩個(gè)子區(qū)間：左子區(qū)間x1，xx和右子區(qū)間xx，x2（其中xx=（x1+x2）/2）。如果f(x1)*f(xx)0，則確定根在左區(qū)間x1，xx內(nèi)，將xx設(shè)為該區(qū)間的右界值（x2=xx），繼續(xù)對(duì)

18、左區(qū)間進(jìn)行對(duì)分；否則確定根在右區(qū)間xx，x2內(nèi)，將xx設(shè)為該區(qū)間的左界值（x1=xx），繼續(xù)對(duì)右區(qū)間進(jìn)行對(duì)分；上述對(duì)分過(guò)程一直進(jìn)行到區(qū)間的間距滿(mǎn)足精度要求為止（即x2-x10.005）。此時(shí)確定x1為f(x)的根。參考程序如下：Program ex6;$N+var x:integer; a,b,c,d,x1,x2,xx:extended;function f(x:extended):extended;begin f:=(a*x+b)*x+c)*x+d;end;begin read(a,b,c,d); for x:=-100 to 100 do begin x1:=x;x2:=x+1; if f

19、(x1)=0 then write(x1:0:2, ) else if f(x1)*f(x2)=0.005 do begin xx:=(x1+x2)/2; if f(x1)*f(xx)=0 then x2:=xx else x1:=xx; end;while write(x1:0:2, ); end; then end;forend.【例7】數(shù)的查找【問(wèn)題描述】對(duì)于給定的n個(gè)元素的數(shù)組a1.n，要求從中找出第k小的元素。【輸入】第一行是總數(shù)n和k，第二行是n個(gè)待比較的元素?！据敵觥康趉小的數(shù)在數(shù)組中的位置?！緲永斎搿?0 47 2 6 8 13 15 11 22 10 9【樣例輸出】8【問(wèn)題

20、分析】對(duì)于一組混亂無(wú)序的數(shù)來(lái)說(shuō)，要找到第k小的元素通常要經(jīng)過(guò)兩個(gè)步驟方可實(shí)現(xiàn)：第一步，將數(shù)進(jìn)行從小到大排序；第二步，確定第k個(gè)位置上的數(shù)。傳統(tǒng)的排序算法（插入排序法、選擇排序法等）大家已經(jīng)非常熟悉了，但已學(xué)過(guò)的排序方法無(wú)論從速度上，還是從穩(wěn)定性方面不是最佳的，因此在實(shí)際運(yùn)用中一般不大采用。事實(shí)上用歸并排序或堆排序的方法來(lái)實(shí)現(xiàn)排序相對(duì)而言是較快較穩(wěn)的，或者通過(guò)避免排序的方法同樣也可以有效地提高查找的效率。下面戯一列由10個(gè)元素組成的數(shù)組：7 2 6 8 13 15 11 22 10 9假設(shè)要找出k=4的元素，我們不妨這樣來(lái)處理：設(shè)i指針為這個(gè)數(shù)列的左邊界，j指針為這個(gè)數(shù)列的右邊界，將中間數(shù)13作

21、為一個(gè)基準(zhǔn)數(shù)，然后i指針從左邊掃描過(guò)來(lái)，碰到大于等于13時(shí)停止，再讓j指針從右邊掃描過(guò)來(lái)，碰到小于等于13時(shí)停止，如果ij，此時(shí)13小的數(shù)在左邊，比13大或相等的數(shù)在右邊，即變成二段7 2 6 8 9 10 1122 15 13觀察一下，比第二段小的數(shù)有7個(gè)，題目要求k=4，那么我們就可以將數(shù)的搜索范圍縮小到第一段。遞歸地對(duì)第一段進(jìn)行上述處理，變成了7 2 6 8 9 10 11三段。 通看一遍，第一段右邊界是，而第二段的左邊界是5，而基準(zhǔn)數(shù)8正好是第4小的元素。這個(gè)方法正是利用了分治算法，時(shí)間復(fù)雜度應(yīng)該是log2(n)，下面是核心程序段：function find(l,r,k:longint

22、):longint;var i,j,mid:longint;begin if l=r then exit(al); i:=l; j:=r; mid:=a(i+j)div 2; repeat while aimid do dec(j); if ij; if (l=j) and (k=j) then exit(find(l,j,k); if (i=i) then exit(find(i,r,k); exit(mid);end;【例8】旅行家的預(yù)算(noip1999提高組復(fù)賽第三題)【問(wèn)題描述】一個(gè)旅行家想駕駛汽車(chē)以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離A、

23、汽車(chē)油箱的容量C（以升為單位）每升汽油能行駛的距離B、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途油站數(shù)N（0=N=100），油站i離出發(fā)點(diǎn)的距離Di、每升汽油價(jià)格Pi（il，2，.N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無(wú)法到達(dá)目的地，則輸出“No solution”?！据斎搿緼 C B P N D1 P1 D2 P2 DN PN【輸出】最小費(fèi)用【樣例輸入】275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2【樣例輸出】26.95【算法分析】（1）第i站到第i+1站的距離大于C*B，則輸出無(wú)解信息后退出。（2）有解的話(huà)我們這樣考慮，除終點(diǎn)站外從后向前尋找油價(jià)最低的加油站k，如果k不

24、是起點(diǎn)，顯然車(chē)至k站油箱應(yīng)為空，利用分治法可以將起點(diǎn)至k站、k站至終點(diǎn)作為兩個(gè)子問(wèn)題考慮；否則k為起點(diǎn)，若能一次加油即到達(dá)終點(diǎn)則直接計(jì)算，若不能則在k站應(yīng)加滿(mǎn)油，然后從后往前尋找除起點(diǎn)終點(diǎn)站外油價(jià)最低的加油站，若該加油站位于起點(diǎn)加滿(mǎn)油后不能到達(dá)之處，則到達(dá)該站時(shí)油箱應(yīng)該為空，以該站為界將全程分為兩個(gè)子問(wèn)題考慮，否則該加油站處于起點(diǎn)加滿(mǎn)油后能到達(dá)之處，前一段可直接計(jì)算費(fèi)用，后一段又可視為一個(gè)有余油的子問(wèn)題。對(duì)每個(gè)子問(wèn)題繼續(xù)用上面分治的算法解決。（3）設(shè)計(jì)一個(gè)遞歸函數(shù)money，形式參數(shù)start表示起點(diǎn)站，形式參數(shù)stop表示終點(diǎn)站，形式參數(shù)rest表示到達(dá)加油站start時(shí)汽車(chē)油箱余下的油的容

25、量，它的功能是最終計(jì)算出從加油站start到stop區(qū)間內(nèi)的最小費(fèi)用。 參考程序代碼如下：function money (start，stop:longint；rest:real):real；Var k:longint；beginif stop-start=1 then money:=(dstop-dstart)/d2-rest)*pstartelse begin k:=minp(start，stop-1)； minp(b，e:longint):longint；在b站到e站之間從后往前找油價(jià)最低的站 if kstart 油價(jià)最低的加油站不是起點(diǎn)站 then money:=money(start

26、，k，rest)+money(k，stop，0) else if dstop-dstart=d2*c 在起點(diǎn)加滿(mǎn)油能直接到達(dá)該段終點(diǎn) then money:=(dstop-dstart)/d2-rest) * pstart else begin k:=minp(start+1 , stop-1) ; if dk - dstart = d2 * c then 在起點(diǎn)加滿(mǎn)油能到達(dá)加油站k money:=(c-rest) * pstart + money(k, stop, c-(dk - dstart)/d2) else money := money(start, k, rest) + money(

27、 k, stop, 0) end endend;【例9】坐車(chē)【問(wèn)題描述】甲、乙兩人同時(shí)從A地出發(fā)盡快同時(shí)趕到B地，出發(fā)時(shí)你在A地開(kāi)著一輛只能坐兩個(gè)人的小車(chē)，又知甲乙兩人步行的速度，問(wèn)，怎樣利用小車(chē)才能使兩人盡快同時(shí)到達(dá)?！舅惴ǚ治觥孔罴逊桨福杭紫瘸塑?chē)到達(dá)C地后下車(chē)行走，車(chē)回頭接已經(jīng)走到E地的乙設(shè)在D相遇，乙乘車(chē)到達(dá)B地時(shí)也步行到達(dá)，這時(shí)時(shí)間最短。問(wèn)題轉(zhuǎn)化為求C點(diǎn)的位置，設(shè)A、B距離為S，步行速度為a，車(chē)速為b，甲耗時(shí)T1，乙耗時(shí)T2?！娟P(guān)鍵算法】1）c0:=0;c1:=s;,c:=(c0+c1)/2;以中間點(diǎn)作為測(cè)試數(shù)據(jù)；2）求T1，T2;3）if T1T2 then C0、C中點(diǎn)設(shè)為C el

28、se 把C、C1中點(diǎn)設(shè)為C。反復(fù)進(jìn)行（2）（3）直到T1-T2e(誤差)參考程序repeat c:=(c0+c1)/2; t3:=c/b;計(jì)算甲乘車(chē)到c的時(shí)間 t1:=t3+(s-c)/a;計(jì)算甲總耗時(shí) t4:=（c-t3*a）/(a+b)計(jì)算小車(chē)從c回頭與乙相遇的時(shí)間 t2:=t3+t4+(s-(t3+t4)*a)/b;計(jì)算乙總耗時(shí)； if t1t2 then c1:=c else c0:=c;until abs(t1-t2)e0;(e0是一個(gè)足夠小的數(shù))【例10】剔除多余括號(hào) 【問(wèn)題描述】輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余的括號(hào)，原表達(dá)式中

29、所有變量和運(yùn)算符相對(duì)位置保持不變，并保持與原表達(dá)式等價(jià)。 輸入表達(dá)式應(yīng)輸出表達(dá)式a+(b+c)a+b+c(a*b)+c/(d*e)a*b+a/(d*e)a+b/(c-d)a+b/(c-d)例如：注意輸入表達(dá)式以字符串輸入，長(zhǎng)度不超過(guò)255，輸入不需要判錯(cuò)。所有變量為單個(gè)小寫(xiě)字母。只是要求去掉所有多余括號(hào)，不要求對(duì)表達(dá)式簡(jiǎn)化?！緲永斎搿?a*b)+c/da*b+c/d【樣例輸出】a*b+c/da*b+c/d【算法分析】四則運(yùn)算表達(dá)式含運(yùn)算符+,-,*,/,(,)，我們分析一下表達(dá)式中哪些括號(hào)可以去掉。設(shè)待整理的表達(dá)式為（s1 op s2）；op為括號(hào)內(nèi)優(yōu)先級(jí)最低的運(yùn)算符（“+”，“-”或“*”

30、，“/”）；左鄰括號(hào)的運(yùn)算符為“/”，則括號(hào)必須保留，即 /（s1 op s2） 形式。左鄰括號(hào)的運(yùn)算符為“*”或“-”。而op為“+”或“-”，則保留括號(hào)，即*（s1+s2） 或 -（s1+s2） 或 *（s1-s2） 或 -（s1-s2）右鄰括號(hào)的運(yùn)算符為“*”或“/”，而op為“+”或“-”，原式中的op運(yùn)算必須優(yōu)先進(jìn)行，因此括號(hào)不去除，即（s1+s2）* 除上述情況外，可以括號(hào)去除，即 s1 op s2 等價(jià)于（s1 op s2）在設(shè)計(jì)算法時(shí)，可以在優(yōu)先級(jí)最低的運(yùn)算符處將原表達(dá)式拆分為兩個(gè)子表達(dá)式，然后對(duì)每個(gè)子表達(dá)采用相似的方法進(jìn)行拆分，同時(shí)對(duì)相應(yīng)層進(jìn)行括號(hào)整理，直至最外層的括號(hào)保留或

31、去除為止。例如，剔除表達(dá)式“(a+b)*f)-(i/j)”中多余的括號(hào)。依據(jù)上述算法進(jìn)行拆分整理過(guò)程如下：最后自底向上得到整理結(jié)果：(a+b)*f-i/j。參考程序如下：var ch:char;expr:string;function rightbracket(s:string;i:byte):byte;var q:byte;begin q:=1; repeat inc(i); if si=( then inc(q) else if si=) then dec(q); until q=0; rightbracket:=i;end;function find(s:string):byte;var

32、 i,k,k1,k2:byte;begin i:=1;k1:=0;k2:=0; while i=length(s) do begin if (si=+)or(si=-) then k1:=i; if (si=*)or(si=/) then k2:=i; if si=( then i:=rightbracket(s,i); inc(i); end; if k1=0 then find:=k2 else find:=k1;end;function deletebracket(s:string;var p:char):string;var i:byte;ch1,ch2:char;left,right

33、:string;begin if length(s)=1 then begin deletebracket:=s;p:= ;exit;end; if (s1=()and(rightbracket(s,1)=length(s) then begin deletebracket:=deletebracket(copy(s,2,length(s)-2),p); exit; end; i:=find(s); p:=si; left:=deletebracket(copy(s,1,i-1),ch1); right:=deletebracket(copy(s,i+1,length(s)-i),ch2);

34、if (p in *,/)and(ch1 in +,-) then left:=(+left+); if (p in *,-)and(ch2 in +,-) or (p=/)and(ch2 ) then right:=(+right+); deletebracket:=left+p+right;end;begin readln(expr); writeln(deletebracket(expr,ch);end.【例11】導(dǎo)線和開(kāi)關(guān)【問(wèn)題描述】如下圖是一個(gè)具有3根導(dǎo)線的電纜把A區(qū)和B區(qū)連接起來(lái)。在A區(qū)3根導(dǎo)線標(biāo)以1，2，3;在B區(qū)導(dǎo)線1和被連到開(kāi)關(guān)3，導(dǎo)線2連到開(kāi)關(guān)1。一般說(shuō)來(lái)，電纜含(190)

35、根導(dǎo)線，在A區(qū)標(biāo)以1,2,m。在B區(qū)有個(gè)開(kāi)關(guān)，標(biāo)為1，2，。每一根導(dǎo)線都被嚴(yán)格地連到這些開(kāi)關(guān)中的某一個(gè)上; 每一個(gè)開(kāi)關(guān)上可以連有0根或多根導(dǎo)線。你的程序應(yīng)作某些測(cè)量來(lái)確定導(dǎo)線和開(kāi)關(guān)怎樣連。每個(gè)開(kāi)關(guān)或處于接通或處于斷開(kāi)狀態(tài)，開(kāi)關(guān)的初始狀態(tài)為斷開(kāi)。我們可用一個(gè)探頭P在A區(qū)進(jìn)行測(cè)試：如果探頭點(diǎn)到某根導(dǎo)線上，當(dāng)且僅當(dāng)該導(dǎo)線連到處于接通狀態(tài)的開(kāi)關(guān)時(shí)，燈L才會(huì)點(diǎn)亮。你的程序從標(biāo)準(zhǔn)輸入讀入一行以得到數(shù)字m；然后可以通過(guò)向標(biāo)準(zhǔn)輸出寫(xiě)入一行以發(fā)出命令(共3種命令)。每種命令的開(kāi)頭是一個(gè)大寫(xiě)字母:測(cè)試導(dǎo)線命令T：T后面跟一個(gè)導(dǎo)線標(biāo)號(hào)；改變開(kāi)關(guān)狀態(tài)命令C：C后面跟一個(gè)開(kāi)關(guān)標(biāo)號(hào)；完成命令D：D后面跟的是一個(gè)表列，該表

36、列中的第i個(gè)元素代表與導(dǎo)線i相連的開(kāi)關(guān)號(hào)。在命令T和C之后，你的程序應(yīng)從標(biāo)準(zhǔn)輸入讀入一行。若開(kāi)關(guān)狀態(tài)能使燈亮，則命令T的回答應(yīng)是Y；反之，回答應(yīng)是N。命令C的作用是改變開(kāi)關(guān)的狀態(tài)(若原來(lái)是接通則變?yōu)閿嚅_(kāi)；若原來(lái)是斷開(kāi)則變?yōu)榻油?。對(duì)C命令的回答是作為一種反饋信號(hào)。 你的程序可以給出一系列命令，將T命令與C命令以任意順序混合使用。最后給出命令D，并結(jié)束。你的程序給出的命令總數(shù)應(yīng)不大于900。舉例：下表給出了一個(gè)實(shí)例，對(duì)應(yīng)于上圖，這是一個(gè)有8條命令的對(duì)話(huà)。 Standard Output Standard Input 3 C 3 Y T 1 Y T 2 N T 3 Y C 3 N C 2 Y T

37、2 N D 3 1 3 【算法分析】為了使導(dǎo)線和開(kāi)關(guān)的連接工作有規(guī)律地進(jìn)行，我們不妨采用二分法。1分解設(shè)當(dāng)前待接的開(kāi)關(guān)為head.tail,初始時(shí)為1.m,則左區(qū)間head.(head+tail-1)/2,開(kāi)關(guān)集合為p1=1.m，右區(qū)間 (head+tail-1)/2+1.tail,開(kāi)關(guān)集合為p2=，導(dǎo)線的連接狀態(tài)state=(0,1)，分別表示斷開(kāi)和連接，對(duì)區(qū)間進(jìn)行檢測(cè)，對(duì)p1中的每根導(dǎo)線發(fā)出T命令，若開(kāi)關(guān)狀態(tài)為閉合，且回答N,或者開(kāi)關(guān)狀態(tài)為斷開(kāi)，且回答Y,則移到p2。2遞歸過(guò)程check(p1,左區(qū)間,1-state)check(p2,右區(qū)間,state)3合并當(dāng)區(qū)間僅剩下一個(gè)開(kāi)關(guān)(hea

38、d=tail)且與之相連的導(dǎo)線集合p1非空，則p1中所有的導(dǎo)線與head相連,并使得ANSi=head,i屬于p1算法框架Procedure check(p1,head,tail,state);Begin if p1 then if head =tail then begin 計(jì)算左區(qū)間p1；通過(guò)c命令和用戶(hù)應(yīng)答，將左區(qū)間開(kāi)關(guān)狀態(tài)取反；右區(qū)間p2=；對(duì)p1中的每根導(dǎo)線發(fā)出T命令，若開(kāi)關(guān)狀態(tài)為閉合，且回答N,或者開(kāi)關(guān)狀態(tài)為斷開(kāi)，且回答Y,則移到p2； end;i:=trunc(head+tail)/2);check(p1,head,i,state);check(p2,i+1,tail,state

39、);End;【例12】最接近點(diǎn)對(duì)問(wèn)題【問(wèn)題描述】在應(yīng)用中，常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中的實(shí)體。在涉及這些幾何對(duì)象的問(wèn)題中，常需要了解其鄰域中其他幾何對(duì)象的信息。例如，在空中交通控制問(wèn)題中，若將飛機(jī)作為空間中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，則具有最大碰撞危險(xiǎn)的2架飛機(jī)，就是這個(gè)空間中最接近的一對(duì)點(diǎn)。這類(lèi)問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一。下面我們著重考慮平面上的最接近點(diǎn)對(duì)問(wèn)題。最接近點(diǎn)對(duì)問(wèn)題的提法是:給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最小。嚴(yán)格地說(shuō)，最接近點(diǎn)對(duì)可能多于1對(duì)。為了簡(jiǎn)單起見(jiàn)，這里只限于找其中的一對(duì)。（預(yù)備知識(shí)：在平面幾何中每一個(gè)點(diǎn)都用（x,

40、y）來(lái)表示它在平面中的位置，點(diǎn)1（x1,y1）與點(diǎn)2（x2,y2）之間的距離可用公式：表示）輸入：平面中各點(diǎn)的坐標(biāo)，以(0,0)表示輸入結(jié)束。輸出：距離最近的兩點(diǎn)坐標(biāo)。樣例輸入：7 2 2 7 3 4 9 7 0 0樣例輸出：the nearest length is:3.16 The first point is:2 2.00 7.00 The second point is:3 3.00 4.00問(wèn)題分析：常規(guī)分析中，我們通常是套用公式，求出所有點(diǎn)對(duì)之間的距離，然后用找最小值的方法進(jìn)行比較分析，從而找出距離最小的點(diǎn)對(duì)。這種方法稱(chēng)為直接分析法。使用這種方法優(yōu)點(diǎn)在于能找出所有的點(diǎn)對(duì)，比較穩(wěn)定；

41、缺點(diǎn)在于耗時(shí)太多，用數(shù)學(xué)方法分析一下，我們就會(huì)發(fā)現(xiàn)對(duì)于平面上的n個(gè)點(diǎn)，會(huì)產(chǎn)生n*(n-1)個(gè)點(diǎn)對(duì)，即需要求n*(n-1)次距離，就時(shí)間復(fù)雜性而言應(yīng)為o(n2)。對(duì)于n的值很小的時(shí)候可以這樣做，但隨著n值增大，計(jì)算機(jī)所花的計(jì)算時(shí)間將成倍地增加，很顯然這種算法是不可取的。不妨試著將大問(wèn)題規(guī)模縮小，將一個(gè)大問(wèn)題縮小為兩個(gè)小問(wèn)題，其中一個(gè)問(wèn)題（稱(chēng)為問(wèn)題A）大小為n/2，另一個(gè)問(wèn)題（稱(chēng)為問(wèn)題B）大小也為n/2。這樣出現(xiàn)最近點(diǎn)對(duì)的情況有可能是以下三種：情況1:兩個(gè)點(diǎn)都出現(xiàn)在A中；情況2:兩個(gè)點(diǎn)都出現(xiàn)在B中；情況3:一個(gè)點(diǎn)在A中，一個(gè)點(diǎn)在B中。分別找出這三種情況下的距離最近的點(diǎn)對(duì)，而最近的點(diǎn)對(duì)必定是這三種情

42、況下距離值最小的。對(duì)于情況1和情況2都可以遞歸地實(shí)現(xiàn)找距離最近的點(diǎn)對(duì)，對(duì)于情況3則需用另外的方法進(jìn)行判斷。這種方法取決于如何對(duì)A和B進(jìn)行劃分，一種合理的方法是在根據(jù)X坐標(biāo)的中間值處做一條垂線，垂線的左邊歸點(diǎn)集A，垂線的右邊歸點(diǎn)集B，在垂線線上點(diǎn)可以A，B之間分配以便滿(mǎn)足A，B的大小。因?yàn)閷?duì)于A中的任意一個(gè)點(diǎn)P，B中仍需用要n/2個(gè)點(diǎn)與之構(gòu)成候選點(diǎn)，這樣的思路勢(shì)必會(huì)導(dǎo)致耗時(shí)仍為o(n2)，因此我們應(yīng)該把注意力轉(zhuǎn)移到情況3上去。為了使問(wèn)題易于理解和分析，我們先來(lái)考慮一維的情形。如下圖所示，x軸上的n個(gè)實(shí)數(shù)x1,x2,xn。那么找最接近點(diǎn)對(duì)就是為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。我們顯然可以先將x1,

43、x2,xn排好序，然后，用一次線性?huà)呙杈涂梢哉页鲎罱咏c(diǎn)對(duì)，這種方法主要計(jì)算時(shí)間花在排序上，雖然這種方法無(wú)法適應(yīng)二維的情形，但是如果我們對(duì)這種一維的簡(jiǎn)單情形試用分治法來(lái)求解，那么就有可能推廣到二維的情形。BmAP3P2Q3Q1Q2P1根據(jù)某一種方法，我們找出了劃分兩個(gè)子集的分割點(diǎn)m，假設(shè)已經(jīng)找到A集中的最小點(diǎn)對(duì)距離為s1，B集中的最小點(diǎn)對(duì)距離為s2，又設(shè)在兩種情況下的最小點(diǎn)對(duì)距離為g，顯然，g=min(s1,s2)。而第三種情況（即跨越兩個(gè)子集）只需找出s1中坐標(biāo)的最大值點(diǎn)p3和s2中坐標(biāo)的最小值點(diǎn)q3，然后求出p3和q3之間的距離，可以得出g最終應(yīng)是s1,s2，q3-p3的最小值。通過(guò)分治算法，我們可以把時(shí)間復(fù)雜度降低到o(n)。至此，問(wèn)題的關(guān)鍵轉(zhuǎn)化為如何確定分割點(diǎn)m及A和B兩個(gè)數(shù)集的劃分。明顯地，如果通過(guò)m點(diǎn)，將兩個(gè)數(shù)集的規(guī)模劃分相等無(wú)疑是最佳的。涉及的數(shù)據(jù)為x:array1.50 of real;存放點(diǎn)的坐標(biāo)程序分