《算法設(shè)計(jì)與》-第2章遞歸與分治策略

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析授課教師：劉偉授課教師：劉偉電電 話：話郵 件：件：bme_ QQ：1071271580辦辦 公公 室：長(zhǎng)安校區(qū)東區(qū)室：長(zhǎng)安校區(qū)東區(qū) FZ145 室室第第 2 章章 遞歸與分治策略遞歸與分治策略分治法是經(jīng)典的計(jì)算機(jī)算法，是一種求解大問題的有效策略。什么樣的問題適于采用分治法解決？什么樣的問題適于采用分治法解決？如何用分治法解決問題？如何用分治法解決問題？第第 2 章章 遞歸與分治策略遞歸與分治策略凡治眾如治寡，分?jǐn)?shù)是也斗眾如斗寡，形名是也孫子兵法勢(shì)篇管理大部隊(duì)與管理小部隊(duì)原理是一樣的管理大部隊(duì)與管理小部隊(duì)原理是一樣的，抓住編制員額有異，抓住

2、編制員額有異這個(gè)特點(diǎn)就行了這個(gè)特點(diǎn)就行了指揮大部隊(duì)?wèi)?zhàn)斗與指揮小部隊(duì)?wèi)?zhàn)斗基本原理是一樣的指揮大部隊(duì)?wèi)?zhàn)斗與指揮小部隊(duì)?wèi)?zhàn)斗基本原理是一樣的，掌握，掌握部隊(duì)建制規(guī)模及其相應(yīng)的名稱不同這個(gè)特點(diǎn)就行了部隊(duì)建制規(guī)模及其相應(yīng)的名稱不同這個(gè)特點(diǎn)就行了第第 2 章章 遞歸與分治策略遞歸與分治策略分治法（分治法（Divide and Conquer）將一個(gè)難以直接解決的大問題，合理分割成一些規(guī)模較小的相同問題，以便各個(gè)解決，這個(gè)策略就叫分治法（分而治之分而治之）。第第 2 章章 遞歸與分治策略遞歸與分治策略分治法把一個(gè)規(guī)模大的問題劃分為若干個(gè)規(guī)模小的問題，劃分后的小問題和原始的大問題是同樣的問題，而且互相獨(dú)立，沒有

3、關(guān)聯(lián)。這種劃分可以一直做下去，直至所有的小問題可以直接求解為止。然后把所有小問題的解進(jìn)行合并，最終可以得到原始大問題的解。由此可見，分治法的思想是降低問題分治法的思想是降低問題的規(guī)模，其目的是使問題易于求解的規(guī)模，其目的是使問題易于求解。第第 2 章章 遞歸與分治策略遞歸與分治策略分治法求解問題時(shí)包含兩個(gè)過程：一是反復(fù)把大問題自頂向自頂向下下劃分為一系列相同且獨(dú)立的小問題，直至這些小問題可以直接求解為止。這是這是“分分”的過程的過程。第第 2 章章 遞歸與分治策略遞歸與分治策略二是求解這些小問題并將所有小問題的解自底向上自底向上合并得到大問題的解。這是這是“治治”的過程的過程。第第 2 章章

4、遞歸與分治策略遞歸與分治策略在分治法“分”的過程中，由于大問題被劃分為一系列相同的小問題，這就為使用遞歸技術(shù)遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模不斷縮小，最終使子問題縮小到很容易求出其解，由此自然引出遞歸算法。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法（但這在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法（但這并非意味著分治法一定要使用遞歸）并非意味著分治法一定要使用遞歸）。第第 2 章章 遞歸與分治策略遞歸與分治策略分治法：從求數(shù)組最值談起分治法：從求數(shù)組最值談起【例】數(shù)組 M

5、中包含 N 個(gè)互不相同的隨機(jī)非零整數(shù)，求 M 中的最大值和最小值?！痉治龇治觥坎捎帽闅v法比較數(shù)組元素求最值來解決。根據(jù)題意要設(shè)計(jì)如下 2 個(gè)函數(shù)：生成互不相同隨機(jī)生成互不相同隨機(jī)整數(shù)數(shù)組及查找數(shù)組中最值的函數(shù)整數(shù)數(shù)組及查找數(shù)組中最值的函數(shù)。第第 2 章章 遞歸與分治策略遞歸與分治策略【注】本課件中所有代碼如無特別說明，均采用標(biāo)準(zhǔn) C 語言撰寫，在 Visual Studio 2010 旗艦版環(huán)境下調(diào)試通過。實(shí)驗(yàn)環(huán)境：CPU 為 Intel Core i3 雙核（64 位處理器），3.4 GHz，內(nèi)存 8 G。操作系統(tǒng)為 Windows 8.1中文版（64 位系統(tǒng)）。第第 2 章章 遞歸與分治策

6、略遞歸與分治策略#include #include #include #define ARRAY_SIZE 10#define TRUE 1#define FALSE 0/ 生成包含生成包含 N 個(gè)互不相同隨機(jī)整數(shù)的數(shù)組個(gè)互不相同隨機(jī)整數(shù)的數(shù)組.void CreateRandomIntArray( int *p, int N ) int i, j, kt, IsStop, *pt; / 生成隨機(jī)數(shù)種子生成隨機(jī)數(shù)種子. srand( ( unsigned )time( NULL ) ); 第第 2 章章 遞歸與分治策略遞歸與分治策略 / 生成包含生成包含 N 個(gè)互不相同隨機(jī)整數(shù)的數(shù)組個(gè)互不相同隨

