《算法设计与》-第2章递归与分治策略

1、算法设计与分析算法设计与分析授课教师：刘伟授课教师：刘伟电电 话：话邮 件：件：bme_ QQ：1071271580办办 公公 室：长安校区东区室：长安校区东区 FZ145 室室第第 2 章章 递归与分治策略递归与分治策略分治法是经典的计算机算法，是一种求解大问题的有效策略。什么样的问题适于采用分治法解决？什么样的问题适于采用分治法解决？如何用分治法解决问题？如何用分治法解决问题？第第 2 章章 递归与分治策略递归与分治策略凡治众如治寡，分数是也斗众如斗寡，形名是也孙子兵法势篇管理大部队与管理小部队原理是一样的管理大部队与管理小部队原理是一样的，抓住编制员额有异，抓住

2、编制员额有异这个特点就行了这个特点就行了指挥大部队战斗与指挥小部队战斗基本原理是一样的指挥大部队战斗与指挥小部队战斗基本原理是一样的，掌握，掌握部队建制规模及其相应的名称不同这个特点就行了部队建制规模及其相应的名称不同这个特点就行了第第 2 章章 递归与分治策略递归与分治策略分治法（分治法（Divide and Conquer）将一个难以直接解决的大问题，合理分割成一些规模较小的相同问题，以便各个解决，这个策略就叫分治法（分而治之分而治之）。第第 2 章章 递归与分治策略递归与分治策略分治法把一个规模大的问题划分为若干个规模小的问题，划分后的小问题和原始的大问题是同样的问题，而且互相独立，没有

3、关联。这种划分可以一直做下去，直至所有的小问题可以直接求解为止。然后把所有小问题的解进行合并，最终可以得到原始大问题的解。由此可见，分治法的思想是降低问题分治法的思想是降低问题的规模，其目的是使问题易于求解的规模，其目的是使问题易于求解。第第 2 章章 递归与分治策略递归与分治策略分治法求解问题时包含两个过程：一是反复把大问题自顶向自顶向下下划分为一系列相同且独立的小问题，直至这些小问题可以直接求解为止。这是这是“分分”的过程的过程。第第 2 章章 递归与分治策略递归与分治策略二是求解这些小问题并将所有小问题的解自底向上自底向上合并得到大问题的解。这是这是“治治”的过程的过程。第第 2 章章

4、递归与分治策略递归与分治策略在分治法“分”的过程中，由于大问题被划分为一系列相同的小问题，这就为使用递归技术递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然引出递归算法。分治与递归像一对孪生兄弟，经常同时应用分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法（但这在算法设计之中，并由此产生许多高效算法（但这并非意味着分治法一定要使用递归）并非意味着分治法一定要使用递归）。第第 2 章章 递归与分治策略递归与分治策略分治法：从求数组最值谈起分治法：从求数组最值谈起【例】数组 M

5、中包含 N 个互不相同的随机非零整数，求 M 中的最大值和最小值。【分析分析】采用遍历法比较数组元素求最值来解决。根据题意要设计如下 2 个函数：生成互不相同随机生成互不相同随机整数数组及查找数组中最值的函数整数数组及查找数组中最值的函数。第第 2 章章 递归与分治策略递归与分治策略【注】本课件中所有代码如无特别说明，均采用标准 C 语言撰写，在 Visual Studio 2010 旗舰版环境下调试通过。实验环境：CPU 为 Intel Core i3 双核（64 位处理器），3.4 GHz，内存 8 G。操作系统为 Windows 8.1中文版（64 位系统）。第第 2 章章 递归与分治策

6、略递归与分治策略#include #include #include #define ARRAY_SIZE 10#define TRUE 1#define FALSE 0/ 生成包含生成包含 N 个互不相同随机整数的数组个互不相同随机整数的数组.void CreateRandomIntArray( int *p, int N ) int i, j, kt, IsStop, *pt; / 生成随机数种子生成随机数种子. srand( ( unsigned )time( NULL ) ); 第第 2 章章 递归与分治策略递归与分治策略 / 生成包含生成包含 N 个互不相同随机整数的数组个互不相同随

