递归与分治策略第一部分

1、算法设计与分析,第2章 递归与分治策略,分治（Divide and Conquer）,凡治众如治寡，分数是也。 孙子兵法,治理大军团就象治理小部队一样有效，是依靠合理的组织、结构、编制。,将一个难以直接解决的大问题，合理分割成一些规模较小的相同问题，以便各个击破，这个策略就叫分而治之（分治法）。,第2章 递归与分治策略,分治法是最为重要的算法设计方法之一。 主要思想是：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。 因此分治法可以分为两个重要步骤： （1）自顶向下：将问题不断分割成小的问题。 （2）自底而上：将小问题解决来构建大问题的解。 分治和递归经常同时应用在算

2、法设计中。,第2章 递归与分治策略,将要求解的较大规模的问题分割为 k 个较小规模的子问题。对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,第2章 递归与分治策略,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,第2章 递归与分治策略,【例】找一组数的最大最小数。 直接求解：需要 n - 1 次比较来求最小数（n 个数两两比较共需要 n 1 次），然后另外 n - 2 次比较来求最大数（除去最小值的剩下 n 1 个数两两比较共需要 n 2 次）。总计为（ 2n

3、- 3）次。 分治方法 （Divide and Conquer）: （1）将数据集 S 均分为 S1 和 S2； （2）求解 S1 和 S2 中的最大和最小值； （3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )； （4）采用同样的处理方法递归处理 S1 和 S2。,第2章 递归与分治策略,min_max(S, min, max) if |S| = 2 then min min(S) max max(S) else split S evenly into S1 and S2 min_max(S1, min1, max1) min_max(S2, mi

4、n2, max2) min min(min1, min2) max max(max1, max2) ,治,分,合并,算法描述（为方便起见，假定 n 是 2 的指数倍，n 1）：,第2章 递归与分治策略,复杂度公式 T( n ) = 3n/2 2 的推导过程（要会处理类似的问题）：,第2章 递归与分治策略,第2章 递归与分治策略,教学内容和要求（讲授 6 学时，2 学时上机实验，共 8 学时） （1）递归、递归算法的设计（Ackerman 函数、排列问题、整数划分问题）（重点） （2）分治法的基本思想、算法效率分析（掌握） （3）二分搜索技术（熟练掌握） （4）棋盘覆盖（理解） （5）合并排序（

5、理解） （6）快速排序（熟练掌握）,第2章 递归与分治策略,2.1 递归的概念 （1）直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 （2）由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 （3）分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,第2章 递归与分治策略,递归实例 （1）数据结构本身固有递归特性，特别适于用递归描述：树（二叉树） 树是由 n（n 0）个

6、结点组成的有限集合。若 n = 0，称为空树；若 n 0，则： （A）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （B）除根结点以外的其它结点可以划分为m（ m 0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i = 0, 1, , m - 1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有 0 个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,第2章 递归与分治策略,树的实例 1 - 红楼梦人物关系表,树的实例 2 图像处理类谱系,第2章 递归与分治策略,二叉树是 n（n 0）个结点的有限

7、集，它或者是空集（n = 0），或者由一个根结点及两棵不相交的左子树和右子树组成。,二叉树的前序遍历 递归算法,第2章 递归与分治策略,（2）一些问题本身没有明显的递归结构，但用递归技术来求解，可使设计出的算法简捷易懂。 【例 1】阶乘函数 阶乘函数可递归地定义为：,边界条件（一般是非递归定义的初始值）与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,西安邮电大学计算机学院,第2章 递归与分治策略,int factorial( int n ) if ( n = 0 ) return 1; return n * factorial( n 1 ); ,算法

8、代码,第2章 递归与分治策略,【例 2】 Fibonacci 数列 无穷数列1，1，2，3，5，8，13，21，34，55，称为 Fibonacci数列。它可以递归地定义为：,第2章 递归与分治策略,第 n 个 Fibonacci 数可递归地计算如下： int fibonacci( int n ) if (n = 1) return 1; return fibonacci( n 1 ) + fibonacci( n 2 ); ,算法代码,西安邮电大学计算机学院,第2章 递归与分治策略,【例 3】 Ackerman 函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ac

