PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

夙钢禹
5 years ago
Views:

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

2 内容提要归纳数学归纳法强数学归纳法运用良序公理来证明递归递归定义结构归纳法递归算法

3 数学归纳法

4 数学归纳法 ( 有效性 ) 良序公理正整数集合的非空子集都有一个最小元素数学归纳法的有效性 ( 归谬法 ) 假设 n P(n) 不成立, 则 n (P(n)) 成立. 令 S={ n + P(n)},S 是非空子集. 根据良序公理,S 有最小元素, 记为 m, m1 (m-1)s, 即 P(m-1) 成立. 根据归纳步骤,P(m) 成立, 即 ms, 矛盾. 因此,n P(n) 成立.

5 数学归纳法 ( 举例 ) H k =1+1/2+ +1/k (k 为正整数 ) 证明 :H 2n 1+n/2 (n 为正整数 ) 基础步骤 :P(1) 为真, H 2 =1+1/2 归纳步骤 : 对任意正整数 k, P(k) P(k+1). H k+1 2 = H 2k +1/(2 k +1)+ +1/2 k+1 (1+k/2)+2 k (1/2 k+1 ) =1+(1+k)/2 因此, 对任意正整数 n, P(n) 成立.

6 数学归纳法 ( 举例 ) 猜测前 n 个奇数的求和公式, 并证明之 1=1 1+3= = = (2n-1)=n 2 (n 为正整数 ) 运用数学归纳法证明 ( 练习 )

7 运用数学归纳法时犯的错误

8 数学归纳法证明时常见错误

9 数学归纳法证明时常见错误

10 强数学归纳法

11 强数学归纳法 ( 一般形式 ) 设 P(n) 是与整数 n 有关的陈述, a 和 b 是两个给定的整数, 且 a b. 如果能够证明下列陈述 P(a), P(a +1),, P(b). 对任意 k b, P(a) P(k)P(k+1) 则下列陈述成立对任意 n a, P(n).

12 强数学归纳法 ( 有效性 ) { nz n a } 是良序的良序集 : 该集合的非空子集都有一个最小元素数学归纳法的有效性 ( 归谬法 ) 假设 n P(n) 不成立, 则 n (P(n)) 成立. 令 S={ n (na) P(n) },S 是非空子集. 根据良序公理,S 有最小元素, 记为 m, m>a a,, (m-1)s, 即 P(a),, P(m-1) 成立. 根据归纳步骤,P(m) 成立, 即 ms, 矛盾. 因此,n P(n) 成立.

13 强数学归纳法 ( 举例 ) 任意整数 n(n 2) 可分解为 ( 若干个 ) 素数的乘积 n = 2. 考察 n+1. 用 4 分和 5 分就可以组成 12 分及以上的每种邮资. P(12), P(13), P(14), P(15). 对任意 k 15, P(12) P(k)P(k+1)

14 ( 强 ) 数学归纳法 ( 举例 ) 对每个正整数 n 4,n! 2 n 基础步骤 :P(4) 为真,24 16 归纳步骤 : 对任意正整数 k 4, P(k) P(k+1). (k+1)!= (k+1) k! (k+1) 2 k 2 k+1 因此, 对任意正整数 n 4, P(n) 成立.

15 运用良序公理来证明 ( 举例 ) 设 a 是整数, d 是正整数, 则存在唯一的整数 q 和 r 满足 0 r < d a =dq+ r 证明令 S={a-dq 0a-dq,qZ},S 非空. 非负整数集合具有良序性 S 有最小元, 记为 r 0 = a-dq 0. 可证 0 r 0 < d 唯一性证明, 0 r 1 - r 0 = d (q 0 -q 1 ) d, 因此,q 1 =q 0

16 运用良序公理来证明 ( 举例 ) 在循环赛胜果图中, 若存在长度为 m(m3) 的回路, 则必定存在长度为 3 的回路备注 : a i a j 表示 a i 赢了 a j 证明设最短回路的长度为 k // 良序公理的保证假设 k3 a 1 a 2 a 3 a k a 1 若 a 3 a 1, 存在长度为 3 的回路, 矛盾若 a 1 a 3, 存在长度为 (k-1) 的回路, 矛盾

17 递归定义 (N 上的函数 ) 递归地定义自然数集合 N 上的函数基础步骤 : 指定这个函数在 0 处的值 ; 递归步骤 : 给出从较小处的值来求出当前的值之规则举例, 阶乘函数 F(n)=n! 的递归定义 F(0)=1 F(n)=nF(n-1) for n>0 17

18 Fibonacci 序列 Fibonacci 序列 {f n } 定义如下 f 0 = 0, f 1 = 1, f n = f n 1 + f n 2, 对任意 n 2. 其前几个数 0, 1, 1, 2, 3, 5, 8, 证明 : 对对任意 n 0, f n n n 其中, 1 5 1,

