第二章 递归与分治策略
1.递归的概念
直接或间接地调用自身的算法成为递归算法。用函数自身给出定义的函数成为递归函数。
2.递归实例
(1)阶乘函数
阶乘函数可递归的定义为 n!=1 n=0 n!=n*(n-1)! n>0
递归算法如下:
(2)Fibonacci 数列
Fibonacci 数列可递归地定义为 F(n)=1( n=0 或 n=1) F(n)=F(n-1)+F(n-2) n>1
递归算法如下:
(3) Ackerman 函数:双递归函数
(4)排列问题
(5)整数划分问题
(6)汉诺塔问题
递归算法如下
3.分治法的基本思想
分治法的基本思想将一个规模为 n 的问题分解为 k 个规模较小的子问题,这些子问题互相独
立且与原问题相同。递归地解决这些子问题,然后将各子问题合并得到原问题的解。
4. 主定理公式
T(n)=aT(n/b)+f(n) f(n)∈θ(n
d
) d>=0
T(n)=θ(n
d
) a<b
d
Int factorial(int n){
If(n==0)
Return 1;
Return n*factorial(n-1);
}
Int fibonacci(int n){
If(n<=1)
Return 1;
Return fibonacci(n-1)+fibonacci(n-2);
}
Void hanoi(int n,int a,int b,int c){
If(n>0){
Hanoi(n-1,a,c,b);
Move(a,b);
Hanoi(n01,c,b,a);
}
}
评论0