9、kerman 函数 A(n，m) 有 2 个独立的整型变量 m = 0 和 n = 0，定义如下：,西安邮电大学计算机学院,第2章 递归与分治策略,Ackerman 函数的特点：“阶乘函数”和“Fibonacci 数列”都可以找到相应的非递归方式定义，如下：,Ackerman 函数却无法找到非递归的定义。,西安邮电大学计算机学院,第2章 递归与分治策略,Ackerman 函数 A ( n，m ) 的自变量 m 的每一个值都定义了一个单变量函数：,西安邮电大学计算机学院,第2章 递归与分治策略,西安邮电大学计算机学院,第2章 递归与分治策略,Ackerman 函数总结如下：,西安邮电大学计算机学

10、院,第2章 递归与分治策略,int Ackerman( int n, int m ) if ( m = 0) if ( n = 1 ) return 1; else return ( n + 2 ); else if( n = 0 ) return 1; else return Ackerman( Ackerman( n - 1, m ), m - 1 ); ,算法代码,西安邮电大学计算机学院,第2章 递归与分治策略,定义单变量的 Ackerman 函数 A(n) 为：A( n ) = A( n，n )。 定义其拟逆函数(n)为：( n ) = min kA( k ) n 。即 ( n ) 是

11、使 n A( k )成立的最小的 k 值。 A( 0 ) = 1 A( 1 ) = 2 A( 2 ) = 4 A( 3 ) = 16 A( 4 ) = 2 多重幂（其中 2 的层数为 65536） 可知： ( 1 ) = 0 ( 2 ) = 1 ( 3 ) = ( 4 ) = 2 ( 5 ) = = ( 16 ) = 3 ( n )的增长速度非常缓慢。 ( n )在复杂度分析中常遇到。对于通常所见到的正整数n，有 ( n ) 4 。但在理论上( n )没有上界，随着 n 的增加，它以难以想象的慢速度趋向正无穷大。,西安邮电大学计算机学院,第2章 递归与分治策略,【例 4】 排列问题 设计一个递

12、归算法生成 n 个元素 r1, r2, , rn 的全排列。 全排列：从 n 个不同元素中任取m（m n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当 m = n 时所有的排列情况叫全排列。 如 1, 2, 3 三个元素的全排列为： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 共 3！= 3 * 2 * 1 = 6 种排列,西安邮电大学计算机学院,第2章 递归与分治策略,全排列的递归算法设计 从实际例子中观察可知： （1） 1 的全排列为：1 （2） 1, 2 的全排列为：1, 2 2, 1 （3）

13、1, 2, 3 的全排列为： 1, 2, 3 1, 3, 2 2, 3 的全排列加上 1 所得 2, 1, 3 2, 3, 1 1, 3 的全排列加上 2 所得 3, 1, 2 3, 2, 1 1, 2 的全排列加上 3 所得 即：3 个元素的全排列问题可转化为求 2 个元素的全排列问题。 . 推广结论：n 个元素的全排列问题可转化为求 n - 1 个元素的全排列问题（递归设计）。,西安邮电大学计算机学院,第2章 递归与分治策略,全排列的递归算法 设 R = r1, r2, , rn 是要进行排列的 n 个元素，Ri = R - ri 。 集合 X 中元素的全排列记为 perm( X )。 (

14、 ri )perm( X ) 表示在全排列 perm( X ) 的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当 n = 1 时，perm( R ) = ( r )，其中 r 是集合 R 中唯一的元素； 当 n 1 时，perm( R ) 由 ( r1 )perm(R1)，( r2 )perm(R2)，( rn )perm(Rn)构成。,西安邮电大学计算机学院,第2章 递归与分治策略,全排列的递归算法说明示例 设 R = 1, 2, 3 ，则 n = 3，根据上述算法，产生的全排列为： 1 2, 3 2 3 3 2 （即对集合 2, 3 继续执行递归算法，下同） 2 1, 3

15、1 3 3 1 3 1, 2 1 2 2 1 即 R = 1, 2, 3 产生的全排列为： 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1,西安邮电大学计算机学院,第2章 递归与分治策略,全排列在 IT 公司的笔试面试中比较热门，百度、迅雷等大公司的校园招聘以及程序员和软件设计师的考试中都考过此题。 如下面的百度、迅雷校招笔试题中的“全排列”： 【题目】用 C+ 写一个函数, 如 Foo( const char *str ), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba。 【分析】