7、機(jī)整數(shù)的數(shù)組. pt = p; for( i = 0; i N; i+ ) IsStop = FALSE; while( !IsStop ) kt = rand( ) + 1; / 返回一個(gè)非返回一個(gè)非 0 的隨機(jī)數(shù)的隨機(jī)數(shù). / kt 是否已經(jīng)存在是否已經(jīng)存在. for( j = 0; j i; j+ ) if ( *( pt + j ) = kt ) / 發(fā)現(xiàn)重復(fù)數(shù)發(fā)現(xiàn)重復(fù)數(shù). break;第第 2 章章 遞歸與分治策略遞歸與分治策略 if ( i = 0 ) / 第第 1 個(gè)數(shù)單獨(dú)處理個(gè)數(shù)單獨(dú)處理. IsStop = ( *pt != kt ); else IsStop = ( j =

8、i );*p+ = kt; 第第 2 章章 遞歸與分治策略遞歸與分治策略/ 采用遍歷法查找數(shù)組中的最值采用遍歷法查找數(shù)組中的最值.void FindArrayMaxAndMin( int *p, int N, int *MaxNum, int *MinNum ) int i; *MaxNum = *p+; *MinNum = *MaxNum; for( i = 1; i *MaxNum ) *MaxNum = *p; if ( *p *MinNum ) *MinNum = *p; p+; 第第 2 章章 遞歸與分治策略遞歸與分治策略void main( void ) int ArrayData

9、 ARRAY_SIZE ; int i, MaxNum, MinNum; / 生成包含生成包含 N 個(gè)互不相同隨機(jī)整數(shù)的數(shù)組個(gè)互不相同隨機(jī)整數(shù)的數(shù)組. CreateRandomIntArray( ArrayData, ARRAY_SIZE ); / 輸出隨機(jī)數(shù)組內(nèi)容輸出隨機(jī)數(shù)組內(nèi)容. for( i = 0; i ARRAY_SIZE; i+ ) printf( %dn, ArrayData i ); printf( n ); / 遍歷方式查找數(shù)組最值遍歷方式查找數(shù)組最值. FindArrayMaxAndMin( ArrayData, ARRAY_SIZE, &MaxNum, &

10、MinNum ); printf( : %dn, MaxNum ); printf( : %dn, MinNum ); printf( n );第第 2 章章 遞歸與分治策略遞歸與分治策略/ 等待用戶輸入任意一鍵返回等待用戶輸入任意一鍵返回. system( PAUSE );遍歷法求數(shù)組最值運(yùn)行結(jié)果示例遍歷法求數(shù)組最值運(yùn)行結(jié)果示例第第 2 章章 遞歸與分治策略遞歸與分治策略另外的角度：用分治法的思想來求解數(shù)組最值問題用分治法的思想來求解數(shù)組最值問題。分治法求數(shù)組最值：分治法求數(shù)組最值：“分分”的過程的過程第第 2 章章 遞歸與分治策略遞歸與分治策略分治法求數(shù)組最值：分治法求數(shù)組最值：“治治”的

11、過程的過程第第 2 章章 遞歸與分治策略遞歸與分治策略分治方法求數(shù)組最值的算法框架分治方法求數(shù)組最值的算法框架（1）將數(shù)據(jù)集 S 均分為 S1 和 S2；（2）求解 S1 和 S2 中的最大和最小值；（3）最終的最大和最小值可以計(jì)算得到：min( S1, S2 ), max( S1, S2 )；（4）采用同樣的處理方法遞歸處理 S1 和 S2。第第 2 章章 遞歸與分治策略遞歸與分治策略/ 采用分治法查找數(shù)組中的最值采用分治法查找數(shù)組中的最值./ kb - (子子)數(shù)組左邊界數(shù)組左邊界( begin )/ ke - (子子)數(shù)組右邊界數(shù)組右邊界( end )void FindArrayMaxA

12、ndMin( int ArrayData, int kb, int ke, int *MaxNum, int *MinNum ) int LMaxNum, LMinNum; int RMaxNum, RMinNum; if( ke - kb ArrayData ke ) *MaxNum = ArrayData kb ; *MinNum = ArrayData ke ;第第 2 章章 遞歸與分治策略遞歸與分治策略else *MaxNum = ArrayData ke ; *MinNum = ArrayData kb ; else / (子子)數(shù)組中含有多個(gè)元素?cái)?shù)組中含有多個(gè)元素. / 數(shù)組左半部

13、分?jǐn)?shù)組左半部分 分治分治. FindArrayMaxAndMin( ArrayData, kb, kb + ( ke - kb ) / 2, &LMaxNum, &LMinNum ); / 數(shù)組右半部分?jǐn)?shù)組右半部分 分治分治. FindArrayMaxAndMin( ArrayData, kb + ( ke - kb ) / 2 + 1, ke, &RMaxNum, &RMinNum ); 第第 2 章章 遞歸與分治策略遞歸與分治策略/ 下面是合并過程下面是合并過程. if( LMaxNum RMaxNum ) *MaxNum = LMaxNum;else *M

14、axNum = RMaxNum; if( LMinNum = 6000 ) & ( ArrayData kb = 10000 ) );else / (子子)數(shù)組中含有多個(gè)元素?cái)?shù)組中含有多個(gè)元素 . LNum = CountEmployeeNum( ArrayData, kb, kb + ( ke - kb ) / 2 ); RNum = CountEmployeeNum( ArrayData, kb + ( ke - kb ) / 2 + 1, ke ); return ( LNum + RNum ); 第第 2 章章 遞歸與分治策略遞歸與分治策略【例】一個(gè)裝有 16 枚硬幣的袋子，1

15、6 枚硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕?，F(xiàn)有一臺(tái)可用來比較兩組硬幣重量的儀器，請(qǐng)使用分治法設(shè)計(jì)一個(gè)算法，可以找出那枚偽造的硬幣。第第 2 章章 遞歸與分治策略遞歸與分治策略【分析分析】根據(jù)已知可以有如下求解方案：方案一方案一：任意取 1 枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，則為偽幣。最多可能有最多可能有 15 次比較次比較。第第 2 章章 遞歸與分治策略遞歸與分治策略【分析分析】根據(jù)已知可以有如下求解方案：方案二方案二：將硬幣分為 8 組，每組 2 個(gè)，每組比較一次。若發(fā)現(xiàn)輕者，則為偽幣。最多可能有最多可能有 8 次比較次比較。第第 2 章章 遞歸與分治策略遞歸與分治

