1、 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):理解遞歸的概念。理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。掌握設(shè)計(jì)有效算法的分治策略。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)；）二分搜索技術(shù)； （2）大整數(shù)乘法；）大整數(shù)乘法；（3）棋盤(pán)覆蓋；）棋盤(pán)覆蓋；（4）合并排序和快速排序；）合并排序和快速排序；（5）循環(huán)賽日程表。）循環(huán)賽日程表。n將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n對(duì)這對(duì)這k k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為小，則再

2、劃分為k k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。到問(wèn)題規(guī)模足夠小，很容易求出其解為止。n對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) n將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)

3、更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。題的解，自底向上逐步求出原來(lái)問(wèn)題的解。n將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n

4、/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊，以便各個(gè)擊破，破，分而治之分而治之。 分而治之方法法與軟件設(shè)計(jì)的模塊化方法非常相分而治之方法法與軟件設(shè)計(jì)的模塊化方法非常相似。為解決一個(gè)大問(wèn)題，可以（似。為解決一個(gè)大問(wèn)題，可以（1 1）把它分解成兩個(gè)或）把它分解成兩個(gè)或多個(gè)更小的問(wèn)題；（多個(gè)更小的問(wèn)題；（2 2）分別解決每個(gè)小問(wèn)題；（）分別解決每個(gè)小問(wèn)題；（3 3）

5、把各小問(wèn)題的解答組合起來(lái)，即可得到原問(wèn)題的解。把各小問(wèn)題的解答組合起來(lái)，即可得到原問(wèn)題的解。 小問(wèn)題通常與原問(wèn)題相似或同質(zhì)小問(wèn)題通常與原問(wèn)題相似或同質(zhì) ，因而可以遞歸，因而可以遞歸地使用分而治之策略解決。地使用分而治之策略解決。 2.1 n直接或間接地調(diào)用自身的算法稱為直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。n由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與情況下

6、，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。致遞歸過(guò)程的產(chǎn)生。n分治與遞歸像一對(duì)孿生兄弟分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。下面來(lái)看幾個(gè)實(shí)例。2.1 例例1 1 階乘函數(shù)階乘函數(shù) 階乘函數(shù)可遞歸地定義為階乘函數(shù)可遞歸地定義為：10!(1)!0nnn nn=- 邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸

7、函邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果結(jié)果。2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程10( )11(1)(2)1nF nnF nF nn=-+- 第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n =2) return (n+2);return akm(akm(n-1,m),m-1);2

8、.1 例例4 4 排列問(wèn)題排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成設(shè)計(jì)一個(gè)遞歸算法生成n n個(gè)元素個(gè)元素rr1 1,r,r2 2,r,rn n 的全排列。的全排列。設(shè)設(shè)R=rR=r1 1,r,r2 2,r,rn n 是要進(jìn)行排列的是要進(jìn)行排列的n n個(gè)元素，個(gè)元素，R Ri i=R-r=R-ri i 。集合集合X X中元素的全排列記為中元素的全排列記為perm(X)perm(X)。(r(ri i)perm(X)perm(X)表示在全排列表示在全排列perm(X)perm(X)的每一個(gè)排列前加上前的每一個(gè)排列前加上前綴得到的排列。綴得到的排列。R R的全排列可歸納定義如下：的全排列可歸納定義如下： 當(dāng)當(dāng)n=

9、1n=1時(shí)，時(shí)，perm(R)=(r)perm(R)=(r)，其中，其中r r是集合是集合R R中唯一的元素；中唯一的元素；當(dāng)當(dāng)n1n1時(shí)，時(shí)，perm(R)perm(R)由由(r(r1 1)perm(R)perm(R1 1) )，(r(r2 2)perm(R)perm(R2 2) )，(r(rn n)perm(R)perm(Rn n) )構(gòu)成。構(gòu)成。 程序清單程序清單2.1 例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題將正整數(shù)將正整數(shù)n n表示成一系列正整數(shù)之和：表示成一系列正整數(shù)之和：n=nn=n1 1+n+n2 2+n+nk k，其中其中n n1 1nn2 2nnk k11，k1k1。正整數(shù)正整

10、數(shù)n n的這種表示稱為正整數(shù)的這種表示稱為正整數(shù)n n的劃分。求正整數(shù)的劃分。求正整數(shù)n n的不的不同劃分個(gè)數(shù)。同劃分個(gè)數(shù)。 例如正整數(shù)例如正整數(shù)6 6有如下有如下1111種不同的劃分：種不同的劃分： 6 6； 5+15+1； 4+24+2，4+1+14+1+1； 3+33+3，3+2+13+2+1，3+1+1+13+1+1+1； 2+2+22+2+2，2+2+1+12+2+1+1，2+1+1+1+12+1+1+1+1； 1+1+1+1+1+11+1+1+1+1+1。例例5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題n下面介紹一種通過(guò)遞歸方法得到一個(gè)正整數(shù)的劃分?jǐn)?shù)。n 遞歸函數(shù)的聲明為 int split(in

11、t n, int m);其中n為要?jiǎng)澐值恼麛?shù)，m是劃分中的最大加數(shù)(當(dāng)m n時(shí)，最大加數(shù)為n)，n 1、當(dāng)n = 1或m = 1時(shí)，split的值為1，可根據(jù)上例看出，只有一個(gè)劃分1 或 1 + 1 + 1 + 1 + 1 + 1n 可用程序表示為: if(n = 1 | m = 1) return 1;例例5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題n2、下面看一看m 和 n的關(guān)系。它們有三種關(guān)系n (1) m nn 在整數(shù)劃分中實(shí)際上最大加數(shù)不能大于n，因此在這種情況可以等價(jià)為split(n, n);n 可用程序表示為: if(m n) return split(n, n); n (2) m = nn