7、机整数的数组. pt = p; for( i = 0; i N; i+ ) IsStop = FALSE; while( !IsStop ) kt = rand( ) + 1; / 返回一个非返回一个非 0 的随机数的随机数. / kt 是否已经存在是否已经存在. for( j = 0; j i; j+ ) if ( *( pt + j ) = kt ) / 发现重复数发现重复数. break;第第 2 章章 递归与分治策略递归与分治策略 if ( i = 0 ) / 第第 1 个数单独处理个数单独处理. IsStop = ( *pt != kt ); else IsStop = ( j =

8、i );*p+ = kt; 第第 2 章章 递归与分治策略递归与分治策略/ 采用遍历法查找数组中的最值采用遍历法查找数组中的最值.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 个互不相同随机整数的数组个互不相同随机整数的数组. CreateRandomIntArray( ArrayData, ARRAY_SIZE ); / 输出随机数组内容输出随机数组内容. for( i = 0; i ARRAY_SIZE; i+ ) printf( %dn, ArrayData i ); printf( n ); / 遍历方式查找数组最值遍历方式查找数组最值. FindArrayMaxAndMin( ArrayData, ARRAY_SIZE, &MaxNum, &MinNum )

10、; printf( : %dn, MaxNum ); printf( : %dn, MinNum ); printf( n );第第 2 章章 递归与分治策略递归与分治策略/ 等待用户输入任意一键返回等待用户输入任意一键返回. system( PAUSE );遍历法求数组最值运行结果示例遍历法求数组最值运行结果示例第第 2 章章 递归与分治策略递归与分治策略另外的角度：用分治法的思想来求解数组最值问题用分治法的思想来求解数组最值问题。分治法求数组最值：分治法求数组最值：“分分”的过程的过程第第 2 章章 递归与分治策略递归与分治策略分治法求数组最值：分治法求数组最值：“治治”的过程的过程第第

11、2 章章 递归与分治策略递归与分治策略分治方法求数组最值的算法框架分治方法求数组最值的算法框架（1）将数据集 S 均分为 S1 和 S2；（2）求解 S1 和 S2 中的最大和最小值；（3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；（4）采用同样的处理方法递归处理 S1 和 S2。第第 2 章章 递归与分治策略递归与分治策略/ 采用分治法查找数组中的最值采用分治法查找数组中的最值./ kb - (子子)数组左边界数组左边界( begin )/ ke - (子子)数组右边界数组右边界( end )void FindArrayMaxAndMin( i

12、nt 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 / (子子)数组中含有多个元素数组中含有多个元素. / 数组左半部分数组左半部分

13、分治分治. FindArrayMaxAndMin( ArrayData, kb, kb + ( ke - kb ) / 2, &LMaxNum, &LMinNum ); / 数组右半部分数组右半部分 分治分治. FindArrayMaxAndMin( ArrayData, kb + ( ke - kb ) / 2 + 1, ke, &RMaxNum, &RMinNum ); 第第 2 章章 递归与分治策略递归与分治策略/ 下面是合并过程下面是合并过程. if( LMaxNum RMaxNum ) *MaxNum = LMaxNum;else *MaxNum = RMaxNum; if( LMi

14、nNum = 6000 ) & ( ArrayData kb = 10000 ) );else / (子子)数组中含有多个元素数组中含有多个元素 . LNum = CountEmployeeNum( ArrayData, kb, kb + ( ke - kb ) / 2 ); RNum = CountEmployeeNum( ArrayData, kb + ( ke - kb ) / 2 + 1, ke ); return ( LNum + RNum ); 第第 2 章章 递归与分治策略递归与分治策略【例】一个装有 16 枚硬币的袋子，16 枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币

15、要轻。现有一台可用来比较两组硬币重量的仪器，请使用分治法设计一个算法，可以找出那枚伪造的硬币。第第 2 章章 递归与分治策略递归与分治策略【分析分析】根据已知可以有如下求解方案：方案一方案一：任意取 1 枚硬币，与其他硬币进行比较，若发现轻者，则为伪币。最多可能有最多可能有 15 次比较次比较。第第 2 章章 递归与分治策略递归与分治策略【分析分析】根据已知可以有如下求解方案：方案二方案二：将硬币分为 8 组，每组 2 个，每组比较一次。若发现轻者，则为伪币。最多可能有最多可能有 8 次比较次比较。第第 2 章章 递归与分治策略递归与分治策略【分析分析】根据已知可以有如下求解方案：方案三（分治

