离散数学课件-第2章-2.ppt

1,2019/11/1,离散数学 Discrete Mathematics,汪荣贵 教授 合肥工业大学软件学院专用课件 2010.3,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 矩阵,学习内容,算法的复杂性,函数的增长 算法的时间复杂度 算法的复杂度分析,函数的增长,对数据的描述：数据结构(data structure) 对操作的描述：算法(algorithm),著名计算机科学家沃思提出一个公式: 数据结构 + 算法 = 程序,数据结构算法程序设计方法语言工具,完整的程序设计应该是:,算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次,同一个问题，可有不同的解题方法和步骤,例： 求,例: 求 12345,步骤1：先求12，得到结果2 步骤2：将步骤1得到的乘积2再乘以3，得到结果6 步骤3：将6再乘以4，得24 步骤4：将24再乘以5，得120,太繁琐,如果要求121000，则要写999个步骤,算法的概念,S1：使p=1 S2：使i=2 S3：使pi，乘积仍放在变量p中，可表示为：p=pi S4：使i的值加1，即i=i+1。 S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。,可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果, 算法可改写：,S1：p=1 S2：i=3 S3：p=pi S4：i=i+2 S5：若i999，返回S3。否则，结束。,如果题目改为：求135999算法只需作很少的改动：,算法简练,例 有50个学生，要求将他们之中成绩在80分以上者打印出来。 设gi代表第i个学生成绩，算法表示如下:,S1：i=1 S2：如果gi 80，则打印和，否则不打印。 S3：i=i+1 S4：如果i50，返回S2，继续执行。否则算法结束,变量i作为下标，用来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。,例 判定20002500年中的每一年是否闰年，将结果输出。,分析：闰年的条件是： (1)能被4整除，但不能被100整除的年份都是闰年，如1996,2004年是闰年； (2)能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。 不符合这两个条件的年份不是闰年。,设y为被检测的年份，算法可表示如下 ： S1：y=2000 S2：若y不能被4整除，则输出y “不是闰年”。然后转到S6。 S3：若y能被4整除，不能被100整除，则输出y “是闰年”。然后转到S6。 S4：若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是闰年”。 然后转到S6。 S5: 输出y “不是闰年”。 S6：y=y+1 S7：当y2500时，转S2继续执行，如y2500，算法停止。,以上算法中,每做一步都分别分离出一些范围(巳能判定为闰年或非闰年)，逐步缩小范围，直至执行S5时，只可能是非闰年。 “其它” 包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1990) 是非闰年。,计算机算法可分为两大类别： 数值运算算法：求数值解，例如求方程的根、求函数的定积分等。 非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。,2.1 算法,算法的基本类别,算法的基本特征,输入 算法从一个指定的集合得到输入值 输出 对每个输入值集合，算法都要从一个指定的集合中产生输出值。输出值就是问题的解 确定性 算法的步骤必须是准确定义的 正确性 对每一组输入值算法都应产生正确的输出值,算法的基本特征,有限性 对集合中的任何输入，算法都应在有限（可能很多）步之后产生所求的输出. 有效性 算法的每一步必须能够准确地执行，并在有限时间内完成. 通用性 算法过程应适用于要求行事的所有问题，而不只是用于一组特定的输入值.,正确性(correctness) 可读性(readability) 健壮性(robustness) 计算复杂度(Complexity),算法的评价标准,算法的表示,自然语言 传统流程图 结构化流程图 伪代码 PAD图,算 法,算法的基本概念 搜索算法 递归算法,搜索问题描述如下： 在不同元素a1，a2，,an的表中，为元素x定位，或者判定它在不在该表中。问题的解是表中等于x的项的位置，当x不在表中时，问题的解为0. 搜索问题也叫查找问题。,搜索问题,从如下几个方面评价查找算法的性能 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：需要和给定值进行比较的字符个数的期望值叫查找算法的。,查找算法评价,线性搜索算法（顺序搜索算法） 从比较x和a1开始，若x=a1，那么解就是a1的 位置，当xa1， 比较x和a2，若x=a2，解就是a2的位置，当xa2，比较x与a3， 继续这一过程，逐一比较x和表中每一项，直到出现相等，解就是该项的位置，除非不存在相等。,2.1 算法,线性查找算法,查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1,线性查找的ASL,对分搜索算法： 适用于各项增序 把要搜索的元素与表的中间项比较，然后表分成两个字表，根据与中间线的比较结果，搜索将限于两个字表的一个中进行 对分搜索效率高于线性搜索,对分查找算法,算法描述,其它查找算法,分块查找算法(略) 哈希查找算法(略),算 法,算法的基本概念 搜索算法 递归算法,若一个对象部分地包含它自己, 或用它自己给自己定义 ，则称为是递归的（Recursion）。 递归不仅是数学上的一种重要表达方法，也是计算机科学中的一个基本概念。,递归算法,能采用递归描述的算法通常有这样的特征： 为求解规模为N的问题，设法将它分解成规模较小的问题; 然后从这些小问题的解方便地构造出大问题的解; 并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 递归的能力在于用有限的语句来定义对象的无限集合。,自然数阶乘n!可以采用递归方法计算出来的。 令f (n) = n!，则f(n)可以表示为： f (0) = 1 f (n) = nf (n1) n0,Example,现在已知n!=n*(N-1)*(n-2)*(n-3)*2*1 首先可知当n=1时 n!=1 第二步可设当R(n)=n!，R(n+1)=(n+1)! 第三步，求R(n+1)与R(n)之间的关系。R(n)=n!， 而R(n+1)=(n+1)!=(n+1)*(n)*(n-1)*2*1=(n+1)*n!=(n+1)*R(n) 即：R(n+1)=(n+1)*R(n) = R(n)=n*R(n-1),算法代码 factorial (int N) if (N = 1) return 1; return N * factorial (N - 1) /* 递归部分 */ ,菲波那契数， F(0) = 1，F(1) = 1 F(n) = F (n1) + F (n2) n1 由上述公式，我们得到： F (2) = 2，F (3) = 3，F (4) = 5， F (5) = 8，F (6) = 13， 利用菲波那契数可以推算出兔子繁衍规律。,Example,写成递归函数有： int fib(int n) if (n=0) return 0; if (n=1) return 1; if (n1) return fib(n-1)+fib(n-2); ,Some other Algorithms,Optimization problem: The goal of such problems is to find a solution to the given problem that either minimizes or maximizes the value of some parameter. （优化问题：这种问题的目标是求给定问题把某个参数值最小化或最大化的解） Algorithms that make what seems