16、策略【分析分析】根據(jù)已知可以有如下求解方案：方案三（分治策略）方案三（分治策略）：按下圖處理，有有 4 次比較次比較。第第 2 章章 遞歸與分治策略遞歸與分治策略【分析分析】上述三種方案，分別需要比較 15 次、8 次、4 次。原因在于：方案一方案一：每枚硬幣都至少進(jìn)行了一次比較，而有一枚硬幣進(jìn)行了 15 次比較。方案二方案二：每枚硬幣只進(jìn)行了 1 次比較。方案三方案三：分治策略分治策略。將硬幣分為兩組后，1 次比較可以將硬幣的范圍縮小到原來的一半。這樣充分利用了只有一枚偽幣的基本性質(zhì)。第第 2 章章 遞歸與分治策略遞歸與分治策略根據(jù)上述算法，請(qǐng)各位同學(xué)編寫用分治策略求解找根據(jù)上述算法，請(qǐng)各位

17、同學(xué)編寫用分治策略求解找偽幣問題的程序代碼偽幣問題的程序代碼。第第 2 章章 遞歸與分治策略遞歸與分治策略教學(xué)內(nèi)容教學(xué)內(nèi)容（1）遞歸算法（2）分治法算法框架（3）二分搜索技術(shù)（4）棋盤覆蓋問題（5）合并排序與快速排序（6）平面最接近點(diǎn)對(duì)問題（選講選講）第第 2 章章 遞歸與分治策略遞歸與分治策略2.1 遞歸算法遞歸算法（1）直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。（2）由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致反復(fù)應(yīng)用分治手段，可以使子問題與原問題類

18、型一致而其規(guī)模卻不斷縮小而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生這自然導(dǎo)致遞歸過程的產(chǎn)生。第第 2 章章 遞歸與分治策略遞歸與分治策略（3）分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法（但這并非算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法（但這并非意味著分治法一定要使用遞歸）意味著分治法一定要使用遞歸）。第第 2 章章 遞歸與分治策略遞歸與分治策略在什么情況下可以使用遞歸程序設(shè)計(jì)？在什么情況下可以使用遞歸程序設(shè)計(jì)？ 程序要處理的數(shù)據(jù)結(jié)構(gòu)具有遞歸特性，適于用遞歸描述。程序要處理的數(shù)據(jù)結(jié)構(gòu)具有

19、遞歸特性，適于用遞歸描述。如二叉樹結(jié)構(gòu)具有遞歸特性，其遍歷算法為遞歸算法。第第 2 章章 遞歸與分治策略遞歸與分治策略 程序要處理的問題具有遞歸特性，則適于用遞歸描述。程序要處理的問題具有遞歸特性，則適于用遞歸描述。這類問題一般具有非常明顯的遞歸關(guān)系式，比較容易設(shè)計(jì)相應(yīng)的代碼。【例例】階乘函數(shù)可遞歸地定義如下，設(shè)計(jì)計(jì)算階乘的程序。階乘函數(shù)可遞歸地定義如下，設(shè)計(jì)計(jì)算階乘的程序。第第 2 章章 遞歸與分治策略遞歸與分治策略【分析】邊界條件邊界條件（一般是非遞歸定義的初始值）與遞歸方程遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。int CalcFactor

20、ial( int n ) if ( n = 0 ) return 1; return n * CalcFactorial( n 1 );第第 2 章章 遞歸與分治策略遞歸與分治策略【例例】無窮數(shù)列無窮數(shù)列 1、1、2、3、5、8、13、21、，稱為，稱為Fibonacci 數(shù)列，它的定義如下。編寫程序計(jì)算數(shù)列，它的定義如下。編寫程序計(jì)算 Fibonacci 數(shù)列。數(shù)列。1 0( )1 1(1)(2) 1nF nnF nF nn【分析】上述 Fibonacci 數(shù)列的計(jì)算公式是一個(gè)典型的遞歸關(guān)系式。公式前兩行是邊界條件，第三行是遞歸方程。根據(jù)公式可以很容易寫出代碼。第第 2 章章 遞歸與分治策略

21、遞歸與分治策略/ 遞歸方式計(jì)算遞歸方式計(jì)算 Fibonacci 數(shù)列數(shù)列.int CalcFibonacciSequence( int n ) if ( n = 0 和和 n = 0，定義如下：，定義如下：第第 2 章章 遞歸與分治策略遞歸與分治策略【分析】“階乘函數(shù)”和“Fibonacci 數(shù)列”都可以找到相應(yīng)的非遞歸方式定義，如下所示。Ackerman 函數(shù)卻無法找到非遞歸的定義。Ackerman 函數(shù) A ( n，m ) 的自變量 m 的每一個(gè)值都定義了一個(gè)單變量函數(shù)：第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞

22、歸與分治策略Ackerman 函數(shù)總結(jié)如下：第第 2 章章 遞歸與分治策略遞歸與分治策略int CalcAckerman( int n, int m ) if ( m = 0 ) if ( n = 1 ) return 1; else return ( n + 2 ); else if( n = 0 ) return 1; else return CalcAckerman( CalcAckerman( n - 1, m ), m - 1 );第第 2 章章 遞歸與分治策略遞歸與分治策略 程序要處理的問題本身沒有明顯的遞歸特性，經(jīng)過分析后程序要處理的問題本身沒有明顯的遞歸特性，經(jīng)過分析后發(fā)現(xiàn)其蘊(yùn)

23、含著遞歸結(jié)構(gòu)，可以采用遞歸設(shè)計(jì)。發(fā)現(xiàn)其蘊(yùn)含著遞歸結(jié)構(gòu)，可以采用遞歸設(shè)計(jì)。這類問題表面上看起來沒有明顯的遞歸結(jié)構(gòu)，但仔細(xì)分析可以發(fā)現(xiàn)蘊(yùn)含著遞歸結(jié)構(gòu)。解決的思路是先通過幾個(gè)簡(jiǎn)單的例子觀察問題是否具有遞歸特性，即大問題是否可以劃分為類似的若干個(gè)小問題？如果可以，則該問題能采用遞歸設(shè)計(jì)求解。然后根據(jù)將大問題劃分為類似的若干個(gè)小問題的方法進(jìn)行遞歸程序設(shè)計(jì)。第第 2 章章 遞歸與分治策略遞歸與分治策略【例例】設(shè)計(jì)一個(gè)遞歸算法生成設(shè)計(jì)一個(gè)遞歸算法生成 n 個(gè)無重復(fù)元素個(gè)無重復(fù)元素 r1, r2, , rn 的全排列。的全排列。【分析】從 n 個(gè)互不相同的元素中任取 m 個(gè)元素( m = n )，按照一定的順

24、序排列起來，叫做從 n 個(gè)不同元素中取出 m 個(gè)元素的一個(gè)排列。當(dāng) m = n 時(shí)所有的排列情況叫無重復(fù)元素的全排列。如 1、2、3 三個(gè)元素的全排列為：1、2、3，1、3、2，2、1、3，2、3、1，3、1、2，3、2、1，共3！= 6種排列方式。如果有 n 個(gè)元素，則有 n! 種排列方式。第第 2 章章 遞歸與分治策略遞歸與分治策略全排列問題表面上看是不能采用遞歸設(shè)計(jì)的，因?yàn)樗幌?Fibonacci數(shù)列那樣有明顯的遞歸結(jié)構(gòu)。經(jīng)過仔細(xì)分析可以發(fā)現(xiàn)，全排列問題也蘊(yùn)含著遞歸結(jié)構(gòu)。以 1、2、3 三個(gè)元素的全排列為例分析如下：第第 2 章章 遞歸與分治策略遞歸與分治策略由此可以得到一個(gè)結(jié)論：3

