基礎(chǔ)算法5-分治法

基礎(chǔ)算法——分治法一、分治思想分治法，又叫分治策略，顧名思義，分而治之。它的基本思想：對(duì)于難以直接解決的規(guī)模較大的問題，把它分解成若干個(gè)能直接解決的相互獨(dú)立的子問題，遞歸求出各子問題的解，再合并子問題的解，得到原問題的解。通過減少問題的規(guī)模，逐步求解，能夠明顯降低解決問題的復(fù)雜度。二、分治法的適用條件使用分治法解決問題，一般分為三個(gè)步驟：①分解（Divide）：將要解決的問題分解成若干個(gè)規(guī)模較小的同類子問題；②解決（Conquer）：當(dāng)子問題劃分得足夠小時(shí)，求解出子問題的解。③合并（Combine）：將子問題的解逐層合并成原問題的解。分治法在信息學(xué)競(jìng)賽中應(yīng)用非常廣泛，使用分治策略能生成一些常用的算法和數(shù)據(jù)結(jié)構(gòu)，如快排、最優(yōu)二叉樹、線段樹等；還可以直接使用分治策略，解決一些規(guī)模很大、無(wú)法直接下手的問題。分治算法設(shè)計(jì)過程圖在劃分問題時(shí)，可以采用遞歸策略，把一個(gè)大問題逐步分解成規(guī)模較小的子問題，直至可以直接求出子問題的解；再將子問題逐層合并，返回到頂層，得到原問題的解。根據(jù)分治策略的劃分原則，一般把原問題每次劃分成2個(gè)子問題、每個(gè)子問題的規(guī)模差不多最合適。合并解時(shí)要因題而異，有些問題遞歸分解完能直接得到原問題的解，有些問題需逐層合并，得到原問題的解。四、分治的框架結(jié)構(gòu)procedureDivide()beginif(問題不可分)then//解決begin

直接求解；返回問題的解；endelsebegin

對(duì)原問題進(jìn)行分治；//分解遞歸對(duì)每一個(gè)分治的部分進(jìn)行求解;//解決

歸并整個(gè)問題，得出全問題的解;//合并

endend;1、求最大值和最小值例題1：給n個(gè)數(shù)，求它們之中最大值和最小值，要求比較次數(shù)盡量小。分析：假設(shè)數(shù)據(jù)個(gè)數(shù)為n,存放在數(shù)組a[1..n]中。可以直接進(jìn)行比較：

minn:=a[1];maxx:=a[1];fori:=2tondoifa[i]>maxxthenmaxx:=a[i];elseifa[i]<minnthenminn:=a[i];使用這一算法，比較次數(shù)為2(n-1)。若n=10,則比較18次?！痉椒?】分治策略劃分：把n個(gè)數(shù)均分為兩半。即：劃分點(diǎn)為d=(r1+r2)div2，兩個(gè)區(qū)間為[r1,d]和[d+1,r2]。遞歸求解：求左半的最小值min1和最大值max1以及右半最小值min2和最大值max2。合并：max1與max2比較得到所有數(shù)的最大值為maxx；min1與min2比較得到所有數(shù)的最小值為minn。若n=10，則只要比較9次就可以。programmaxmin;varx:array[1..100]ofinteger;

i,n,max,min:integer;procedurepd(r1,r2:integer;varmaxx,minn:integer);vard,min1,min2,max1,max2:integer;beginifr1=r2then{如果只有一個(gè)數(shù)}begin

maxx:=x[r1];

minn:=x[r1];endelseifr2=r1+1then{如果有兩個(gè)數(shù)}beginifx[r2]>x[r1]thenbegin

maxx:=x[r2];

minn:=x[r1];endelsebegin

maxx:=x[r1];

minn:=x[r2];endendelsebegind:=(r1+r2)div2;{找到中間位置}pd(r1,d,max1,min1);{比較第一段的值}pd(d+1,r2,max2,min2);{比較第二段的值}ifmax1>max2thenmaxx:=max1{求出最大值}elsemaxx:=max2;ifmin1<min2thenminn:=min1{求出最小值}elseminn:=min2;end;end;begin

