分治策略ppt課件

1、分治算法教案長沙市雅禮中學 朱全民問題1：找出偽幣給他一個裝有1 6枚硬幣的袋子。1 6枚硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。他的義務是找出這枚偽造的硬幣。為了協(xié)助他完成這一義務，將提供一臺可用來比較兩組硬幣分量的儀器，比如天平。利用這臺儀器，可以知道兩組硬幣的分量能否一樣。 方法1恣意取1枚硬幣，與其他硬幣進展比較，假設發(fā)現(xiàn)輕者，這那枚為偽幣。最多能夠有15次比較。 方法2將硬幣分為8組，每組2個，每組比較一次，假設發(fā)現(xiàn)輕的，那么為偽幣。最多能夠有8次比較。 方法3分析上述三種方法,分別需求比較15次,8次,4次,那么構成比較次數(shù)差別的根本緣由在哪里?方法1:每枚硬幣

2、都至少進展了一次比較,而有一枚硬幣進展了15次比較方法2:每一枚硬幣只進展了一次比較方法3:將硬幣分為兩組后一次比較可以將硬幣的范圍減少到了原來的一半,這樣充分地利用了只需1枚偽幣的根本性質。問題2：金塊問題有一個老板有一袋金塊。每個月將有兩名雇員會因其優(yōu)良的表現(xiàn)分別被獎勵一個金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據(jù)這種方式，除非有新的金塊參與袋中，否那么第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。假設有新的金塊周期性的參與袋中，那么每個月都必需找出最輕和最重的金塊。假設有一臺比較分量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金

3、塊。方法1 假設袋中有n 個金塊。可以用函數(shù)M a x經(jīng)過n-1次比較找到最重的金塊。找到最重的金塊后，可以從余下的n-1個金塊中用類似的方法經(jīng)過n-2次比較找出最輕的金塊。這樣，比較的總次數(shù)為2n-3。算法如下：max:=a1;min:=a1;for i:=2 to n do 2n-2次比較begin if aimax then max:=ai; if aimax then begin max:=ai; j:=i end;for i:=j+1 to n do ai-1:=ai; 去掉最大的數(shù)ajmin:=a1;for i:=2 to n-1 do n-2次比較，從剩下的元素中找最小的if a

4、imax then min:=ai;找金塊的例如圖方法2：n2，識別出最重和最輕的金塊，一次比較就足夠了。n2，第一步，把這袋金塊平分成兩個小袋A和B。第二步，分別找出在A和B中最重和最輕的金塊。設A中最重和最輕的金塊分別為HA 與LA，以此類推，B中最重和最輕的金塊分別為HB 和LB。第三步，經(jīng)過比較HA 和HB，可以找到一切金塊中最重的；經(jīng)過比較LA 和LB，可以找到一切金塊中最輕的。在第二步中，假設n2，那么遞歸地運用分而治之方法。分治過程比較過程分析從圖例可以看出，當有8個金塊的時候，方法1需求比較1516次，方法2只需求比較10次,那么構成比較次數(shù)差別的根本緣由在哪里?其緣由在于方法

5、2對金塊實行了分組比較。對于N枚金塊，我們可以推出比較次數(shù)的公式：假設n是2的次冪，c(n)為所需求的比較次數(shù)。方法1： c(n)=2n-1方法2：c(n) = 2c(n/2 ) + 2。由c(2)=1, 運用迭代方法可知c(n) = 3n/2 - 2。在本例中，運用方法2比如法1少用了2 5的比較次數(shù)。 證明令n=2kC(2K)=2C(2K-1)+2 =22C(2K-2)+2+2=22+2+22C(2K-2) =22+2+22C(2K-3)+2=23+22+2+23C(2K-3) = 2K-1+2K-2+2+2K-1C(2) =2K-1+2K-2+2+2K-1 =2K-2+2K-1C(n)=

6、3n/2 -2分治思想分治(divide-and-conquer)就是“分而治之的意思，其本質就是將原問題分成n個規(guī)模較小而構造與原問題類似的子問題；然后遞歸地解這些子問題，最后合并其結果就得到原問題的解。當n=2時的分治法又稱二分法。其三個步驟如下；分解(Divide)：將原問題分成一系列子問題。處理(Conquer)：遞歸地解各子問題。假設子問題足夠小，那么可直接求解。合并(combine)；將子問題的結果合并成原問題的解。 分治思想問題S問題S問題SS的解問題S1問題S2問題Si問題SnS1的解S2的解Si的解Sn的解問題的分解子集解的合并子問題求解分治思想由分治法所得到的子問題與原問題

