第2章递归与分治策略PPT课件

第2章 递归与分治策略
作业
.
1
学习要点:
• 理解递归的概念。
• 掌握设计有效算法的分治策略。
• 通过下面的范例学习分治策略设计技巧。
（1）二分搜索技术；
（2）大整数乘法；
（3）Strassen矩阵乘法；
（4）棋盘覆盖；
（5）合并排序和快速排序；
（6）线性时间选择；
（7）最接近点对问题；
（8）循环赛日程表。
A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。
2 m=3时，类似的可以推出 222 ，其中 2的层数为n
m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式 子来表示这一函数。
.
11
2.1 递归的概念
例3 Ackerman函数 定义单变量的Ackerman函数A(n)为，A(n)=A(n，
.
10
2.1 递归的概念
例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)，和
.
2
2.1 递归的概念与思想
直接或间接地调用自身的算法称为递归算法。 使算法的描述简单明了、易于理解、容易编程和
验证。 很多复杂问题使用递归技术，可能容易而有效地
进行求解。 计算机软件领域，是一种非常重要并且不可或缺
的算法
.
3
2.1 递归的概念与思想
在思想方法上，递归技术分为：
基于归纳法的递归 把归纳法的思想应用于算法设计中
的某种运算或处理。
例如 a1是问题P(1)的解，若a2=p(a1),则a2是问 题P(2)的解；以此类推，若an-1是问题P(n-1)的 解，且an=p(an-1),则an是问题P(n)的解。
.
5
2.1 递归的概念
用函数自身给出定义的函数称为递归函数。
例1 阶乘函数 阶乘函数可递归地定义为：
n!n(n11)!
n)。 定义其拟逆函数B(n)为：B(n)=min{k｜A(k)≥n}。
即B(n)是使n≤A(k)成立的最小的k值。 A(0)=1,A(1)=2,A(2)=4,A(3)=16推知
B(1)=0,B(2)=1,B(3)=B(4)=2和 B(5)=…=B(16)=3。由此可以看出B(n)的增长速度 非常慢。
边界条件 递归方程
第n个Fibonacci数可递归地计算如下：
int fibonacci(int n)
{
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
.
8
2.1 递归的概念
例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数 是双递归函数。 Ackerman函数A(n，m)定义如下：
n0 n0
边界条件
递归方程
边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。
.
6
2.1 递归的概念
n阶乘的递归计算如下： Int factorial(int n) {
if(n==0) return 1;
return n*factorial(n-1);
B(n)在复杂度分析中常遇到。A(4)=222…2其中2的 层数为65535，对于通常所见到的正整数n，有 B(n)≤4。但在理论上α(n)没有上界，随着n的增加， 它以难以想象的慢速度趋向正无穷大。
.
12
2.1 递归的概念
例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)法如下： void Perm(Type list[],int k,int m)
建立递归方程：
{ if(k==m) { //只剩下1个元素 for(int i=0;i<=m;i++) cout <<list[i];
f(1)n f (n) nf(n1)
cout<<endl; }
}
递归方程为：
f(0)0 f(n) f(n1)1
此类递归方程时间复
杂度为 (n)
.
7
2.1 递归的概念
例2 Fibonacci(斐波那契)数列
无穷数列1，1，2，3，5，8，13，21，34，55，……，称为
Fibonacci数列。它可以递归地定义为：
1
n0
F(n)
1
n1
F(n1)F(n2) n1
A(1,0) 2
A(0,m) 1
m0
A(n,0) n2
n2
A(n,m)A(A(n1,m),m1) n,m1
.
9
2.1 递归的概念
例3 Ackerman函数 前2例中的函数都可以找到相应的非递归方式定义：
n ! 1 2 3 (n 1 )n
F(n)15125n1125n1
本例中的Ackerman函数却无法找到非递归的定义。
基于分治法的递归 把问题划分成一个或多个子问题递归地进行求解
.
4
2.1 递归的概念与思想
对规模为n的问题P(n)，归纳法思想： (1) 基础步： a 1是问题P(1)的解 (2)归纳步：对所有的k,1<k<n,若b是问题P(k)的 解，则p(b)是问题P(k+1)的解。其中， p(b)是对b
算法的运行时间：
else //还有多个元素待排列，递归产生排列 for(int i=k;i<=m;i++)
(nn!)
{
Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i];
}
}
算法Perm（list,k,m）递归地产生所有前缀是 list[0:k-1]，且后 缀是list[k:m]的全排列的所有排列，如果是Perm(list,0,n-1)则 产生list[0:n-1]的全排列。