25、個(gè)元素的全排列問題可轉(zhuǎn)化為求 2個(gè)元素的全排列問題。按照這種方式繼續(xù)推廣分析，可以得到結(jié)論：n 個(gè)元素的全排列問題可轉(zhuǎn)化為求個(gè)元素的全排列問題可轉(zhuǎn)化為求 n-1 個(gè)元素的全排列個(gè)元素的全排列問題。顯然全排列問題具有遞歸結(jié)構(gòu)，可以采用遞歸程序設(shè)計(jì)問題。顯然全排列問題具有遞歸結(jié)構(gòu)，可以采用遞歸程序設(shè)計(jì)。第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略全排列的遞歸算法說明示例全排列的遞歸算法說明示例設(shè) R = 1, 2, 3 ，則 n = 3，根據(jù)上述算法，產(chǎn)生的全排列為：1 2, 3 2 3 3 2 （即對(duì)集合即對(duì)集合 2, 3 繼續(xù)執(zhí)行遞歸算法，繼續(xù)執(zhí)行遞

26、歸算法，下同下同）2 1, 3 1 3 3 1 3 1, 2 1 2 2 1 即 R = 1, 2, 3 產(chǎn)生的全排列為：1, 2, 3 1, 3, 22, 1, 3 2, 3, 13, 1, 2 3, 2, 1第第 2 章章 遞歸與分治策略遞歸與分治策略#include #include #include / 交換交換 2 個(gè)字符個(gè)字符.void SwapChar( char *a, char *b ) char t = *a; *a = *b; *b = t;第第 2 章章 遞歸與分治策略遞歸與分治策略/ 全排列實(shí)現(xiàn)全排列實(shí)現(xiàn), k 表示當(dāng)前選取到第幾個(gè)元素表示當(dāng)前選取到第幾個(gè)元素, m

27、表示共有多少元素表示共有多少元素.void FullPermutation( char *pe, int k, int m ) if ( k = m ) static int it = 1; printf( : %sn, it+, pe ); else / 第第 i 個(gè)元素分別與它后面的元素交換就能得到新的排列個(gè)元素分別與它后面的元素交換就能得到新的排列. for ( int i = k; i = m; i+ ) SwapChar( pe + k, pe + i );第第 2 章章 遞歸與分治策略遞歸與分治策略 FullPermutation( pe, k + 1, m ); SwapChar

28、( pe + k, pe + i ); void main( void ) char szTextStr = 123; printf( %s的全排列如下的全排列如下:nn, szTextStr ); FullPermutation( szTextStr, 0, strlen( szTextStr ) - 1 ); printf( nn ); / 等待用戶輸入任意一鍵返回等待用戶輸入任意一鍵返回. system( PAUSE );第第 2 章章 遞歸與分治策略遞歸與分治策略無重復(fù)元素全排列運(yùn)行結(jié)果示例無重復(fù)元素全排列運(yùn)行結(jié)果示例第第 2 章章 遞歸與分治策略遞歸與分治策略【例例】整數(shù)劃分問題。將

29、正整數(shù)整數(shù)劃分問題。將正整數(shù) n 表示成一系列正整數(shù)之和：表示成一系列正整數(shù)之和：n = n1 + n2 + + nk，其中，其中 n1 n2 nk 1，k 1。正整數(shù)正整數(shù) n 的這種表示稱為正整數(shù)的這種表示稱為正整數(shù) n 的劃分。求正整數(shù)的劃分。求正整數(shù) n 的不同的不同劃分個(gè)數(shù)。劃分個(gè)數(shù)。 【分析】先通過一個(gè)例子來看整數(shù)劃分問題。例如正整數(shù) 6 有如下 11 種不同的劃分：6、5 + 1、4 + 2、4 + 1 + 1、3 + 3、3 + 2 + 1、3 + 1 + 1 + 1、2 + 2 + 2、2 + 2 + 1 + 1、2 + 1 + 1 + 1 + 1、1 + 1 + 1 + 1