7、具有一樣的類型。假設得到的子問題相對來說還太大，那么可反復運用分治戰(zhàn)略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出不用進一步細分就可求解的子問題。分治求解可用一個遞歸過程來表示。要使分治算法效率高，關鍵在于如何分割？普通地，出于一種平衡原那么，總是把大問題分成K個規(guī)模盡能夠相等的子問題，但也有例外，如求表的最大最小元問題的算法，當n6時，等分定量成兩個規(guī)模為3的子表L1和L2不是最正確分割。分治戰(zhàn)略的解題思緒 if 問題不可分then begin 直接求解； 前往問題的解；end else begin 對原問題進展分治； 遞歸對每一個分治的部分求解 歸并整個問題，得出全問題的解；end;有形

8、如：ax3+bx2+cx+d=0這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d均為實數(shù))，并商定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值=1。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并準確到小數(shù)點后4位。提示：記方程f(x)=ax3+bx2+cx+d，假設存在2個數(shù)x1和x2，且x1x2，f(x1)*f(x2)0，那么在(x1，x2)之間一定有一個根。樣例輸入：1 -5 -4 20輸出：-2.00 2.00 5.00問題3:一元三次方程求解分析假設準確到小數(shù)點后兩位，可用簡單的枚舉法：將x從-100.00 到100.0

9、0步長0.01 逐一枚舉，得到20000個 f(x)，取其值與0最接近的三個f(x)，對應的x即為答案。而標題已改成精度為小數(shù)點后4位，枚舉算法時間復雜度將達不到要求。直接運用求根公式，極為復雜。加上此題的提示給我們以啟迪：采用二分法逐漸減少根的范圍，從而得到根的某精度的數(shù)值分析A、當知區(qū)間(a,b)內(nèi)有一個根時，用二分法求根，假設區(qū)間(a,b)內(nèi)有根，那么必有f(a)f(b)b或f(a+b)/2)=0，那么可確定根為(a+b)/2并退出過程； (2)假設f(a)* f(a+b)/2)0 ，那么必然有f(a+b)/2)* f(b)=1。因此可知：在-100,-99、-99,-98、99，100

10、、100，100這201個區(qū)間內(nèi)，每個區(qū)間內(nèi)至多只能有一個根。即：除區(qū)間100，100外，其他區(qū)間a,a+1，只需當f(a)=0或f(a)f(a+1)0時，方程在此區(qū)間內(nèi)才有解。假設f(a)=0 ，解即為a；假設f(a)f(a+1)樞元素4. 移除右邊的索引直到我們得到一個元素=pivot的元素當我們得到一個元素=pivot時，運用index high從右邊掃描尋覓=pivot的元素假設low=high，那么完成我們需求做的，交換low和pivot的值，該值位于兩個分塊之間另一個分塊的實例當前pivot值原先的pivot值分塊交換pivot值交換較好的快速排序pivot值的選擇對快速排序具有決

11、議性的作用。 理想的pivot值是子數(shù)組的中間值，即是排序數(shù)組的中間組成。但是在排序之前我們無法得到中間值。 現(xiàn)實證明每個子數(shù)組的第一個，中間的和最后一個元素的中間值是上面所說的中間值的很好的替代。它保證分塊的每部分至少有兩個元素，提供數(shù)組至少有4個，但是它的執(zhí)行方式通常更好。并且沒有自然的情況會產(chǎn)生最壞的情況。其他改良： 從遞歸到疊代的轉化，更加有效率?？偸窍忍幹米疃痰淖訑?shù)組有限的棧大小，pop，push 當子數(shù)組足夠小5-25個元素運用插入排序，在小問題上它更快快速排序算法(分塊)問題5: 歸并排序知某數(shù)列存儲在序列A1，A2，An，現(xiàn)需求采用分治戰(zhàn)略對它們進展從大到小從小到大排序。例如：

12、 5 2 4 6 2 3 2 6排序后為 6 6 5 4 3 2 2 2歸并排序的整個過程歸并過程procedure Merge(var A: ListType; P, Q, R: Integer); 將AP.Q和AQ+1.R，合并到序列AP.R var I, J, 左右子序列指針 T: Integer;合并后的序列的指針 Lt: ListType; 暫存合并的序列 begin T:= P; I := P; J := Q + 1; while T = R do begin合并未完成 if (I R) or (AI = AJ) then begin Ltt := AI; Inc(I); end