12、這種情況可用遞歸表示為split(n, m - 1) + 1，從以上例子中可以看出，就是最大加數(shù)為6和小于6的劃分之和n 用程序表示為: if(m = n) return (split(n, m - 1) + 1);例例5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題n(3) m m) return (split(n, m - 1) + split(n - m), m);(2) q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即111nn =+ (4) q(n,m)=q(n,m-1)+q

13、(n-m,m), nm1;(4) q(n,m)=q(n,m-1)+q(n-m,m), nm1;正整數(shù)正整數(shù)n n的最大加數(shù)的最大加數(shù)n n1 1不大于不大于m m的劃分由的劃分由n n1 1=m=m的劃分和的劃分和n n1 1m-1 m-1 的劃分組成。的劃分組成。例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)在本例中，如果設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加

14、一個(gè)自變量：將最大加數(shù)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n n1 1不大于不大于m m的劃分個(gè)的劃分個(gè)數(shù)記作數(shù)記作q(n,m)q(n,m)?？梢越ⅰ？梢越(n,m)q(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。(3) q(n,n)=1+q(n,n-1);(3) q(n,n)=1+q(n,n-1);正整數(shù)正整數(shù)n n的劃分由的劃分由n n1 1=n=n的劃分和的劃分和n n1 1n-1n-1的劃分組成的劃分組成。11,1( , )( ,)1( ,1)( ,1)(,)1nmq n nnmq n mq n nnmq n mq nm mnm=例例5 5 整數(shù)劃分問(wèn)題整數(shù)劃分問(wèn)題前面的幾個(gè)例子中

15、，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)在本例中，如果設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n n1 1不大于不大于m m的劃分個(gè)的劃分個(gè)數(shù)記作數(shù)記作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。正整數(shù)正整數(shù)n n的劃分?jǐn)?shù)的劃分?jǐn)?shù)p(n)=q(n,n)p(n)=q(n,n)。 例例5 整數(shù)劃分問(wèn)

16、題整數(shù)劃分問(wèn)題n int split(int n, int m)n n if(n 1 | m 1) return 0;n if(n = 1 | m = 1) return 1;n if(n m) return (split(n, m - 1) + split(n - m), m);n n在印度，有這么一個(gè)古老的傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面

17、。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。 2.1 2.1 例例6 Hanoi6 Hanoi塔問(wèn)題塔問(wèn)題設(shè)設(shè)a,b,ca,b,c是是3 3個(gè)塔座。開(kāi)始時(shí)，在塔座個(gè)塔座。開(kāi)始時(shí)，在塔座a a上有一疊共上有一疊共n n個(gè)圓盤(pán)，這個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為為1,2,n,1,2,n,現(xiàn)要求將塔座現(xiàn)要求將塔座a a上的這一疊圓盤(pán)移到塔座上的這一疊圓盤(pán)移到塔座b b上，并仍上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：