write('inputn:');{輸入數(shù)值個(gè)數(shù)}

readln(n);fori:=1tondoread(x[i]);{輸入n個(gè)數(shù)}pd(1,n,max,min);{開始比較}

write('max=',max,',min=',min);{輸出結(jié)果}end.參考代碼2、求方程的根例題2：一元三次方程求解（NOIP2001）【題目描述】有形如：ax3+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)后4位?！疚募斎搿枯斎雰H一行，有四個(gè)數(shù)，依次為a、b、c、d【文件輸出】輸出也只有一行，即三個(gè)根(從小到大輸出)【樣例輸入】1-5-420【樣例輸入】-2.00002.00005.0000分析如果精確到小數(shù)點(diǎn)后兩位，可用簡(jiǎn)單枚舉法：將x從-100.00到100.00（步長(zhǎng)0.01）逐一枚舉，得到20000個(gè)f(x)，取其值與0最接近的三個(gè)f(x)，對(duì)應(yīng)的x即為答案。而題目已改成精度為小數(shù)點(diǎn)后4位，枚舉算法時(shí)間復(fù)雜度將達(dá)不到要求。直接使用求根公式，極為復(fù)雜。加上本題的提示給我們以啟迪：采用二分法逐漸縮小根的范圍，從而得到根的某精度的數(shù)值。分析A.當(dāng)已知區(qū)間(a,b)內(nèi)有一個(gè)根時(shí)；用二分法求根，若區(qū)間(a,b)內(nèi)有根，則必有f(a)*f(b)<0。重復(fù)執(zhí)行如下的過程：

①、若a+0.0001>b或f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程；

②、若f(a)*f((a+b)/2)<0,則由題目給出的定理可知根在區(qū)間(a,(a+b)/2)中,故對(duì)區(qū)間重復(fù)該過程；

③、若f(a)*f((a+b)/2)>0,則必然有f((a+b)/2)*f(b)<0,根在((a+b)/2,b)中,對(duì)此區(qū)間重復(fù)該過程。執(zhí)行完畢,就可以得到精確到0.0001的根。分析B、求方程的所有三個(gè)實(shí)根所有的根的范圍都在-100至100之間，且根與根之差的絕對(duì)值>=1。因此可知：在[-100,-99]、[-99,-98]、……、[99，100]、[100，100]這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能有一個(gè)根。即：除區(qū)間[100，100]外，其余區(qū)間[a,a+1]，只有當(dāng)f(a)=0或f(a)*f(a+1)<0時(shí)，方程在此區(qū)間內(nèi)才有解。若f(a)=0，解即為a；若f(a)*f(a+1)<0，則可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。programfangcheng;var

a,b,c,d,x,p,q:real;anx:array[1..3]ofreal;

i,t:integer;functionf(x:real):real;{計(jì)算f(x)的值}beginf:=((a*x+b)*x+c)*x+d;end;functionfindx(i:real):real;{用分治法在已知有根的區(qū)間[i,i+1]里找到一個(gè)解}beginp:=i;{從i開始找起}q:=p+0.99999;{在誤差范圍內(nèi)，q近似等于i+1}ifabs(f(p))<0.00001thenfindx:=p{當(dāng)f(x)的值誤差小于小數(shù)點(diǎn)后4位則得到一個(gè)解p}elsebeginwhile(p+0.0001<q)and(f((p+q)/2)<>0)do{p小于q且中間值計(jì)算結(jié)果不為0}iff(p)*f((p+q)/2)<0{如果解在[p,(p+q)/2]區(qū)間內(nèi)}thenq:=(p+q)/2{開始在[p,(p+q)/2]區(qū)間內(nèi)找解}elsep:=(p+q)/2;{否則在[(p+q)/2,q]區(qū)間內(nèi)找解}

findx:=(p+q)/2;{每次都二分查找值}end;end;begin

read(a,b,c,d);t:=0;{t為解的個(gè)數(shù)}fori:=-100to100dobeginif(abs(f(i))<0.00001)or(f(i)*f(i+0.99999)<=