16、策略）方案三（分治策略）：按下图处理，有有 4 次比较次比较。第第 2 章章 递归与分治策略递归与分治策略【分析分析】上述三种方案，分别需要比较 15 次、8 次、4 次。原因在于：方案一方案一：每枚硬币都至少进行了一次比较，而有一枚硬币进行了 15 次比较。方案二方案二：每枚硬币只进行了 1 次比较。方案三方案三：分治策略分治策略。将硬币分为两组后，1 次比较可以将硬币的范围缩小到原来的一半。这样充分利用了只有一枚伪币的基本性质。第第 2 章章 递归与分治策略递归与分治策略根据上述算法，请各位同学编写用分治策略求解找根据上述算法，请各位同学编写用分治策略求解找伪币问题的程序代码伪币问题的程序

17、代码。第第 2 章章 递归与分治策略递归与分治策略教学内容教学内容（1）递归算法（2）分治法算法框架（3）二分搜索技术（4）棋盘覆盖问题（5）合并排序与快速排序（6）平面最接近点对问题（选讲选讲）第第 2 章章 递归与分治策略递归与分治策略2.1 递归算法递归算法（1）直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。（2）由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小而其规模却不断缩小，最终使子问题

18、缩小到很容易直接求出其解。这自然导致递归过程的产生这自然导致递归过程的产生。第第 2 章章 递归与分治策略递归与分治策略（3）分治与递归像一对孪生兄弟，经常同时应用在分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法（但这并非算法设计之中，并由此产生许多高效算法（但这并非意味着分治法一定要使用递归）意味着分治法一定要使用递归）。第第 2 章章 递归与分治策略递归与分治策略在什么情况下可以使用递归程序设计？在什么情况下可以使用递归程序设计？ 程序要处理的数据结构具有递归特性，适于用递归描述。程序要处理的数据结构具有递归特性，适于用递归描述。如二叉树结构具有递归特性，其遍

19、历算法为递归算法。第第 2 章章 递归与分治策略递归与分治策略 程序要处理的问题具有递归特性，则适于用递归描述。程序要处理的问题具有递归特性，则适于用递归描述。这类问题一般具有非常明显的递归关系式，比较容易设计相应的代码。【例例】阶乘函数可递归地定义如下，设计计算阶乘的程序。阶乘函数可递归地定义如下，设计计算阶乘的程序。第第 2 章章 递归与分治策略递归与分治策略【分析】边界条件边界条件（一般是非递归定义的初始值）与递归方程递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。int CalcFactorial( int n ) if ( n = 0 ) re

20、turn 1; return n * CalcFactorial( n 1 );第第 2 章章 递归与分治策略递归与分治策略【例例】无穷数列无穷数列 1、1、2、3、5、8、13、21、，称为，称为Fibonacci 数列，它的定义如下。编写程序计算数列，它的定义如下。编写程序计算 Fibonacci 数列。数列。1 0( )1 1(1)(2) 1nF nnF nF nn【分析】上述 Fibonacci 数列的计算公式是一个典型的递归关系式。公式前两行是边界条件，第三行是递归方程。根据公式可以很容易写出代码。第第 2 章章 递归与分治策略递归与分治策略/ 递归方式计算递归方式计算 Fibona

