离散数学─归纳与递归 南京大学计算机科学与技术系

Presentation on theme: "离散数学─归纳与递归 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─归纳与递归 南京大学计算机科学与技术系

2 内容提要 递归定义 结构归纳法 递归算法

3 递归定义（N上的函数） 递归地定义自然数集合N上的函数。 举例，阶乘函数F(n)=n!的递归定义 基础步骤：指定这个函数在0处的值；
递归步骤：给出从较小处的值来求出当前的值之规则。 举例，阶乘函数F(n)=n!的递归定义 F(0)=1 F(n)=nF(n-1) for n>0

4 Fibonacci 序列 Fibonacci 序列 {fn} 定义如下 其前几个数 证明：对任意n  0， 其中， f0 = 0,
fn = fn – 1 + fn –2, 对任意n  2. 其前几个数 0, 1, 1, 2, 3, 5, 8, … 证明：对任意n  0， 其中，

5 归纳证明: Fibonacci 序列 验证：当n=0,1时，陈述正确。 对于k+1,
注意：2 =  + 1，且n + 1 = n + n – 1 对任意n  1.

6 归纳证明: Fibonacci 序列

7 递归定义（集合） 递归地定义集合。 举例，正整数集合的一个子集S，定义如下： 基础步骤：指定一些初始元素；
递归步骤：给出从集合中的元素来构造新元素之规则； 排斥规则（只包含上述步骤生成的那些元素）默认成立 举例，正整数集合的一个子集S，定义如下： 2S 若xS且yS，则 x+yS。

8 递归定义（举例） 字母表上的字符串集合*。 字符串的长度（ *上的函数l）。 基础步骤：* （表示空串）;
递归步骤：若 * 且x  ，则x * 。 字符串的长度（ *上的函数l）。 基础步骤：l()=0; 递归步骤：l(x) = l() +1, 若 * 且x  

9 递归定义（举例） *上的字符串连接运算。 基础步骤：若 *，则  =;
递归步骤：若1 * 且2 * 以及x  ，则 1  (2 x) = (1  2) x 。 // 1  2通常也写成1 2

10 递归定义（举例） 复合命题的合式公式。 基础步骤：T, F, p都是合式公式，其中p是命题变元;
递归步骤：若E和F是合式公式，则 (E)、(EF)、 (EF)和(EF) 都是合式公式。

11 结构归纳法 关于递归定义的集合的命题，进行结构归纳证明。 结构归纳法的有效性源于自然数上的数学归纳法
基础步骤：证明对于初始元素来说，命题成立; 递归步骤：针对生产新元素的规则，若相关元素满足命题，则新元素也满足命题 结构归纳法的有效性源于自然数上的数学归纳法

12 结构归纳法（举例） l(xy) = l(x) + l(y), x和y属于 * 。 证明
设P(y)表示：每当x属于 * ，就有l(xy) = l(x) + l(y) 。 基础步骤：每当x属于 * ，就有l(x) = l(x) + l() 。 递归步骤：假设P(y)为真，a属于 , 要证P(ya)为真。 即：每当x属于 * ，就有l(xya) = l(x) + l(ya) P(y)为真，l(xy) = l(x) + l(y) l(xya)= l(xy)+1= l(x) + l(y)+1=l(x) + l(ya)

13 广义结构归纳法（举例） NN是良序的 递归定义am,n 归纳证明 am,n= m + n(n+1)/2 a0,0 = 0
am,n= am-1,n +1 (n=0, m>0) am,n= am,n-1 +n (n>0) 归纳证明 am,n= m + n(n+1)/2

14 递归算法（欧几里德算法） 递归算法的正确性 递归算法的复杂性 （时间、空间）
function gcd(a, b) // ab0, a>0 if b=0 return a else return gcd(b, a mod b) 递归算法的正确性 递归算法的复杂性 （时间、空间）

15 欧几里德算法的复杂性 Let r0=a, r1=b. qi1 for 1in qn2 because qn= rn-1/rn 1
Let r0=a, r1=b. qi1 for 1in qn2 because qn= rn-1/rn 1 rn1= f2, rn-12rn 2= f3 b=r1r2+r3 fn+fn –1=fn+1n-1 log10 b  (n-1)log10  for n2 log10  >1/5

16 递归算法的设计

17 作业 教材[4.3, 4.4] P ：24, 32, 34, 47, 52 P ：36, 37