19 归纳证明 : Fibonacci 序列 k k k k k k k k k k k k k f f f 验证 : 当 n=0,1 时, 陈述正确对于 k+1, 注意 : 2 = + 1, 且 n + 1 = n + n 1 对任意 n 1. 19

20 递归定义 ( 集合 ) 递归地定义集合基础步骤 : 指定一些初始元素 ; 递归步骤 : 给出从集合中的元素来构造新元素之规则 ; 排斥规则 ( 只包含上述步骤生成的那些元素 ) 默认成立举例, 正整数集合的子集 S xs 若 xs 且 ys, 则 x+ys 20

21 递归定义 ( 举例 ) 字母表上的字符串集合 * 基础步骤 : * ( 表示空串 ); 递归步骤 : 若 * 且 x, 则 x * 字符串的长度 ( * 上的函数 l) 基础步骤 :l()=0; 递归步骤 :l(x) = l() +1, 若 * 且 x 21

22 递归定义 ( 举例 ) * 上的字符串连接运算 (Concatenation) 基础步骤 : 若 *, 则 =; 递归步骤 : 若 1 * 且 2 * 以及 x, 则 1 ( 2 x) = ( 1 2 ) x // 1 2 通常也写成

23 递归定义 ( 举例 ) 复合命题的合式公式基础步骤 :T, F, s 都是合式公式, 其中 s 是命题变元 ; 递归步骤 : 若 E 和 F 是合式公式, 则 (E) (EF) (EF) (EF) 和 (EF) 都是合式公式 23

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

25 结构归纳法 ( 举例 ) 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) 25

26 广义结构归纳法 ( 举例 ) NN 是良序的 ( 字典序 ) 递归定义 a m,n a 0,0 = 0 a m,n = a m-1,n +1 (n=0, m>0) a m,n = a m,n-1 +n (n>0) 归纳证明 a m,n = m+n(n+1)/2 26

27 递归算法举例 : 欧几里德算法 function gcd(a, b) // ab0, a>0 if b=0 return a else return gcd(b, a mod b) 递归算法的正确性递归算法的复杂性 ( 时间空间 ) 27

28 递归与迭代 n! fibonacci(n) 正确性如何保证? 28

29 作业见课程网站

T(1) = 1 T(n) = 2T(n-1) +1 void hanoi(int n,char one, two, three) // 将 n 个盘从 one 座借助 two 座, 移到 three

30 递归思维 : 例 1 汉诺塔问题 : How many moves are need to move all the disks to the third peg by moving only one at a time and never placing a disk on top of a smaller one. T(1) = 1 T(n) = 2T(n-1) +1 void hanoi(int n,char one, two, three) // 将 n 个盘从 one 座借助 two 座, 移到 three 座 { void move(char x,char y); if(n==1) then move(one,three); else { hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } }

31 汉诺塔问题的解 T(n) = 2T(n-1) + 1 2T(n-1) = 4T(n-2) + 2 4T(n-2) = 8T(n-3) + 4. T(n) = 2 n -1 2 n-2 T(2) = 2 n-1 T(1) + 2 n-2

32 递归思维 : 例 2 Cutting the plane How many sections can be generated at most by n straight lines with infinite length? Intersecting all n-1 existing lines to get as most sections as possible L(0) = 1 L(n) = L(n-1) +n Line n

33 Solution of Cutting the Plane L(n) = L(n-1)+n = L(n-2)+(n-1)+n = L(n-3)+(n-2)+(n-1)+n = = L(0) (n-2)+(n-1)+n L(n) = n(n+1)/2 + 1

34 递归思维 : 例 3 Josephus Problem Live or die, it s a problem! Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle. We use a simpler version: every second...

35 10 9 Make a Try: for n= survivor

36 For 2n Persons (n=1,2,3,... ) 2n 1 2 2n-1 3 2n n-3 5 n persons left k+1 k-1 k k+3 k+1 k-1 The solution is: newnumber (J(n)) And the newnumber(k) is... 2k-1

37 And What about 2n+1 Persons (n=1,2,3,... ) 1 2n+1 2 2n 3 2n n-1 7 k+1 k k-1 do the same: n persons left k+3 k+1 k-1 The solution is: newnumber (J(n)) And for the time, the newnumber(k) is... 2k+1

38 Solution in Recursive Equations

39 Explicit Solution for small n s

40 Eureka! If we write n in the form n = 2 m + l, (where 2 m is the largest power of 2 not exceeding n and where l is what's left), the solution to our recurrence seems to be: As an example: J(100) = J(64+36) = 36*2+1 = 73

41 Binary Representation Suppose n s binary expansion is : then:

数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数

数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数 .. 数学分析 (I) 短课程 [Part 2] 自然数整数和有理数孙伟华东师范大学数学系算子代数中心 Week 2 to 18. Fall 2014 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014 1 / 78 3. 自然数理论初步孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014