21、cci 数列数列.int CalcFibonacciSequence( int n ) if ( n = 0 和和 n = 0，定义如下：，定义如下：第第 2 章章 递归与分治策略递归与分治策略【分析】“阶乘函数”和“Fibonacci 数列”都可以找到相应的非递归方式定义，如下所示。Ackerman 函数却无法找到非递归的定义。Ackerman 函数 A ( n，m ) 的自变量 m 的每一个值都定义了一个单变量函数：第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略Ackerman 函数总结如下：第第 2 章

22、章 递归与分治策略递归与分治策略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 章章 递归与分治策略递归与分治策略 程序要处理的问题本身没有明显的递归特性，经过分析后程序要处理的问题本身没有明显的递归特性，经过分析后发现其蕴含着递归结构，可以采用递归设计。发现其蕴含着递归结构，可

23、以采用递归设计。这类问题表面上看起来没有明显的递归结构，但仔细分析可以发现蕴含着递归结构。解决的思路是先通过几个简单的例子观察问题是否具有递归特性，即大问题是否可以划分为类似的若干个小问题？如果可以，则该问题能采用递归设计求解。然后根据将大问题划分为类似的若干个小问题的方法进行递归程序设计。第第 2 章章 递归与分治策略递归与分治策略【例例】设计一个递归算法生成设计一个递归算法生成 n 个无重复元素个无重复元素 r1, r2, , rn 的全排列。的全排列。【分析】从 n 个互不相同的元素中任取 m 个元素( m = n )，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一

24、个排列。当 m = n 时所有的排列情况叫无重复元素的全排列。如 1、2、3 三个元素的全排列为：1、2、3，1、3、2，2、1、3，2、3、1，3、1、2，3、2、1，共3！= 6种排列方式。如果有 n 个元素，则有 n! 种排列方式。第第 2 章章 递归与分治策略递归与分治策略全排列问题表面上看是不能采用递归设计的，因为它不像 Fibonacci数列那样有明显的递归结构。经过仔细分析可以发现，全排列问题也蕴含着递归结构。以 1、2、3 三个元素的全排列为例分析如下：第第 2 章章 递归与分治策略递归与分治策略由此可以得到一个结论：3 个元素的全排列问题可转化为求 2个元素的全排列问题。按照

25、这种方式继续推广分析，可以得到结论：n 个元素的全排列问题可转化为求个元素的全排列问题可转化为求 n-1 个元素的全排列个元素的全排列问题。显然全排列问题具有递归结构，可以采用递归程序设计问题。显然全排列问题具有递归结构，可以采用递归程序设计。第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略全排列的递归算法说明示例全排列的递归算法说明示例设 R = 1, 2, 3 ，则 n = 3，根据上述算法，产生的全排列为：1 2, 3 2 3 3 2 （即对集合即对集合 2, 3 继续执行递归算法，继续执行递归算法，下同下同）2 1, 3 1 3 3 1 3 1,

26、 2 1 2 2 1 即 R = 1, 2, 3 产生的全排列为：1, 2, 3 1, 3, 22, 1, 3 2, 3, 13, 1, 2 3, 2, 1第第 2 章章 递归与分治策略递归与分治策略#include #include #include / 交换交换 2 个字符个字符.void SwapChar( char *a, char *b ) char t = *a; *a = *b; *b = t;第第 2 章章 递归与分治策略递归与分治策略/ 全排列实现全排列实现, k 表示当前选取到第几个元素表示当前选取到第几个元素, m 表示共有多少元素表示共有多少元素.void FullPe

27、rmutation( char *pe, int k, int m ) if ( k = m ) static int it = 1; printf( : %sn, it+, pe ); else / 第第 i 个元素分别与它后面的元素交换就能得到新的排列个元素分别与它后面的元素交换就能得到新的排列. for ( int i = k; i = m; i+ ) SwapChar( pe + k, pe + i );第第 2 章章 递归与分治策略递归与分治策略 FullPermutation( pe, k + 1, m ); SwapChar( pe + k, pe + i ); void mai

28、n( void ) char szTextStr = 123; printf( %s的全排列如下的全排列如下:nn, szTextStr ); FullPermutation( szTextStr, 0, strlen( szTextStr ) - 1 ); printf( nn ); / 等待用户输入任意一键返回等待用户输入任意一键返回. system( PAUSE );第第 2 章章 递归与分治策略递归与分治策略无重复元素全排列运行结果示例无重复元素全排列运行结果示例第第 2 章章 递归与分治策略递归与分治策略【例例】整数划分问题。将正整数整数划分问题。将正整数 n 表示成一系列正整数之和

29、：表示成一系列正整数之和：n = n1 + n2 + + nk，其中，其中 n1 n2 nk 1，k 1。正整数正整数 n 的这种表示称为正整数的这种表示称为正整数 n 的划分。求正整数的划分。求正整数 n 的不同的不同划分个数。划分个数。 【分析】先通过一个例子来看整数划分问题。例如正整数 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 + 1 + 1。也可以采用如下方式表示 6 的 11

30、个划分： 6 ， 5、1 ， 1、1、1、1、1、1 。第第 2 章章 递归与分治策略递归与分治策略由于要求 n1 n2 nk 1，k 1 ，所以像 1 + 5、2 + 4 这类划分不会出现。将正整数 n 的不同划分个数称为正整数 n 的划分数，记作 p( n )，如上述 p( 6 ) = 11。整数划分问题表面无明显的递归结构，但仔细观察上述但仔细观察上述 6 的划分例子，的划分例子，6 = 3 + 3 又包含了整数又包含了整数 3 的划分问题，也即大问题中包含了类似的小的划分问题，也即大问题中包含了类似的小问题的求解，所以该问题具有递归结构问题的求解，所以该问题具有递归结构。可以采用如下方

31、法设计整数划分问题的递归算法：第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略综上可得递归表达式如下所示：1 11 1( ,)( , ) 1( ,1) (,)( ,1) nmq n mq n nnmq n nnmq nm mq n mnm第第 2 章章 递归与分治策略递归与分治策略/ 递归方式计算整数划分问题递归方式计算整数划分问题.unsigned long CalcIntPartitionNum( int n, int m ) if ( ( n 1 ) | ( m

32、 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 章章 递归与分治策略递归与分治策略递归程序设计具有结构清晰，可读性强，容易用数学归纳法来证明算法正确性等优点

33、，为设计算法、调试程序带来很大方便。但递归算法的运行效率较低，无论是耗费的计算时间还是占但递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多用的存储空间都比非递归算法要多。因此有时需要在递归算法中消除递归调用，使其转化为非递归算法。一种常用的做法是用递推来实现递归函数用递推来实现递归函数，这种方法在时空复杂度上均有较大改善。第第 2 章章 递归与分治策略递归与分治策略【例例】采用递推算法求解采用递推算法求解 Fibonacci 数列问题。数列问题。 【分析】根据 Fibonacci 数列的计算公式可以写出递推算法：/ 递推法计算递推法计算 Fibonacci 数列

34、第数列第 n 项的值项的值.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 分治法算法框架分治法算法框架分治法的基本思想分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题递归地解这些

35、子问题，然后将各个子问题的解合并得到原问题的解。什么样的问题适于采用分治法解决？什么样的问题适于采用分治法解决？第第 2 章章 递归与分治策略递归与分治策略分治法所能解决的问题一般具有如下几个特性（适用分治法所能解决的问题一般具有如下几个特性（适用条件）条件）：（1）该问题规模缩小到一定的程度就可以容易地解该问题规模缩小到一定的程度就可以容易地解决决。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特性。（2）该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题。这条特性是应用分治法的前提，它也是大多数问题可以满足的，此特性反映了递归思想的

36、应用。第第 2 章章 递归与分治策略递归与分治策略（3）利用该问题分解出的子问题的解可以合并为该利用该问题分解出的子问题的解可以合并为该问题的解。问题的解。能否利用分治法完全取决于问题是否具有这条特性，如果具备了前两条特性，而不具备第三条特性，则可以考虑贪心算法或动态规划。第第 2 章章 递归与分治策略递归与分治策略（4）该问题所分解出的各个子问题是相互独立的，该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题即子问题之间不包含公共的子问题。这条特性涉及到分治法的效率。如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共子问题，此时虽然也可用分治法，但一般用动

37、态规划法较好（在在“动态规划法动态规划法”一章中还要提及此问题一章中还要提及此问题）。第第 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 );第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递

38、归与分治策略递归与分治策略分治法是将一个规模为分治法是将一个规模为 n 的问题分解为的问题分解为 k 个规模较个规模较小的子问题，那么小的子问题，那么 k 值取多少合适呢？也就是说应值取多少合适呢？也就是说应该把原问题划分为多少个子问题合适？每个子问题该把原问题划分为多少个子问题合适？每个子问题的规模应当多大？的规模应当多大？第第 2 章章 递归与分治策略递归与分治策略由于实际情况千变万化，这些问题很难从理论上分析回答。大量实践表明在用分治法设计算法时，最好使大量实践表明在用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题划分成大小相子问题的规模大致相同，即将一个问题划分成大小相等的

39、等的 k 个子问题的处理方法行之有效。许多问题可以个子问题的处理方法行之有效。许多问题可以取取 k = 2（如前面讲解的例子）。这种使子问题规模大致相等的做法是出自一种“平衡子问题平衡子问题”的思想，它几乎总是比子问题规模不等的做法要好。第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略(1) 1( )( /)( ) 1OnT nkT n mf nn采用和前面数组最值问题类似的推导方法可得：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 章章 递归与分治策略递归与分治策略通过若干实例分析：通过若干实例分析：如何用分治法解决问题？如何用分治法解决问题？ 二分搜索技术 棋盘覆盖问题 合并排序与快速排序 平面最接近点对问题（选讲选讲）第第 2 章章 递归与分治策略递归与分治策略2.3 二分

41、搜索技术二分搜索技术给定已排好序（如升序）的 n 个元素 a 0 : n 1 ，现要在这 n 个元素中找出一特定元素 x。针对上述有序数组查找问题，可使用不同的策略求解。第第 2 章章 递归与分治策略递归与分治策略顺序搜索方法（顺序搜索方法（非分治策略非分治策略）逐个比较 a 0 : n 1 中的元素，直至找出元素 x 或者搜索遍整个数组后确定 x 不在其中。该方法的缺点该方法的缺点是没有很好地利用是没有很好地利用 n 个元素已排好序这个条件个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要 O(n) 次比较。第第 2 章章 递归与分治策略递归与分治策略二分搜索方法（二分搜索方法（分治

42、策略分治策略）的基本思想）的基本思想将 n 个元素分成个数大致相同的两半，取 a n / 2 与欲查找的 x 作比较，如果 x = a n / 2 则找到 x，算法终止；如果 x a n / 2 ，则只要在数组 a 的右半部继续搜索 x。二分搜索方法充分利用元素间的次序关系充分利用元素间的次序关系，采用分治采用分治策略策略，可在最坏情况下用 O( logn ) 时间完成搜索任务。第第 2 章章 递归与分治策略递归与分治策略为何分治策略（二分搜索方法）适于有序数组查找为何分治策略（二分搜索方法）适于有序数组查找问题？问题？（1）如果 n = 1 即只有一个元素，则只要比较这个元素和 x 就可以确

43、定 x 是否在表中。因此这个问题满足分治法的第一个适用条件满足分治法的第一个适用条件：该问题的规模缩小该问题的规模缩小到一定的程度就可以容易地解决到一定的程度就可以容易地解决。第第 2 章章 递归与分治策略递归与分治策略（2）比较 x 和 a 的中间元素 a mid ，若 x = a mid ，则 x 在数据表 L 中的位置就是mid；如果 x a mid ，同理只要在 a mid 的后面查找 x 即可。无论是在前面还是后面查找 x，其方法都和在 a 中查找 x 一样，只不过是查找的规模缩小了。这就说明此问题满足满足分治法的第二个适用条件分治法的第二个适用条件：该问题可以分解为若干个规模该问题

44、可以分解为若干个规模较小的相同问题较小的相同问题。第第 2 章章 递归与分治策略递归与分治策略（3）提出的问题是从数据表 L 中找出 x，无论是原始表还是缩小规模的表，该问题都是一样的，所以此问题满足分治法的第三个适用条件：分解出的子满足分治法的第三个适用条件：分解出的子问题的解可以合并为原问题的解问题的解可以合并为原问题的解。（4）很显然此问题分解出的子问题相互独立，即在 a mid 的前面或后面查找 x 是独立的子问题，因此满足分治法的第四个适用条件满足分治法的第四个适用条件：分解出的各个分解出的各个子问题是相互独立的子问题是相互独立的。第第 2 章章 递归与分治策略递归与分治策略/ 基于

45、分治策略的二分查找算法（递归形式）基于分治策略的二分查找算法（递归形式）.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, middle + 1, right, x ); else retu

46、rn 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; return -1; / 未找到未找到 x第第 2 章章

47、 递归与分治策略递归与分治策略算法复杂性分析（非递归形式）算法复杂性分析（非递归形式）每执行一次算法的 while 循环，待搜索数组的大小减少一半。因此，在最坏情况下，在最坏情况下，while 循环被执行了循环被执行了 O( logn ) 次次。循环体内运算需要 O( 1 ) 时间，因此整整个算法在最坏情况下的计算时间复杂性为个算法在最坏情况下的计算时间复杂性为 O( logn ) 。第第 2 章章 递归与分治策略递归与分治策略第第 2 章章 递归与分治策略递归与分治策略二分搜索法的思想易于理解，应用广泛。但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在 1946 年就

48、出现了，但是第一个完全正确的二分搜索算法直到 1962 年才出现。Bentley 在他的著作Writing Correct Programs中写道，90%的计算机专家不能在的计算机专家不能在 2 小时内写出完全正确的二小时内写出完全正确的二分搜索算法分搜索算法。思考题：思考题：教材 算法分析题算法分析题 2 的 2-2 题（P36）。第第 2 章章 递归与分治策略递归与分治策略【练习题练习题】给定给定 a，用分治法设计出求，用分治法设计出求 an 的算法。的算法。【分析】第第 2 章章 递归与分治策略递归与分治策略2.4 棋盘覆盖问题棋盘覆盖问题在一个 2k 2k 个方格组成的棋盘中，恰有一个

49、方格与其他方格不同，称该方格为一特殊方格特殊方格，且称该棋盘为一特殊棋盘特殊棋盘。显然特殊方格在棋盘上出现的位置有 4k 种情形（ 2k 2k = 4k），对 k 0，有 4k 种不同的特殊棋盘。下图 (a) 中的特殊棋盘是当 k = 2 时 16 个特殊棋盘中的一个。第第 2 章章 递归与分治策略递归与分治策略棋盘覆盖问题中的特殊棋盘与棋盘覆盖问题中的特殊棋盘与 L 型骨牌型骨牌棋盘覆盖问题是指用下图 (b)-(e)中所示的 4 种不同形态的 L 型骨牌去覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且(b)-(e)中任何 2 个 L 型骨牌不得重叠覆盖。第第 2 章章 递归与分治策略递归与

50、分治策略棋盘覆盖问题初看起来很难下手解决，但仔细思考后可以采用分治策略分治策略设计针对该问题的一个巧妙解法：如下图所示，当 k 0 时，将 2k 2k 棋盘分割为 4 个 2k-1 2k-1 子棋盘，如图 (a) 所示。显然特殊方格必位于图 (a) 中 4 个较小子棋盘之一中，其余 3 个子棋盘中则无特殊方格。为了将这为了将这 3 个个无特殊方格的子棋盘转化为特殊棋盘，可以用一个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L 型骨型骨牌覆盖这牌覆盖这 3 个较小棋盘的会合处个较小棋盘的会合处，如图 (b) 和 (c) 所示。从而将原问题转化为 4 个较小规模的棋盘覆盖问题。递归地使用这种分割

51、，直至棋盘简化为棋盘 11（易于求解易于求解）。第第 2 章章 递归与分治策略递归与分治策略分治法求解棋盘覆盖问题示意图分治法求解棋盘覆盖问题示意图第第 2 章章 递归与分治策略递归与分治策略棋盘覆盖问题的数据结构棋盘覆盖问题的数据结构（1）棋盘棋盘：可以用一个二维整型数组 Board size size 表示一个棋盘，其中，size = 2k。为了在递归处理的过程中使用同一个棋盘，将数组 Board 设为全局变量；（2）子棋盘子棋盘：整个棋盘用二维数组 Board size size 表示，其中的子棋盘由棋盘左上角的下标（行号、列号行号、列号） tr、tc 和棋盘大小 s 表示；（3）特殊方

52、格特殊方格：用 Board dr dc 表示特殊方格，dr 和 dc 是该特殊方格在二维数组 Board 中的下标（行号、列号行号、列号）；（4） L 型骨牌型骨牌：一个 2k 2k 的棋盘中有一个特殊方格，用到 L 型骨牌的个数为 ( 4k 1 ) / 3，将所有将所有 L 型骨牌从型骨牌从 1 开始连续编号（形状相同的开始连续编号（形状相同的骨牌可能采用不同的编号），用一个全局变量骨牌可能采用不同的编号），用一个全局变量 t 表示表示。第第 2 章章 递归与分治策略递归与分治策略棋盘覆盖问题的分治算法代码棋盘覆盖问题的分治算法代码int tile = 1; / L 型骨牌的编号型骨牌的编号

53、( 递增递增 )int Board 100 100 ; / 棋盘棋盘/ 递归方式实现棋盘覆盖算法递归方式实现棋盘覆盖算法./ tr - 当前棋盘左上角的行号当前棋盘左上角的行号/ tc - 当前棋盘左上角的列号当前棋盘左上角的列号/ dr - 当前特殊方格所在的行号当前特殊方格所在的行号/ dc - 当前特殊方格所在的列号当前特殊方格所在的列号/ size - 当前棋盘的大小：当前棋盘的大小：2 kvoid ChessBoard( int tr, int tc, int dr, int dc, int size ) if ( size = 1 ) / 棋盘方格大小为棋盘方格大小为 1, 说明递

54、归到最里层说明递归到最里层. return;第第 2 章章 递归与分治策略递归与分治策略 int t = tile+; / 每次递增每次递增 1( L 型骨牌编号型骨牌编号, 注意这里是连续编号注意这里是连续编号 ). int s = size / 2; / 分割棋盘分割棋盘 / 检查特殊方块是否在左上角子棋盘中检查特殊方块是否在左上角子棋盘中. if ( ( dr tr + s ) & ( dc tc + s ) ) ChessBoard( tr, tc, dr, dc, s ); else / 不在不在, 将该子棋盘右下角的方块视为特殊方块将该子棋盘右下角的方块视为特殊方块. Board

55、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 + s, s ); / 检查特殊方块是否在左下角子棋盘中检查特殊方