18、按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則規(guī)則1 1：每次只能移動(dòng)：每次只能移動(dòng)1 1個(gè)圓盤(pán)；個(gè)圓盤(pán)；規(guī)則規(guī)則2 2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則規(guī)則3 3：在滿足移動(dòng)規(guī)則：在滿足移動(dòng)規(guī)則1 1和和2 2的前提下，可將圓盤(pán)移至的前提下，可將圓盤(pán)移至a,b,ca,b,c中中任一塔座上。任一塔座上。在問(wèn)題規(guī)模較大時(shí)，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單。此時(shí)，只要將編號(hào)為1的圓盤(pán)從塔座a直接移至塔座b上即可。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)較

19、小的圓盤(pán)依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤(pán)從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤(pán)的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題的遞歸算法如下。2.1 例例6 Hanoi6 Hanoi塔問(wèn)題塔問(wèn)題 void hanoi(int n, char a, char b, char c) if (n 0) hanoi(n-1, a, c, b);/把a(bǔ)上n-1個(gè)盤(pán)子借助b移到c上 move(a,b); hanoi(n-1, c, b, a); n漢諾塔問(wèn)題漢諾塔

20、問(wèn)題nvoid Move(char x, char y)n /將第將第n個(gè)圓盤(pán)從塔座個(gè)圓盤(pán)從塔座x移到塔座移到塔座y的頂部的頂部ncout The disk is moved from n x y endl; n2.1 程序n思考：n移動(dòng)次數(shù)和n的關(guān)系？2.1 優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比耗費(fèi)的計(jì)算時(shí)間還是

21、占用的存儲(chǔ)空間都比非遞歸算法要多。非遞歸算法要多。解決方法：解決方法：在遞歸算法中消除遞歸調(diào)用，使其在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。轉(zhuǎn)化為非遞歸算法。1 1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。優(yōu)化效果不明顯。2 2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3 3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為非遞歸，從而、通過(guò)變換能將一些遞歸轉(zhuǎn)化為非遞歸，從而迭代求出結(jié)果。迭

22、代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。n該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；n該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)n利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；解；n該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。題之間不包含公共的子

23、問(wèn)題。 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法貪心算法或動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃較好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)題 divide P in

24、to smaller subinstances P1,P2,.,Pk；/分解問(wèn)題 for (i=1,i 注意注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。 分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無(wú)論是

25、在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前的前面或后面查找面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。用條件。給定已按升序排好序的給定已按升序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個(gè)元素中找個(gè)元素中找出一特定元素出一特定元素x。分析：分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以

26、分解為若干個(gè)規(guī)模較小的相同問(wèn)題該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 給定已按升序排好序的給定已按升序排好序的n個(gè)元素個(gè)元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個(gè)元素中找個(gè)元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計(jì)出據(jù)此容易設(shè)計(jì)出二分搜索算法二分搜索算法：template int BinarySearch(Type a , const Type& x, int n) int left=0; int right=n-1;/在在a0=a1=

27、an-1中搜索中搜索x /找到找到x時(shí)返回其在數(shù)組中的位置，否則返回時(shí)返回其在數(shù)組中的位置，否則返回-1 while (left amiddle) left= middle+1; else right = middle-1; return -1;/未找到未找到x 算法復(fù)雜度分析：算法復(fù)雜度分析：每執(zhí)行一次算法的每執(zhí)行一次算法的while循環(huán)，循環(huán)， 待搜待搜索數(shù)組的大小減少一半。因此，在最索數(shù)組的大小減少一半。因此，在最壞情況下，壞情況下，while循環(huán)被執(zhí)行了循環(huán)被執(zhí)行了O(logn) 次。因此整個(gè)算法在最壞情次。因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為況下的計(jì)算時(shí)間復(fù)雜性為O(logn)

28、 。算法舉例leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92找找210 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid例例 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid找找70 0 1 2 3 4 5 6 7

29、8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92left rightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftrightmid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92leftright在一個(gè)在一個(gè)2k2k 個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它

30、方格不同，稱該方格為一特殊方格，且稱該棋盤(pán)為一特殊棋盤(pán)。在不同，稱該方格為一特殊方格，且稱該棋盤(pán)為一特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的種不同形態(tài)的L型骨牌覆蓋給定型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)個(gè)L型骨牌型骨牌不得重疊覆蓋。不得重疊覆蓋。當(dāng)當(dāng)k0k0時(shí)，將時(shí)，將2 2k k2 2k k棋盤(pán)分割為棋盤(pán)分割為4 4個(gè)個(gè)2 2k-1k-12 2k-1k-1 子棋盤(pán)子棋盤(pán)(a)(a)所示。所示。特殊方格必位于特殊方格必位于4 4個(gè)較小子棋盤(pán)之一中，其余個(gè)較小子棋盤(pán)之一中，其余3 3個(gè)子

