《计算机算法设计与分析》PPT第二章 递归与分治策略

第2章 递归与分治策略

2014-1-12

学习要点：

理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。(1)二分搜索技术 (2)大整数乘法 (3)Strassen矩阵乘法 (4)棋盘覆盖 (5)合并排序和快速排序 (6)线性时间选择 (7)最接近点对问题 (8)循环赛日程表

2014-1-12

算法总体思想

将要求解的较大规模的问题分割成 k个更小规模的子问 对这k个子问题分别求解。如果子问题的规模仍然不够 题。 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。

T(n)

=

n

T(n/2)2014-1-12

T(n/2)

T(n/2)

T(n/2)3

将求出的小规模的问题的解合并为一个更大规模的问 对这 k个子问题分别求解。如果子问题的规模仍然不够 题的解，自底向上逐步求出原来问题的解。 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。

T(n)n/2

=n/2

nn/2 n/2

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/42014-1-12 4

将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。

T(n)n/2

=n/2

nn/2 n/2

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/42014-1-12 5

将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。

n = 分治法的设计思想： T(n) 将一个难以直接解决的大问题，分割成一些规 模较小的相同问题，以便各个击破，分而治之。 n/2 n/2 n/2 n/2 凡治众如治寡，分数是也。 ----孙子兵法2014-1-12 6

T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4

2.1 递归的概念

递归算法：直接或间接地调用自身的算法。 递归函数：用函数自身给出定义的函数。 由分治法产生的子问题往往是原问题的较小模式，方 便使用递归技术。 此时，反复应用分治手段，可使子问题与原问题类型 一致而规模不断缩小，最终使子问题缩小到很容易直 接求出其解。 自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设 计之中，并由此产生许多高效算法。 下面来看几个实例。7

2014-1-12

例1

阶乘函数 阶乘函数可递归地定义为：

边界条件

n 0 1 n! n(n 1)! n 0递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。2014-1-12 8

例2 Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55

, ,称为 Fibonacci数列。 边界条件 它可以递归地定义为： 1 n 0 F ( n) 1 n 1 F (n 1) F (n 2) n 1 递归方程 第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 9 2014-1-12

例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这 个函数是双递归函数。 Ackerman函数A(n,m)定义如下：

A(1,0) 2 A(0, m) 1 m 0 A(n,0) n 2 n 2 A(n, m) A( A(n 1, m), m 1) n, m 110 10

例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：

n! 1 2 3 (n 1) nn 1 n 1 1 5 1 1 5 F ( n) 2 2 5

但本例中的Ackerman函数却无法找到非递归的定义。11 11

例3 Ackerman函数 A(n,m)的自变量m的每一个值都定义了一个单变量函数： m=0时，A(n,0)=n+2 m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和 A(1,1)=2故A(n,1)=2*n m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和 A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2n 。

12

m=3时，类似的可以推出

2 n12

2

2 2

m=4时，A(n,4)的增长速度非常快，以至于没有适当的 数学式子来表示这一函数。

例3 Ackerman函数 定义单变量的Ackerman函数A(n)为，A(n)=A(n,n)。 定义其拟逆函数α(n)为：α(n)=min{k|A(k)≥n}。 即α(n)是使n≤A(k)成立的最小的k值。 α(n)在复杂度分析中常遇到。对于通常所见到的 正整数n,有α(n)≤4。但在理论上α(n)没有上界， 随着n的增加，它以难以想象的慢速度趋向正无穷 大。

13

例4 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (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)构成。 根据这一递归定义，可以设计相应的递归算法，见P112014-1-12 14

例4

排列问题

void Perm(Type list[],int k,int m){//递归产生list[k:m]的所有排列 if(k==m) {//只剩下一个元素 for(int i=0;i<=m;i++) cout<<list[i]; cout<<endl; } else//还有多个元素待排列，递归产生排列 for(int i=k;i<=m;i++){ Swap(list[k],list[i]); Perm(list,k+1,m); Swap(list[k],list[i]; } }15 15

算法Perm(list,k,m)递归地产生所有前缀 是list[0:k-1],且后缀是list[k:m]的全 排列的所有排列。

2014-1-12