56、块是否在左下角子棋盘中. 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 章章 递归与分治策略递归与分治策略骨牌编号从 1 开始，特殊方格编号为 0。如果是一个 4 4 的棋盘，特殊方格为 ( 2, 2 )，则最终生成的棋盘 Board 数组内容为：2 2 3 3 2 1 1 3

57、 4 1 0 5 4 4 5 5第第 2 章章 递归与分治策略递归与分治策略上述代码采用了分治思想。首先将棋盘一分为四，则特殊方格必位于 4 个子棋盘之一。然后用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处，从而将原问题转化为 4 个较小规模的棋盘覆盖问题。之后分别处理左上角、右上角、左下角和右下角 4 个子棋盘。上述代码中有如下一个细节需要加以解释上述代码中有如下一个细节需要加以解释：/ 检查特殊方块是否在左上角子棋盘中检查特殊方块是否在左上角子棋盘中.if ( ( dr tr + s ) & ( dc tc + s ) ) ChessBoard( tr, tc, dr, dc, s );

58、else / 不在不在, 将该子棋盘右下角的方块视为特殊方块将该子棋盘右下角的方块视为特殊方块. Board tr + s - 1 tc + s - 1 = t; ChessBoard( tr, tc, tr + s - 1, tc + s - 1, s );第第 2 章章 递归与分治策略递归与分治策略这段指令首先检查特殊方块是否在左上角子棋盘中，如果是说明满足递归条件直接递归处理；如果特殊方块不在左上角子棋如果特殊方块不在左上角子棋盘中，则将该子棋盘右下角的方块视为特殊方块盘中，则将该子棋盘右下角的方块视为特殊方块。原因如下：分治法求解棋盘覆盖问题示意图分治法求解棋盘覆盖问题示意图第第 2