31、棋盤(pán)中無(wú)特個(gè)子棋盤(pán)中無(wú)特殊方格。為了將這殊方格。為了將這3 3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，可以用一個(gè)以用一個(gè)L L型骨牌覆蓋這型骨牌覆蓋這3 3個(gè)較小棋盤(pán)的會(huì)合處，如個(gè)較小棋盤(pán)的會(huì)合處，如 (b) (b)所示，所示，從而將原問(wèn)題轉(zhuǎn)化為從而將原問(wèn)題轉(zhuǎn)化為4 4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地使用個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)1 11 1。 n 棋盤(pán)覆蓋【解題思路】：將2k x 2k的棋盤(pán)，先分成相等的四塊子棋盤(pán)，其中特殊方格位于四個(gè)中的一個(gè)，構(gòu)造剩下沒(méi)特殊方格三個(gè)子棋盤(pán)，將他們中的也假一個(gè)

32、方格設(shè)為特殊方格。如果是：n 左上的子棋盤(pán)（若不存在特殊方格）-則將該子棋盤(pán)右下角的那個(gè)方格假設(shè)為特殊方格n 右上的子棋盤(pán)（若不存在特殊方格）-則將該子棋盤(pán)左下角的那個(gè)方格假設(shè)為特殊方格n 左下的子棋盤(pán)（若不存在特殊方格）-則將該子棋盤(pán)右上角的那個(gè)方格假設(shè)為特殊方格n 右下的子棋盤(pán)（若不存在特殊方格）-則將該子棋盤(pán)左上角的那個(gè)方格假設(shè)為特殊方格n 當(dāng)然上面四種，只可能且必定只有三個(gè)成立，那三個(gè)假設(shè)的特殊方格剛好構(gòu)成一個(gè)L型骨架，我們可以給它們作上相同的標(biāo)記。這樣四個(gè)子棋盤(pán)就分別都和原來(lái)的大棋盤(pán)類(lèi)似，我們就可以用遞歸算法解決。 將棋盤(pán)保存在一個(gè)二維數(shù)組中。骨牌號(hào)從1開(kāi)始，特殊方格為0，如果是一個(gè)

33、4 * 4的棋盤(pán)，特殊方格為(2,2)，那么程序的輸出為 2 2 3 3 2 1 1 3 4 1 0 5 4 4 5 5 相同數(shù)字的為同一骨牌。void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤(pán) / 覆蓋左上角子棋盤(pán) if (dr tr + s & dc tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc, dr, dc, s); else / 此棋盤(pán)中無(wú)特殊方格 / 用