16、根据上述描述的算法，可知全排列的递归实现算法的规律是“全排列是从第一个数字起每个数分别与它后面的数字交换”。这样根据上述算法可以 写出示例代码如下：,西安邮电大学计算机学院,第2章 递归与分治策略,/ 全排列的递归实现（假定集合中的各个元素互不相同） #include #include void Swap( char *a, char *b ) char t = *a; *a = *b; *b = t; ,西安邮电大学计算机学院,第2章 递归与分治策略,/ k 表示当前选取到第几个数, m表示共有多少数. void AllRange(char *pszStr, int k, int m) if

17、 ( k = m ) static int s_i = 1; printf( 第%3d个排列t%sn, s_i+, pszStr); else for (int i = k; i = m; i+) / 第 i 个数分别与它后面的数字交换就能得到新的排列 Swap( pszStr + k, pszStr + i ); AllRange( pszStr, k + 1, m ); Swap( pszStr + k, pszStr + i ); ,西安邮电大学计算机学院,第2章 递归与分治策略,void Foo( char *pszStr ) AllRange( pszStr, 0, strlen(

18、pszStr ) 1 ); int main() printf( 全排列的递归实现n); char szTextStr = 123; printf(%s的全排列如下:n, szTextStr); Foo( szTextStr ); return 0; ,西安邮电大学计算机学院,第2章 递归与分治策略,运行结果如下：,西安邮电大学计算机学院,第2章 递归与分治策略,【例 5】整数划分问题 将正整数 n 表示成一系列正整数之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。 正整数 n 的这种表示称为正整数 n 的划分。求正整数n的不同划分个数。 例如正整数 6 有如

19、下 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,西安邮电大学计算机学院,第2章 递归与分治策略,再如正整数 4 有如下 5 种不同的划分： 4； 3 + 1； 2 + 2，2 + 1 + 1； 1 + 1 + 1 + 1 注意 4 = 1 + 3 和 4 = 3 + 1 被认为是同一个划分。 也可以采用如下方式表示 4 的 5 个划分： 4 , 3, 1 , 2, 2 ,

20、2, 1, 1 , 1, 1, 1, 1 ;,第2章 递归与分治策略,将正整数 n 的不同划分个数称为正整数 n 的划分数，记作 p( n )。如上述 p( 6 ) = 11。 将正整数 n 表示成一系列正整数之和：n = n1 + n2 + + nk， 其中 n1 n2 nk 1，k 1。正整数 n 的这种表示称为正整数 n 的划分。 如果 max n1, n2, , nk = m，则称划分 n = n1 + n2 + + nk 属于 n 的一个 m 划分，记为 q( n, m )。显然对于正整数划分问题而言，m = n，即计算 q( n, n ) 的值。 前面的几个例子中，问题本身都具有比

21、较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设 p( n ) 为正整数n的划分数，则难以找到递归关系。需要借助 q( n, m ) 建立递归关系。,西安邮电大学计算机学院,第2章 递归与分治策略,在这里考虑一般的 q( n, m ) 的计算，根据 n 和 m 的关系，考虑以下几种情况： （1）当 n = 1 时，不论 m 的值为多少( m 0 )，只有一种划分即 1 ; （2）当 m = 1 时，不论 n 的值为多少，只有一种划分即 n 个 1， 1, 1, 1, ., 1 ;,西安邮电大学计算机学院,第2章 递归与分治策略,（3） 当 n = m 时，根据划分中是否包含 n，

22、可以分为两种情况： （3-1）划分中包含 n 的情况，只有一个即 n ； （3-2）划分中不包含 n 的情况，这时划分中最大的数字也一定比 n 小，即 n 的 所有 ( n 1 ) 划分。（ m = n 1，即包含所有max n1, n2, , nk = n 1 的情况） 因此 q( n, m ) = q( n, n ) = 1 + q( n, n 1 ); 注意：q( n, m ) 中 m 的定义为： 如果 max n1, n2, , nk = m，则称划分 n = n1 + n2 + + nk 属于 n 的一个 m 划分，记为 q( n, m )。 当 n = m 时， max n1, n

23、2, , nk = m = n，也即 n1, n2, , nk 中的最大值小于或者等于 n 都是可以的，所以上述（3-2）是成立的。,第2章 递归与分治策略,（4）当 n m 时，根据划分中是否包含最大值 m，可以分为两种情况： （5-1）划分中包含 m 的情况，即 m, n1, n2, ., ni , 其中 n1, n2, ., ni 的和 为 n - m，可能再次出现 m（ max n1, n2, , ni = m 是可以成立的）， 因此是（ n - m）的 m 划分，因此这种划分个数为 q( n - m, m ); （5-2）划分中不包含 m 的情况，则划分中所有值都比 m 小（ m），

