文档介绍：离散数学
黄晓宇
HuangSir@
本讲内容
递归算法设计
简单的递归算法复杂度分析
回顾
一个递归函数(伪代码)是调用自身的函数。一个递归算法是包含递归函数的算法。
递归算法的基本思想:分而治之。
即将问题分解成与初始问题同类型的子问题来求解,每一个子问题又可以继续分解……依次类推,直到这个过程得到的子问题可以通过一个直接的办法求解。
最后,通过组合子问题的解就可以得到初始问题的解。
阶乘
int Factorial(int n)
{
if(n<=1) return 1;
return n*Factorial(n-1);
}
选择排序(P316)
Input: s1 , . . ., sn和n
Output:以递增顺序排列的s1 , . . ., sn
递归关系?
Sort(s,n)=Sort(s-max{s},n-1)+max{s}
选择排序(二)
Procedure election_sort(S,n)
// basic
if n=1 then
return
// find max
max_index :=1
for i:=2 to n do
if Si > Smax_index then
max_index :=i
//move
swap(si, Smax_index)
call election_sort(S,n-1)
end election_sort
b1 =0
1-7 :0
8 :n-1
9-11: 0
12: bn-1
bn = n-1+ bn-1
时间复杂度分析
bn = n-1+ bn-1
= bn-1 + n-1
= (bn-2 + n-2) + n-1
= (bn-3 + n-3) + n-2 + n-1
= b1 +1+2+3+ . . . +(n-1)
= 0+ 1+2+3+ . . . +(n-1)
= (n-1)*n/2= (n2 )
递归关系
对序列a1, . . . , an,使用a1,a2… an-1表示an的等式称为递归关系。
显式地给出的a1, a2. . . , 的有限项,称为初始条件。
递归举例(i序列):
fn = fn-1 + fn-2 (n  3)
f1 =1 f2 =2
字符串
Sn不含111的n位二进制字符串的个数,计算Sn 。
以0开始的: Sn-1
以10开始的: Sn-2
以110开始的: Sn-3
Sn= Sn-1+ Sn-2+ Sn-3 n 4
字符串(二)
Sn不含111的n位二进制字符串,打印出所有Sn。
PrintS(S,n)
PrintS(S,n-1)+0
PrintS(S,n-2)+01
PrintS(S,n-3)+011
算法实现?参数设计?