13、else begin否那么右序列的首元素進入合并序列 Ltt := AJ; Inc(J); end; Inc(T);合并后的序列的指針右移 end; A := Lt;合并后的序列賦給A end;二分過程procedure Merge_Sort(var A: ListType; P, R: Integer); var Q: Integer; begin if P R then begin 假設子序列A中不止一個元素 Q := (P + R - 1) div 2; 計算中間下標Q Merge_Sort(A, P, Q); 繼續(xù)對左子序列遞歸排序 Merge_Sort(A, Q + 1, R); 繼

14、續(xù)對右子序列遞歸排序 Merge(A, P, Q, R) 對左右子序列歸并 end;end;問題6:求逆序對個數(shù)有一實數(shù)序列A1、A2 、A3 、An-1 、An，假設iAj，那么稱Ai與Aj構成了一個逆序對，求數(shù)列A中逆序對的個數(shù)。n10000。例如，5 2 4 6 2 3 2 6，可以組成的逆序對有 5 2，5 4，5 2，5 3，5 2， 4 2，4 3，4 2， 6 2，6 3，6 2， 3 2共：12個分析在看完試題以后，我們不難想到一個非常簡單的算法窮舉算法，即對數(shù)組中恣意的兩個元素進展判別，看它們是不是構成“逆序對，因此這種算法的時間復雜度為O(N2)。 時間效率不盡如人意.問題

15、出如今哪里呢？ 轉換思想用分治怎樣樣?首先將這一序列A一分為二，分成兩個不同的序列B、C假設求出了B,C的逆序對,那么可由B,C求出A的逆序對.如何來統(tǒng)計序列B和序列C之間的“逆序對呢？ 假設還按照窮舉的思想來統(tǒng)計的話，那么我們采用分治法就沒有什么意義!提示在遞歸的求解B、C兩個序列中的逆序對的個數(shù)以后，假設對B、C兩個序列當中的元素進展排序的話，要統(tǒng)計B、C兩個序列之間的“逆序對是非常容易的.如圖排序前排序后在B數(shù)組當中，首先，B中的6，5，4都與C數(shù)組當中的3，2，2都構成了“逆序對，而2不會構成逆序對，因此B、C兩個數(shù)組之間構成的逆序對的個數(shù)為3+3+3=9。結論由于B、C兩個數(shù)組曾經(jīng)進

16、展了排序，因此可以設置兩個指針進展操作，有效的統(tǒng)計B、C兩個數(shù)組之間的“逆序對的個數(shù)。而且這一統(tǒng)計步驟是可以在線性時間內(nèi)完成的。思索到我們設計的二分模型本身是遞歸定義的，所以可以將我們所建立的二分模型完全與歸并排序聯(lián)絡起來。由于排序的過程是可以在遞歸求解子問題時就可以完成的，算法的時間復雜度就降到了O(nlogn)。在這里，雖然對B、C兩個序列當中的元素進展了排序，使得序列A當中某一部分元素的順序被打亂了，但由于求解過程是遞歸定義的，在排序之前B、C兩個序列各自其中的元素之間的“逆序對個數(shù)曾經(jīng)被統(tǒng)計過了，并且排不排序對統(tǒng)計B、C兩個數(shù)組之間的“逆序對的個數(shù)不會產(chǎn)生影響。所以這個排序過程對整個問

17、題的求解的正確性是沒有任何影響的?？偨Y歸納分治是一種解題的戰(zhàn)略，它的根本思想是：“假設整個問題比較復雜，可以將問題分化，各個擊破。分治包含“分和“治兩層含義，如何分，分后如何“治成為處理問題的關鍵所在不是一切的問題都可以采用分治，只需那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質的問題，才干進展分治分治可進展二分，三分等等，詳細怎樣分，需看問題的性質和分治后的效果。只需深化地領會分治的思想，仔細分析分治后能夠產(chǎn)生的預期效率，才干靈敏地運用分治思想處理實踐問題。思索題1: 剔除多余括號 輸入一個含有括號的四那么運算表達式，能夠含有多余的括號，編程整理該表達式，去掉一切多余的括號