30、 + 1 + 1。也可以采用如下方式表示 6 的 11 個(gè)劃分： 6 ， 5、1 ， 1、1、1、1、1、1 。第第 2 章章 遞歸與分治策略遞歸與分治策略由于要求 n1 n2 nk 1，k 1 ，所以像 1 + 5、2 + 4 這類劃分不會(huì)出現(xiàn)。將正整數(shù) n 的不同劃分個(gè)數(shù)稱為正整數(shù) n 的劃分?jǐn)?shù)，記作 p( n )，如上述 p( 6 ) = 11。整數(shù)劃分問題表面無明顯的遞歸結(jié)構(gòu)，但仔細(xì)觀察上述但仔細(xì)觀察上述 6 的劃分例子，的劃分例子，6 = 3 + 3 又包含了整數(shù)又包含了整數(shù) 3 的劃分問題，也即大問題中包含了類似的小的劃分問題，也即大問題中包含了類似的小問題的求解，所以該問題具有遞

31、歸結(jié)構(gòu)問題的求解，所以該問題具有遞歸結(jié)構(gòu)?？梢圆捎萌缦路椒ㄔO(shè)計(jì)整數(shù)劃分問題的遞歸算法：第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略綜上可得遞歸表達(dá)式如下所示：1 11 1( ,)( , ) 1( ,1) (,)( ,1) nmq n mq n nnmq n nnmq nm mq n mnm第第 2 章章 遞歸與分治策略遞歸與分治策略/ 遞歸方式計(jì)算整數(shù)劃分問題遞歸方式計(jì)算整數(shù)劃分問題.unsigned long CalcIntPartitionNum( int n

32、, int m ) if ( ( n 1 ) | ( m 1 ) ) return 0; if ( ( n = 1 ) | ( m = 1 ) ) return 1; if ( n m ) return CalcIntPartitionNum( n, n ); if ( n = m ) return ( 1 + CalcIntPartitionNum( n, m - 1 ) ); return ( CalcIntPartitionNum( n, m - 1 ) + CalcIntPartitionNum( n - m, m ) );第第 2 章章 遞歸與分治策略遞歸與分治策略遞歸程序設(shè)計(jì)具有結(jié)

33、構(gòu)清晰，可讀性強(qiáng)，容易用數(shù)學(xué)歸納法來證明算法正確性等優(yōu)點(diǎn)，為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。但遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占但遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多用的存儲(chǔ)空間都比非遞歸算法要多。因此有時(shí)需要在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。一種常用的做法是用遞推來實(shí)現(xiàn)遞歸函數(shù)用遞推來實(shí)現(xiàn)遞歸函數(shù)，這種方法在時(shí)空復(fù)雜度上均有較大改善。第第 2 章章 遞歸與分治策略遞歸與分治策略【例例】采用遞推算法求解采用遞推算法求解 Fibonacci 數(shù)列問題。數(shù)列問題。 【分析】根據(jù) Fibonacci 數(shù)列的計(jì)算公式可以寫出遞推

34、算法：/ 遞推法計(jì)算遞推法計(jì)算 Fibonacci 數(shù)列第數(shù)列第 n 項(xiàng)的值項(xiàng)的值.int CalcFibonacciSequence( int n ) int F0 = 1, F1 = 1, Fn = 1; if ( n 3 ) return 1; else for ( int i = 1; i = ( n - 2 ); i+ ) F0 = F1; F1 = Fn; Fn = F0 + F1; return Fn; 第第 2 章章 遞歸與分治策略遞歸與分治策略2.2 分治法算法框架分治法算法框架分治法的基本思想分治法的基本思想是將一個(gè)規(guī)模為 n 的問題分解為 k 個(gè)規(guī)模較小的子問題，這些子問

35、題互相獨(dú)立且與原問題相同。遞歸地解這些子問題遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問題的解。什么樣的問題適于采用分治法解決？什么樣的問題適于采用分治法解決？第第 2 章章 遞歸與分治策略遞歸與分治策略分治法所能解決的問題一般具有如下幾個(gè)特性（適用分治法所能解決的問題一般具有如下幾個(gè)特性（適用條件）條件）：（1）該問題規(guī)?？s小到一定的程度就可以容易地解該問題規(guī)?？s小到一定的程度就可以容易地解決決。因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特性。（2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題該問題可以分解為若干個(gè)規(guī)模較小的相同問題。這條特性是應(yīng)用分治法的

36、前提，它也是大多數(shù)問題可以滿足的，此特性反映了遞歸思想的應(yīng)用。第第 2 章章 遞歸與分治策略遞歸與分治策略（3）利用該問題分解出的子問題的解可以合并為該利用該問題分解出的子問題的解可以合并為該問題的解。問題的解。能否利用分治法完全取決于問題是否具有這條特性，如果具備了前兩條特性，而不具備第三條特性，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。第第 2 章章 遞歸與分治策略遞歸與分治策略（4）該問題所分解出的各個(gè)子問題是相互獨(dú)立的，該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題即子問題之間不包含公共的子問題。這條特性涉及到分治法的效率。如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工

37、作，重復(fù)地解公共子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好（在在“動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法”一章中還要提及此問題一章中還要提及此問題）。第第 2 章章 遞歸與分治策略遞歸與分治策略/ 分治法的算法框架分治法的算法框架.divide-and-conquer( P ) if ( | P | = n0 ) adhoc( P ); divide P into smaller subinstances P1,P2,.,Pk； for ( i = 1,i = k,i+ ) yi = divide-and-conquer( Pi ); return merge( y1, y2, ., yk );第第

38、2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略分治法是將一個(gè)規(guī)模為分治法是將一個(gè)規(guī)模為 n 的問題分解為的問題分解為 k 個(gè)規(guī)模較個(gè)規(guī)模較小的子問題，那么小的子問題，那么 k 值取多少合適呢？也就是說應(yīng)值取多少合適呢？也就是說應(yīng)該把原問題劃分為多少個(gè)子問題合適？每個(gè)子問題該把原問題劃分為多少個(gè)子問題合適？每個(gè)子問題的規(guī)模應(yīng)當(dāng)多大？的規(guī)模應(yīng)當(dāng)多大？第第 2 章章 遞歸與分治策略遞歸與分治策略由于實(shí)際情況千變?nèi)f化，這些問題很難從理論上分析回答。大量實(shí)踐表明在用分治法設(shè)計(jì)算法時(shí)，最好使大量實(shí)踐表明在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同，即將一個(gè)問題劃分成