59、章章 递归与分治策略递归与分治策略上图 (a) 表示特殊方块在左上角子棋盘中，如果特殊方块不在左上角子棋盘中，那么它必然位于左下角、右上角和右下角之一，如图(b)-(d)所示。那么必须采用如图(b)-(d)所示的 L 型骨牌来覆盖棋盘，不管是这三种覆盖情况中的哪一种，不管是这三种覆盖情况中的哪一种，一定会有一个方块覆盖在左上角子棋盘的右下角，如图一定会有一个方块覆盖在左上角子棋盘的右下角，如图(b)-(d)中的中的“*”符号所示符号所示。这就意味着如果特殊方块不在左上如果特殊方块不在左上角子棋盘中，就可以将左上角子棋盘右下角的方块视为特角子棋盘中，就可以将左上角子棋盘右下角的方块视为特殊方块殊

60、方块。如果特殊方块不在左下角、右上角和右下角子棋盘中，则可以类似处理。第第 2 章章 递归与分治策略递归与分治策略“棋盘覆盖棋盘覆盖”演示程序演示程序第第 2 章章 递归与分治策略递归与分治策略2.5 合并排序与快速排序合并排序与快速排序排序排序是计算机内经常进行的一种操作，其目的其目的是使一串是使一串记录记录，按照其中的某个或某些，按照其中的某个或某些关键字关键字的大小，递增或递减排列的大小，递增或递减排列。排序是一种基本操作，是应用程序的基础。第第 2 章章 递归与分治策略递归与分治策略【例例】用百度搜索网页，搜索结果就是排序后的结果（各个网页网页就是记录记录，按照某种算法计算网页和用户检