《离散数学课件-第2章-7》由会员分享，可在线阅读，更多相关《离散数学课件-第2章-7（54页珍藏版）》请在金锄头文库上搜索。
1、1离散数学 Discrete Mathematics 汪荣贵贵 教授合肥工业业大学软软件学院专专用课课件2010.041*第二章第二章 算法基础算法基础2.1 Algorithms2.1 Algorithms算法算法 2.2 Complexity of Algorithms2.2 Complexity of Algorithms算法的复杂性算法的复杂性 2.3 The Integers and Division2.3 The Integers and Division整数和除法整数和除法 2.4 Integers and Algorithm2.4 Integers and Algorithm整
2、数和算法整数和算法 2.5 Applications of 2.5 Applications of Number TheoryNumber Theory数论的应用数论的应用 2.6 Matrices2.6 Matrices矩阵矩阵 2.7 2.7 Recursion Recursion 递归递归l( x) = l() + 1, 若x 且 * . &字符串的长长度的定义义Example 8 证证明l(xy) = l(x) + l(y) ，其中x, y * &字符串的长长度的例题题设设P(y)是命题题：每当x *时时就有l(xy) = l(x) + l(y) ；Basis Step: 先证证明P(
3、)为为真，即对对所有x *来说说有l(x) = l(x) + l()。易知，l(x) = l(x) = l(x) + 0 = l(x) + l()，即P()为为 真。Recursive Step: 假定P(y)为为真，且蕴蕴含着每当a 时时，就有 P(ya)为为真。需证证明对对每个a 来说说有l(xya) = l(x) + l(ya):根据l()定义义，有l(xya) = l(xy) + 1和l(ya) = l(y) + 1，又根据 归纳归纳 假设设，有l(xy) = l(x) + l(y)，故得出l(xya) = l(x) + l(y) + 1 = l(x) + l(ya)。23*定义义 3
4、 递归定义根树的集合，其中根树是由一个顶 点集合和连接这些顶点的边组成的，顶点集合包含的一 个特殊顶点称为树根：Solution:Basis Step: 单个顶点r是根树。Recursive Step: 假设T1,T2,Tn是根树，分别带有树根 r1,r2,rn。则如下形成的图也是根树：从树根r开始，r不属 于树根中T1,T2,Tn的任何一个，从r到r1,r2,rn中的每个都 加一条边边。&根树树的集合24*基础础步骤骤：单单个顶顶点是根树树；步骤骤1：从另一顶顶点到现现有的每个根都加一条边边；步骤骤2：从又一顶顶点到每个根都加一条边边；&建立根树树25*定义义 4 递归定义扩展二叉树的集合：
5、Solution:Basis Step: 空集合是扩展二叉树。Recursive Step: 如果T1和T2都是扩展二叉树，则存在一个 表示为T1 T2的扩展二叉树，它包含树根r和当左子树T1和右 子树T2都非空时，连接从r到这两个子树各自的根的边。&扩扩展二叉树树的集合26*&建立扩扩展二叉树树27*基础础步骤骤：空集合是扩扩展二叉树树；步骤骤1：从另一顶顶点到现现有的两个空集都加一条边边，连连 接空集的边边不必标标出；步骤骤2：左子树树和右子树树均只有根结结点，从另一顶顶点引 出两条边连边连 接左右子树树；或左右子树树分别为别为 只有根结结点 和空集，从另一顶顶点引出两条边连边连 接左右子
6、树树；步骤骤3：左右子树树分别为扩别为扩 展二叉树树，从另一顶顶点引出 两条边连边连 接左右子树树。&建立扩扩展二叉树树28*定义义 5 递归定义满二叉树的集合：Solution:Basis Step: 存在一个只含有单个顶点的满二叉树。Recursive Step: 如果T1和T2都是满满二叉树树，则则存在一个表 示为为T1 T2的满满二叉树树，它包含树树根r和连连接从r到左子树树T1 和右子树树T2各自的根的边边。&满满二叉树树的集合29*&建立满满二叉树树30*基础础步骤骤：单单个顶顶点是满树满树 ；步骤骤1：两个单单个顶顶点均是满树满树 ，分别别作为为左右子树树 各加一条边连边连 接至
7、同一顶顶点；步骤骤2：左右子树树均为满树为满树 ，从又一顶顶点到每个满树满树 的根都加一条边边；&递递 归归递归定义 引言 递归地定义函数 递归地定义集合与结构 递归算法 引言 递归与迭代 归并排序31*&递归递归 算法引言 递归与迭代 归并排序32*33*procedure factorial(n: positive integer) if n=0 thenfactorial(n):=1 elsefactorial(n) := nfactorial(n-1) Example 1Example 1 Give a recursive algorithm for computing the fac
8、torial function n! .给出计算阶乘n！的递归算法&递归递归 算法例题题34*Recursive Algorithms Recursive Algorithms 递归算法递归算法定义义 1 An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input. 若一个算法通过把问题规约到带更小的输入的相同问题的实例，来解决原来的问 题，则这个算法称为递归的Once you have figured o
9、ut a recursive definition for a function, one can immediately turn it into a recursive algorithm in languages (such as Java) which can handle recursion.35*Algorithm 2 A Recursive Algorithm for Computing gad(a,b).procedure gcd(a,b: nonnegative integers with ab) if a=0 thengcd(a,b):=b elsegcd(a,b):= g
10、cd(b mod a,a) Example 2Example 2 Give a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and b with ab.给出满足ab的两个非负整数a和b的最大公因子的递归算法。36*Algorithm 3 A Recursive Linear Search Algorithm).procedure search(i, j, x) if ai=x thenlocation:=i else if i=j thenlocation
11、:=0 elsesearch(i+1, j, x) Example 3Example 3 Express the linear search algorithm as a recursive procedure.把线性搜索算法表达成递归过程&递归递归 算法 引言 递归与迭代 归并排序37*递归与迭代递归：算法容易实现，不过效率低下；迭代：算法实现稍难，不过效率高.38* procedure iterative factorial (n: 正整数)x:=1 For i：= 1 to nx： I xx是n!&阶阶乘的迭代过过程39* procedure iterative fibonacci (n
12、: 非负整数) If n=0 then y:=0 Else Begin x:=0y:=1for i：= 1 to n-1 Begin z := x + yx := yy := z end Endy是第n个斐波那契数&斐波那契数的迭代算法40*&递归递归 算法 引言 递归与迭代 归并排序41* 基本思想 将两个或两个以上的有序子序列“归并”为一个有序序列。基本原理 为将一个具有n个待排序记录的序列看成是n个长度为1的有序列，然后 进行两两归并，得到n/2 个长度为2的有序序列，再进行两两归并， 得到n/4 个长度为4的有序序列，如此重复，直至得到一个长度为n的 有序序列为止。 在内部排序中，通常
13、采用的是2-路归并排序。即：将两个位置相邻 的有序子序列归并为一个有序序列。ri rm rm+1 rn有序有序有序ri rn&归归并排序42* 原理假设初始序列含有n个记录，则可看成n个有 序的子序列，每个子序列长度为1。然后两两归并，得 到n/2个长度为2或1的有序子序列；再两两归并， 如此重复，直至得到一个长度为n的有序序列为止 。初始时： 49 38 65 97 76 13 27&归归并排序原理43*初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 3
14、8 49 65 76 9744* 如何进行两路归并？将两个有序表的元素进行比较，小者复制到目标表中 。（5，24，35，74，222）（19，23，30）( )&两路归归并45*52435 74222()192330()ij()k51923243035 74222两路归并动画演示ikjkjkikjksm tm+146* 归并排序方法可以用递归的形式描述，即首先将待排序的记录序列分为左右两个部分，并分别将这两个部分用归并方法进行排序，然后调用2-路归并算法，再将这两个有序段合并成一个含有全部记录的有序段。&归归并排序的递归递归 算 法47*&归归并排序的递归递归 算 法48*Example 9E
15、xample 9对对对对8,2,4,6,9,7,10,1,5,38,2,4,6,9,7,10,1,5,3进进进进行行归归归归并排序并排序。49*分析分析 归并排序是这样进行的：反复地把表分成长度想归并排序是这样进行的：反复地把表分成长度想等的两个子表（或者其中一个子表比另一个子表多一个元素等的两个子表（或者其中一个子表比另一个子表多一个元素 ），直到每个子表包含一个元素为止。这些子表的序列可以），直到每个子表包含一个元素为止。这些子表的序列可以 表示成平衡二叉树。表示成平衡二叉树。然后继续进行下一过程：不断地合并成对的子表，其中的两然后继续进行下一过程：不断地合并成对的子表，其中的两 个表都是按升序排列的，把它们合并成元素都是按升序排列个表都是按升序排列的，把它们合