39、大小相子問題的規(guī)模大致相同，即將一個(gè)問題劃分成大小相等的等的 k 個(gè)子問題的處理方法行之有效。許多問題可以個(gè)子問題的處理方法行之有效。許多問題可以取取 k = 2（如前面講解的例子）。這種使子問題規(guī)模大致相等的做法是出自一種“平衡子問題平衡子問題”的思想，它幾乎總是比子問題規(guī)模不等的做法要好。第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略(1) 1( )( /)( ) 1OnT nkT n mf nn采用和前面數(shù)組最值問題類似的推導(dǎo)方法可得：2221100232110033221100( )( /)( /)( ) ( /)( /)( /) ( /)(

40、/)( /)( /) ( /)( /)( /)( /) . ( /)ppT nk kT n mf n mf nk T n mk f n mk f n mkkT n mf n mk f n mk f n mk T n mk T n mk f n mk f n mk T n m10( /)pjjjk f n m第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略通過若干實(shí)例分析：通過若干實(shí)例分析：如何用分治法解決問題？如何用分治法解決問題？ 二分搜索技術(shù) 棋盤覆蓋問題 合并排序與快速排序 平面最接近點(diǎn)對(duì)問題（選講選講）

41、第第 2 章章 遞歸與分治策略遞歸與分治策略2.3 二分搜索技術(shù)二分搜索技術(shù)給定已排好序（如升序）的 n 個(gè)元素 a 0 : n 1 ，現(xiàn)要在這 n 個(gè)元素中找出一特定元素 x。針對(duì)上述有序數(shù)組查找問題，可使用不同的策略求解。第第 2 章章 遞歸與分治策略遞歸與分治策略順序搜索方法（順序搜索方法（非分治策略非分治策略）逐個(gè)比較 a 0 : n 1 中的元素，直至找出元素 x 或者搜索遍整個(gè)數(shù)組后確定 x 不在其中。該方法的缺點(diǎn)該方法的缺點(diǎn)是沒有很好地利用是沒有很好地利用 n 個(gè)元素已排好序這個(gè)條件個(gè)元素已排好序這個(gè)條件，因此在最壞情況下，順序搜索方法需要 O(n) 次比較。第第 2 章章 遞歸

42、與分治策略遞歸與分治策略二分搜索方法（二分搜索方法（分治策略分治策略）的基本思想）的基本思想將 n 個(gè)元素分成個(gè)數(shù)大致相同的兩半，取 a n / 2 與欲查找的 x 作比較，如果 x = a n / 2 則找到 x，算法終止；如果 x a n / 2 ，則只要在數(shù)組 a 的右半部繼續(xù)搜索 x。二分搜索方法充分利用元素間的次序關(guān)系充分利用元素間的次序關(guān)系，采用分治采用分治策略策略，可在最壞情況下用 O( logn ) 時(shí)間完成搜索任務(wù)。第第 2 章章 遞歸與分治策略遞歸與分治策略為何分治策略（二分搜索方法）適于有序數(shù)組查找為何分治策略（二分搜索方法）適于有序數(shù)組查找問題？問題？（1）如果 n =

43、 1 即只有一個(gè)元素，則只要比較這個(gè)元素和 x 就可以確定 x 是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件滿足分治法的第一個(gè)適用條件：該問題的規(guī)?？s小該問題的規(guī)?？s小到一定的程度就可以容易地解決到一定的程度就可以容易地解決。第第 2 章章 遞歸與分治策略遞歸與分治策略（2）比較 x 和 a 的中間元素 a mid ，若 x = a mid ，則 x 在數(shù)據(jù)表 L 中的位置就是mid；如果 x a mid ，同理只要在 a mid 的后面查找 x 即可。無論是在前面還是后面查找 x，其方法都和在 a 中查找 x 一樣，只不過是查找的規(guī)?？s小了。這就說明此問題滿足滿足分治法的第二個(gè)適用條件

44、分治法的第二個(gè)適用條件：該問題可以分解為若干個(gè)規(guī)模該問題可以分解為若干個(gè)規(guī)模較小的相同問題較小的相同問題。第第 2 章章 遞歸與分治策略遞歸與分治策略（3）提出的問題是從數(shù)據(jù)表 L 中找出 x，無論是原始表還是縮小規(guī)模的表，該問題都是一樣的，所以此問題滿足分治法的第三個(gè)適用條件：分解出的子滿足分治法的第三個(gè)適用條件：分解出的子問題的解可以合并為原問題的解問題的解可以合并為原問題的解。（4）很顯然此問題分解出的子問題相互獨(dú)立，即在 a mid 的前面或后面查找 x 是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件滿足分治法的第四個(gè)適用條件：分解出的各個(gè)分解出的各個(gè)子問題是相互獨(dú)立的子問題是相互獨(dú)立

45、的。第第 2 章章 遞歸與分治策略遞歸與分治策略/ 基于分治策略的二分查找算法（遞歸形式）基于分治策略的二分查找算法（遞歸形式）.int BinarySearch( int ArrayData, int left, int right, int *x ) if ( left right ) return -1; int middle = ( left + right ) / 2; if ( *x = ArrayData middle ) return middle; if ( *x ArrayData middle ) return BinarySearch( ArrayData, middl

46、e + 1, right, x ); else return BinarySearch( ArrayData, left, middle - 1, x );第第 2 章章 遞歸與分治策略遞歸與分治策略/ 基于分治策略的二分查找算法（非遞歸形式）基于分治策略的二分查找算法（非遞歸形式）.int BinarySearch( int ArrayData, int x, int n ) int left = 0; int right = n - 1; while ( left ArrayData middle ) left = middle + 1; else right = middle - 1;