34、t 號(hào)L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤(pán) if (dr = tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤(pán)中無(wú)特殊方格 / 用 t 號(hào)L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤(pán) if (dr = tr + s

35、 & dc = tr + s & dc = tc + s) / 特殊方格在此棋盤(pán)中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號(hào)L型骨牌覆蓋左上角 boardtr + stc + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 復(fù)雜度分析復(fù)雜度分析解此遞歸方程,可得時(shí)間復(fù)雜度為:T(n)=O(4k)(1)0( )4 (1)(1)0OkT kT kOk=-+ 程序n分治法求解分治法求解 將待排序的元素序列一分為二分，得到兩個(gè)將待排序的元素序列一分為二分，得到兩個(gè)長(zhǎng)度基本

36、相等的子序列，如同對(duì)半搜索的做法；長(zhǎng)度基本相等的子序列，如同對(duì)半搜索的做法；然后對(duì)兩個(gè)子序列分別排序，如果子序列較長(zhǎng)，然后對(duì)兩個(gè)子序列分別排序，如果子序列較長(zhǎng)，還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)還可繼續(xù)細(xì)分，直到子序列的長(zhǎng)度不超過(guò)1 1為止；為止；當(dāng)分解所得的子序列已排列有序，可以將兩個(gè)有當(dāng)分解所得的子序列已排列有序，可以將兩個(gè)有序子序列，合并成一個(gè)有序子序列的方法，實(shí)現(xiàn)序子序列，合并成一個(gè)有序子序列的方法，實(shí)現(xiàn)將子問(wèn)題的解組合成原問(wèn)題解，這是分治法不可將子問(wèn)題的解組合成原問(wèn)題解，這是分治法不可缺少的一步。缺少的一步。void MergeSort(Type a, int left, int

37、right) if (leftright) /至少有2個(gè)元素 int i=(left+right)/2; /取中點(diǎn) mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); /合并到數(shù)組b copy(a, b, left, right); /復(fù)制回?cái)?shù)組a nvoid Merge(Type c,Type d,int left,int m,int right )nn int i=left,j=m+1,k=left;n while(i=m)&(j=right)/從小到大的復(fù)制到d中n if(ci

38、m&jright&i1, c是常數(shù)化簡(jiǎn): 若n=2k,則有, T(n) =2(2T(n/22)+cn/2)+cn = 22T(n/22) + 2cn =22(2T(n/23) +cn/22) + 2cn = 23T(n/23)+3cn = =2kT(1)+kcn =an+cnlogn /k=logn/ 若2kn2k+1,則有T(n)T(2k+1)。所以得：T(n) = (nlogn) &最壞時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：O(nlogn)&平均時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)n 快速排序采用一種特殊的分劃操作對(duì)排序問(wèn)

39、快速排序采用一種特殊的分劃操作對(duì)排序問(wèn)題進(jìn)行分解，其分解方法是：在待排序的序列題進(jìn)行分解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中選擇一個(gè)元素作為分中選擇一個(gè)元素作為分劃元素劃元素，也，也稱為稱為主元主元（pivot）。不妨假定選擇）。不妨假定選擇K 為主元。經(jīng)為主元。經(jīng)過(guò)一趟特殊的分劃處理將原序列中的元素過(guò)一趟特殊的分劃處理將原序列中的元素重新排重新排列列，使得以主元為軸心，將序列分成左右兩個(gè)子，使得以主元為軸心，將序列分成左右兩個(gè)子序列。序列。主元左側(cè)子序列中所有元素都不大于主元，主元左側(cè)子序列中所有元素都不大于主元，主元右側(cè)子序列中所有元素都不小于主元。主元右側(cè)子序列中所有

40、元素都不小于主元。在快速排序中，記錄的比較和交換是從兩端向中間在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。數(shù)較少。templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r);/分劃操作分劃操作 QuickSort (a,p,q-1);

41、 /對(duì)左半段排序?qū)ψ蟀攵闻判?QuickSort (a,q+1,r); /對(duì)右半段排序?qū)τ野攵闻判?n分劃操作(以最左邊的元素72為主元)templateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; / 將將 x的元素交換到右邊區(qū)域的元素交換到右邊區(qū)域 while (true) while (a+i x&ix); /從右邊開(kāi)始尋找不大于從右邊開(kāi)始尋找不大于x的數(shù)的數(shù)aj if (i = j) break; Swap(ai, aj); ap = aj; /移動(dòng)主元的位置移動(dòng)主元的位置 aj =

42、x; return j;n快速排序示例templateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r);/產(chǎn)生產(chǎn)生p和和r之間的一個(gè)隨機(jī)整數(shù)之間的一個(gè)隨機(jī)整數(shù)i Swap(ai, ap); return Partition (a, p, r); 快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改算法算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。望劃分是較對(duì)稱的。&最壞時(shí)間復(fù)雜度：最壞時(shí)間復(fù)雜度：O(n2)&平均時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：O(nlogn)&輔助空間：輔助空間