离散数学课件-第2章-7-2.pptVIP

CHAPTER 2 The Foundations: Algorithms, the Integers ,and Matrices 2.1 Algorithms算法 2.2 Complexity of Algorithms算法的复杂性 2.3 The Integers and Division整数和除法 2.4 Integers and Algorithm整数和算法 2.5 Applications of Number Theory数论的应用 2.6 Matrices矩阵 2.7 Recursion 递归 递归定义 引言 递归地定义函数 递归地定义集合与结构 递归算法 引言 递归与迭代 归并排序 引言 递归地定义函数 递归地定义集合与结构 引言 递归地定义函数 递归地定义集合与结构 〖Example 1〗假定f是用 f（0）=3 f（n+1）=2f（n）+3 来递归地定义的。求出f（1），f（2），f（3）和f（4） 解：从这个递归定义得出 f(1)=2f(0)+3=2*3+3=9 f(2)=2f(1)+3=2*9+3=21 f(3)=2f(2)+3=2*21+3=45 f(4)=2f(3)+3=2*45+3=93 〖Example 2〗：给出阶乘函数F(n)=n！的归纳定义 解：可以通过规定阶乘函数的初值，即F(0)=1，并且给出F(n)求出F(n+1)的规则，来定义这个函数。要得出这个结果，注意通过乘以n+1就从n！计算出(n+1)!。因此，所需要的规则是F(n+1)=(n+1)F(n)。 为了从例2里求出的递归定义来确定阶乘函数的一个值，比如F(5)=5！，有必要多次使用说明如何F(n)表示F(n+1)的规则：F(5)=5F(4)=5×4F(3)=5×4×3F(2)=5×4×3×2F(1)=5×4×3×2×1×F(0)=5×4×3×2×1×1=120 〖Example 3〗给出an的递归定义，其中a是非负零实数而且是非负整数。 解：这个递归定义包括两个部分。首先规定a0，即a0=1.然后给出从an求出an+1的规则，即对n=0，1，2，3，……来说an+1 =a* an 。这两个等式对所有非负整数唯一地定义了an. 〖Example 5〗 斐波那契数f0，f1，f2，…是用等式f0=0，f1=1，以及n=2，3，4，…来说fn=fn-1+fn-2来定义的。斐波那契数f2， f3，f4 ，f5 ，f6 是什么？ 解：因为这个定义的第一部分说f0=0和f1=1 ，所以从这个定义的第二部分得出 f2 = f1 + f0 =1+0=1 f3 = f2 + f1 =1+1=2 f4 = f3 + f2 =2+1=3 f5 = f4 + f3 =3+2=5 f6 = f5 + f4 =5+3=8 引言 递归地定义函数 递归地定义集合与结构 递归定义 引言 递归地定义函数 递归地定义集合与结构 递归算法 引言 递归与迭代 归并排序 引言 递归与迭代 归并排序 引言 递归与迭代 归并排序 递归与迭代 递归：算法容易实现，不过效率低下； 迭代：算法实现稍难，不过效率高； procedure iterative factorial (n: 正整数) x:=1 For i：= 1 to n x：＝ I × x {x是n!} procedure iterative fibonacci (n: 非负整数) If n=0 then y:=0 Else Begin x:=0 y:=1 for i：= 1 to n-1 Begin z := x + y x := y y := z end End {y是第n个斐波那契数} 引言 递归与迭代 归并排序 原理 假设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1。然后两两归并，得到?n/2?个长度为2或1的有序子序列；再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。 如何进行两路归并？ 将两个有序表的元素进行比较，小者复制到目标表中。 归并排序方法可以用递归的形式描述，即首先将待排序的记录序列分为左右两个部分，并分别将这两个部分用归并方法进行排序，然