47、return -1; / 未找到未找到 x第第 2 章章 遞歸與分治策略遞歸與分治策略算法復(fù)雜性分析（非遞歸形式）算法復(fù)雜性分析（非遞歸形式）每執(zhí)行一次算法的 while 循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，在最壞情況下，while 循環(huán)被執(zhí)行了循環(huán)被執(zhí)行了 O( logn ) 次次。循環(huán)體內(nèi)運(yùn)算需要 O( 1 ) 時(shí)間，因此整整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為 O( logn ) 。第第 2 章章 遞歸與分治策略遞歸與分治策略第第 2 章章 遞歸與分治策略遞歸與分治策略二分搜索法的思想易于理解，應(yīng)用廣泛。但是要寫一個(gè)正確的二分搜索算法也

48、不是一件簡(jiǎn)單的事。第一個(gè)二分搜索算法早在 1946 年就出現(xiàn)了，但是第一個(gè)完全正確的二分搜索算法直到 1962 年才出現(xiàn)。Bentley 在他的著作Writing Correct Programs中寫道，90%的計(jì)算機(jī)專家不能在的計(jì)算機(jī)專家不能在 2 小時(shí)內(nèi)寫出完全正確的二小時(shí)內(nèi)寫出完全正確的二分搜索算法分搜索算法。思考題：思考題：教材 算法分析題算法分析題 2 的 2-2 題（P36）。第第 2 章章 遞歸與分治策略遞歸與分治策略【練習(xí)題練習(xí)題】給定給定 a，用分治法設(shè)計(jì)出求，用分治法設(shè)計(jì)出求 an 的算法。的算法。【分析】第第 2 章章 遞歸與分治策略遞歸與分治策略2.4 棋盤覆蓋問題棋盤

49、覆蓋問題在一個(gè) 2k 2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為一特殊方格特殊方格，且稱該棋盤為一特殊棋盤特殊棋盤。顯然特殊方格在棋盤上出現(xiàn)的位置有 4k 種情形（ 2k 2k = 4k），對(duì) k 0，有 4k 種不同的特殊棋盤。下圖 (a) 中的特殊棋盤是當(dāng) k = 2 時(shí) 16 個(gè)特殊棋盤中的一個(gè)。第第 2 章章 遞歸與分治策略遞歸與分治策略棋盤覆蓋問題中的特殊棋盤與棋盤覆蓋問題中的特殊棋盤與 L 型骨牌型骨牌棋盤覆蓋問題是指用下圖 (b)-(e)中所示的 4 種不同形態(tài)的 L 型骨牌去覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且(b)-(e)中任何 2 個(gè) L

50、型骨牌不得重疊覆蓋。第第 2 章章 遞歸與分治策略遞歸與分治策略棋盤覆蓋問題初看起來很難下手解決，但仔細(xì)思考后可以采用分治策略分治策略設(shè)計(jì)針對(duì)該問題的一個(gè)巧妙解法：如下圖所示，當(dāng) k 0 時(shí)，將 2k 2k 棋盤分割為 4 個(gè) 2k-1 2k-1 子棋盤，如圖 (a) 所示。顯然特殊方格必位于圖 (a) 中 4 個(gè)較小子棋盤之一中，其余 3 個(gè)子棋盤中則無特殊方格。為了將這為了將這 3 個(gè)個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè) L 型骨型骨牌覆蓋這牌覆蓋這 3 個(gè)較小棋盤的會(huì)合處個(gè)較小棋盤的會(huì)合處，如圖 (b) 和 (c) 所示。從而將原問題

51、轉(zhuǎn)化為 4 個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡(jiǎn)化為棋盤 11（易于求解易于求解）。第第 2 章章 遞歸與分治策略遞歸與分治策略分治法求解棋盤覆蓋問題示意圖分治法求解棋盤覆蓋問題示意圖第第 2 章章 遞歸與分治策略遞歸與分治策略棋盤覆蓋問題的數(shù)據(jù)結(jié)構(gòu)棋盤覆蓋問題的數(shù)據(jù)結(jié)構(gòu)（1）棋盤棋盤：可以用一個(gè)二維整型數(shù)組 Board size size 表示一個(gè)棋盤，其中，size = 2k。為了在遞歸處理的過程中使用同一個(gè)棋盤，將數(shù)組 Board 設(shè)為全局變量；（2）子棋盤子棋盤：整個(gè)棋盤用二維數(shù)組 Board size size 表示，其中的子棋盤由棋盤左上角的下標(biāo)（行號(hào)、列號(hào)行號(hào)

52、、列號(hào)） tr、tc 和棋盤大小 s 表示；（3）特殊方格特殊方格：用 Board dr dc 表示特殊方格，dr 和 dc 是該特殊方格在二維數(shù)組 Board 中的下標(biāo)（行號(hào)、列號(hào)行號(hào)、列號(hào)）；（4） L 型骨牌型骨牌：一個(gè) 2k 2k 的棋盤中有一個(gè)特殊方格，用到 L 型骨牌的個(gè)數(shù)為 ( 4k 1 ) / 3，將所有將所有 L 型骨牌從型骨牌從 1 開始連續(xù)編號(hào)（形狀相同的開始連續(xù)編號(hào)（形狀相同的骨牌可能采用不同的編號(hào)），用一個(gè)全局變量骨牌可能采用不同的編號(hào)），用一個(gè)全局變量 t 表示表示。第第 2 章章 遞歸與分治策略遞歸與分治策略棋盤覆蓋問題的分治算法代碼棋盤覆蓋問題的分治算法代碼in