18、，原表達式中一切變量和運算符相對位置堅持不變，并堅持與原表達式等價。表達式以字符串輸入，長度不超越255，輸入不需求判錯。一切變量為單個小寫字母。只是要求去掉一切多余括號，不要求對表達式簡化。樣例:輸入表達式應輸出表達式a+b(+c)a+b+c(a*b)+c/(d*e)a*b+a/(d*e)a+b/(c-d)a+b/(c-d)分析對于四那么運算表達式，我們分析一下哪些括號可以去掉。設待整理的表達式為s1 op s2；op為括號內(nèi)優(yōu)先級最低的運算符“+，“-或“*，“/；左鄰括號的運算符為“/，那么括號必需保管，即 /s1 op s2 方式。左鄰括號的預算符為“*或“-。而op為“+或“-，那么

19、保管括號，即*s1+s2 或 -s1+s2 或 *s1-s2 或 -s1-s2右鄰括號的運算符為“*或“/，而op為“+或“-，原式中的op運算必需優(yōu)先進展，因此括號不去除，即s1+s2* 除上述情況外，可以括號去除，即 s1 op s2 等價于s1 op s2我們從最里層嵌套的括號開場，根據(jù)上述規(guī)律逐漸向外進展括號整理，直至最外層的括號保管或去除為止。這個整理過程可以用一個遞歸過程來實現(xiàn)。剔除“(a+b)*f)-(i/j)中多余的括號 思索題2:導線和開關如上圖是一個具有3根導線的電纜把A區(qū)和B區(qū)銜接起來。在A區(qū)3根導線標以1，2，3;在B區(qū)導線1和被連到開關3，導線2連到開關1。 普通說來

20、，電纜含(1 90)根導線，在A區(qū)標以1,2,m。在B 區(qū)有個開關，標為1，2， ，。每一根導線都被嚴厲地連到這些開關中的某一個上; 每一個開關上可以連有0根或多根導線。問題描畫丈量他的程序應作某些丈量來確定，導線和開關怎樣連。 每個開關或處于接通或處于斷開形狀，開關的初始形狀為斷開。我們可用一個探頭P在A區(qū)進展測試:假設探頭點到某根導線上，當且僅當該導線連四處接通形狀的開關時，燈L才會點亮。他的程序從規(guī)范輸入讀入一行以得到數(shù)字;然后可以經(jīng)過向規(guī)范輸出寫入一行以發(fā)出命令(共3種命令)。每種命令的開頭是一個大寫字母:測試導線命令T:T后面跟一個導線標號;改動開關形狀命令C:C后面跟一個開關標號;

21、完成命令D:D后面跟的是一個表列LIST，該表列中的第個元素代表與導線相連的開關號。在命令T和C之后，他的程序應從規(guī)范輸入standard input讀入一行。 假設開關形狀能使燈亮，那么命令T的回答應是Y;反之，回答應是N。命令C的作用是改動開關的形狀假設原來是接通那么變?yōu)閿嚅_;假設原來是斷開那么變?yōu)榻油?。對C命令的回答是作為一種反響信號。他的程序可以給出一系列命令，將T命令與C命令以恣意順序混合運用。最后給出命令D，并終了。他的程序給出的命令總數(shù)應不大于900。樣例Standard OutputStandard InputC 3 T 1 T 2 T 3 C 3 C 2 T 2 D 3 1

22、33YYNYNYN分析為了使導線和開關的銜接任務有規(guī)律地進展，我們無妨采用二分法。1.分解設當前待接的開關為head.tail,初始時為1.m,那么左區(qū)間head.(head+tail-1)/2, 開關集合為p1=1.m右區(qū)間 (head+tail-1)/2+1.tail, 開關集合為p2=導線的銜接形狀state=(0,1)，分別表示斷開和銜接對區(qū)間進展檢測，對p1中的每根導線發(fā)出T命令，假設開關形狀為閉合，且回答N,或者開關形狀為斷開，且回答Y,那么移到p22. 遞歸過程check(p1,左區(qū)間,1-state)check(p2,右區(qū)間,state)3. 合并當區(qū)間近近剩下一個開關(head=tail)且與之相連的導線集合p1非空，那么p1中一切的導線與head相連,并使得ANSi=head,i屬于p1算法框架Procedure check(p1,head,tail,state);Begin if p1 then if head =tail then begin 計算左區(qū)間p1；經(jīng)過c命令和用戶應對，將左區(qū)間開關形狀取反；右區(qū)間p2=；對p1中的每根導線發(fā)出T命令，假設開關形狀為閉合，且回答N,