24、即 n 的 ( m 1 ) 划分（一定满足max n1, n2, , nk = m - 1），个数为 q( n, m 1 ); 因此 q( n, m ) = q( n - m, m ) + q( n, m 1 );,西安邮电大学计算机学院,第2章 递归与分治策略,综上可知：上面的结论具有递归定义特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，将会转换为情况（5）。而情况（5）为通用情况，属于递推的方法，其本质主要是通过减小 m 以达到回归条件，从而解决问题。 递推表达式如下：,正整数 n 的划分数 p( n ) = q( n, n )。,西安邮电大学计算机学院,第2章 递归与

25、分治策略,因此可以给出求出 q( n, m ) 的递归函数代码如下： unsigned long GetIntegerPartitionCount( int n, int m ) if ( n = 1 | m = 1 ) return 1; else if ( n m ) return GetIntegerPartitionCount( n, n ); else if ( n = m ) return 1 + GetIntegerPartitionCount( n, m 1 ); else return GetIntegerPartitionCount( n, m 1 ) + GetInteg

26、erPartitionCount( n - m, m ); ,西安邮电大学计算机学院,第2章 递归与分治策略,【例 6】Hanoi 塔问题 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的 64 片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。,汉

27、诺塔益智玩具,西安邮电大学计算机学院,第2章 递归与分治策略,如果考虑一下把 64 片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢? 这里需要递归的方法。假设有 n 片，移动次数是f( n ).显然 f( 1 )=1, f( 2 ) = 3, f( 3 ) = 7，且 f( k+1 ) = 2 * f( k ) + 1。此后不难证明 f( n ) = 2 n - 1。n = 64 时，假如每秒钟一次，一年 365 天有 31536000 秒，闰年 366 天有 31622400 秒，平均每年 31556952 秒，计算一下， 18446744073709551

28、615 / 31556952 = 584554049253.855年 这表明移完这些金片需要5845亿年以上，而地球存在至今不过 45 亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。,西安邮电大学计算机学院,第2章 递归与分治策略,Hanoi 塔问题的标准描述： 设 a, b, c 是 3 个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规

29、则 1：每次只能移动 1 个圆盘； 规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则 3：在满足移动规则 1 和 2 的前提下，可将圆盘移至 a,b,c 中任一塔座上。,Hanoi 塔的动态演示,西安邮电大学计算机学院,第2章 递归与分治策略,算法设计： （1）当 n = 1 时，只要将编号为 1 的圆盘从塔座 a 直接移到塔座 b 上即可； （2）当 n 1 时，需要利用塔座 c 作为辅助塔座。此时要设法将 n - 1 个较小的圆盘依照规则从 a 移至 c 上，然后将剩下的最大塔座从 a 移至 b 上。最后设法将 n - 1 个较小的圆盘依照规则从 c 移至 b 上。 由此可

30、见，n 个圆盘的移动问题可分解为两次 n - 1 个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出算法如下：,西安邮电大学计算机学院,第2章 递归与分治策略,void hanoi( int n, int a, int b, int c ) / 将塔座 a 上的 n 个圆盘依规则移至塔座 b 上， / 以塔座 c 作为辅助塔座 if ( n 0 ) hanoi( n - 1, a, c, b ); move( a, b ); / 将塔座 a 上编号为 n 的圆盘移至塔座 b 上 hanoi( n - 1, c, b, a ); ,西安邮电大学计算机学院,第2章 递归与分治策略,递归

31、小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 （2）用递推来实现递归函数。这种方法在时空复杂度上均有较大改善，但其适用范围有限。,西安邮电大学计算机学院,第2章 递归与分治策略,2.2 分治法的基本思想 分治法的基本思想是将一个规模为 n

32、的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 分治法所能解决的问题一般具有以下几个特征： （1）该问题规模缩小到一定的程度就可以容易地解决； 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,西安邮电大学计算机学院,第2章 递归与分治策略,（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有“最优子结构性质”。 这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。 （3）利用该问题分解出的子问题的解可以合并为该问题的解。 能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,西安邮电大学计算机学院,第2章 递归与分治策略,（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,西安邮电大学计算机学院,第2章