53、t tile = 1; / L 型骨牌的編號(hào)型骨牌的編號(hào)( 遞增遞增 )int Board 100 100 ; / 棋盤棋盤/ 遞歸方式實(shí)現(xiàn)棋盤覆蓋算法遞歸方式實(shí)現(xiàn)棋盤覆蓋算法./ tr - 當(dāng)前棋盤左上角的行號(hào)當(dāng)前棋盤左上角的行號(hào)/ tc - 當(dāng)前棋盤左上角的列號(hào)當(dāng)前棋盤左上角的列號(hào)/ dr - 當(dāng)前特殊方格所在的行號(hào)當(dāng)前特殊方格所在的行號(hào)/ dc - 當(dāng)前特殊方格所在的列號(hào)當(dāng)前特殊方格所在的列號(hào)/ size - 當(dāng)前棋盤的大?。寒?dāng)前棋盤的大?。? kvoid ChessBoard( int tr, int tc, int dr, int dc, int size ) if ( size =

54、 1 ) / 棋盤方格大小為棋盤方格大小為 1, 說明遞歸到最里層說明遞歸到最里層. return;第第 2 章章 遞歸與分治策略遞歸與分治策略 int t = tile+; / 每次遞增每次遞增 1( L 型骨牌編號(hào)型骨牌編號(hào), 注意這里是連續(xù)編號(hào)注意這里是連續(xù)編號(hào) ). int s = size / 2; / 分割棋盤分割棋盤 / 檢查特殊方塊是否在左上角子棋盤中檢查特殊方塊是否在左上角子棋盤中. if ( ( dr tr + s ) & ( dc tc + s ) ) ChessBoard( tr, tc, dr, dc, s ); else / 不在不在, 將該子棋盤右下角的方

55、塊視為特殊方塊將該子棋盤右下角的方塊視為特殊方塊. Board tr + s - 1 tc + s - 1 = t; ChessBoard( tr, tc, tr + s - 1, tc + s - 1, s ); 第第 2 章章 遞歸與分治策略遞歸與分治策略/ 檢查特殊方塊是否在右上角子棋盤中檢查特殊方塊是否在右上角子棋盤中. if ( ( dr = tc + s ) ) ChessBoard( tr, tc + s, dr, dc, s ); else Board tr + s - 1 tc + s = t; ChessBoard( tr, tc + s, tr + s - 1, tc +

56、 s, s ); / 檢查特殊方塊是否在左下角子棋盤中檢查特殊方塊是否在左下角子棋盤中. if ( ( dr = tr + s ) & ( dc = tr + s ) & ( dc = tc + s ) ) ChessBoard( tr + s, tc + s, dr, dc, s ); else Board tr + s tc + s = t; ChessBoard( tr + s, tc + s, tr + s, tc + s, s ); 第第 2 章章 遞歸與分治策略遞歸與分治策略骨牌編號(hào)從 1 開始，特殊方格編號(hào)為 0。如果是一個(gè) 4 4 的棋盤，特殊方格為 ( 2,

57、2 )，則最終生成的棋盤 Board 數(shù)組內(nèi)容為：2 2 3 3 2 1 1 3 4 1 0 5 4 4 5 5第第 2 章章 遞歸與分治策略遞歸與分治策略上述代碼采用了分治思想。首先將棋盤一分為四，則特殊方格必位于 4 個(gè)子棋盤之一。然后用一個(gè) L 型骨牌覆蓋這 3 個(gè)較小棋盤的會(huì)合處，從而將原問題轉(zhuǎn)化為 4 個(gè)較小規(guī)模的棋盤覆蓋問題。之后分別處理左上角、右上角、左下角和右下角 4 個(gè)子棋盤。上述代碼中有如下一個(gè)細(xì)節(jié)需要加以解釋上述代碼中有如下一個(gè)細(xì)節(jié)需要加以解釋：/ 檢查特殊方塊是否在左上角子棋盤中檢查特殊方塊是否在左上角子棋盤中.if ( ( dr tr + s ) & ( dc

58、 tc + s ) ) ChessBoard( tr, tc, dr, dc, s );else / 不在不在, 將該子棋盤右下角的方塊視為特殊方塊將該子棋盤右下角的方塊視為特殊方塊. Board tr + s - 1 tc + s - 1 = t; ChessBoard( tr, tc, tr + s - 1, tc + s - 1, s );第第 2 章章 遞歸與分治策略遞歸與分治策略這段指令首先檢查特殊方塊是否在左上角子棋盤中，如果是說明滿足遞歸條件直接遞歸處理；如果特殊方塊不在左上角子棋如果特殊方塊不在左上角子棋盤中，則將該子棋盤右下角的方塊視為特殊方塊盤中，則將該子棋盤右下角的方塊視

59、為特殊方塊。原因如下：分治法求解棋盤覆蓋問題示意圖分治法求解棋盤覆蓋問題示意圖第第 2 章章 遞歸與分治策略遞歸與分治策略上圖 (a) 表示特殊方塊在左上角子棋盤中，如果特殊方塊不在左上角子棋盤中，那么它必然位于左下角、右上角和右下角之一，如圖(b)-(d)所示。那么必須采用如圖(b)-(d)所示的 L 型骨牌來覆蓋棋盤，不管是這三種覆蓋情況中的哪一種，不管是這三種覆蓋情況中的哪一種，一定會(huì)有一個(gè)方塊覆蓋在左上角子棋盤的右下角，如圖一定會(huì)有一個(gè)方塊覆蓋在左上角子棋盤的右下角，如圖(b)-(d)中的中的“*”符號(hào)所示符號(hào)所示。這就意味著如果特殊方塊不在左上如果特殊方塊不在左上角子棋盤中，就可以將

60、左上角子棋盤右下角的方塊視為特角子棋盤中，就可以將左上角子棋盤右下角的方塊視為特殊方塊殊方塊。如果特殊方塊不在左下角、右上角和右下角子棋盤中，則可以類似處理。第第 2 章章 遞歸與分治策略遞歸與分治策略“棋盤覆蓋棋盤覆蓋”演示程序演示程序第第 2 章章 遞歸與分治策略遞歸與分治策略2.5 合并排序與快速排序合并排序與快速排序排序排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的其目的是使一串是使一串記錄記錄，按照其中的某個(gè)或某些，按照其中的某個(gè)或某些關(guān)鍵字關(guān)鍵字的大小，遞增或遞減排列的大小，遞增或遞減排列。排序是一種基本操作，是應(yīng)用程序的基礎(chǔ)。第第 2 章章 遞歸與分治策略遞歸與分治策略【例例】用百度搜索網(wǎng)頁，搜索結(jié)果就是排序后的結(jié)果（各個(gè)網(wǎng)頁網(wǎng)頁就是記錄記錄，按照某種算法計(jì)算網(wǎng)頁