计算机算法基础(第3章).ppt

文档介绍：计科学院李刚
手机 **********
电子邮箱 LQY5942@
计算机算法基础
章节安排
第 3 章递归算法√
第 4 章分治法√
第 5 章贪心方法√
第 6 章动态规划√
第 7 章检索与周游√
第 8 章回溯法√
第 9 章分枝-限界√
第10章 NP-问题⊙
第11章并行算法⊙
第 3 章递归算法
递归和消去递归
递归
直接或间接地调用自身
递归是一种强有力的设计方法
递归的效率问题
2 使用递归的准则
如果待解决的问题具备下列两个特性,就可以考虑使用递归
1) 复杂的问题转换为简单的1个或几个子问题;
2) 最简单的问题可以直接解决
经典递归问题
兔子的问题
假设小兔子每 1 个月长成大兔子,大兔子每 1 个月生一个小兔子。假设第 1 个月有 1 只小兔子,不考虑兔子的寿命,求 n 个月后有多少只兔子?
例1 斐波那契(i)序列:
F0= F1 = 1
Fi = Fi-1 + Fi-2 (i>1)
算法1 求斐波那契数
procedure F(n)
//返回第n个斐波那契数//
integer n
if n ≤ 1 then return(1)
else return(F(n-1) + F(n-2))
endif
end F
例2 欧几里得算法
已知两个非负整数a和b,且a>b≥0,求这两个数的最大公因数。
辗转相除法:若b=0,则a和b的最大公因数等于a;若b>0,则a和b的最大公因数等于b和用b除a的余数的最大公因数。
算法2 求最大公因数
procedure GCD(a,b) // 约定a>b //
if b=0 then return(a)
else return (GCD(b,a mod b))
endif
end GCD
例:GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2