算法设计与分析2第一部分.pptVIP

算法设计与分析 主要内容 　　 算法的概念 算法问题求解基础 重要的问题类型 重点难点 重点：算法含义的理解、重要的问题类型 难点：算法的含义 第一节 算法的概念 1、算法含义的理解 计算机科学中，算法已逐渐成了用计算机解一类问题的精确、有效方法的代名词，我们可以将它视为问题的解决方案，获得问题答案的精确指令，但不是问题的答案，在计算机领域还没有给出一个对算法精确的定义，我们可以有如下几种理解： 算法就是解决问题的方法。 算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。 算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。 在本书中也给出了对算法含义的理解：算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。 所谓的指令即人们发出的命令或计算机能够识别并执行的指令，它是把上述理解中的规则细化为了指令。在有合法输入的前提下，计算机可以根据该指令进行一系列操作，在一定的时间内完成对数据的处理，并将处理的结果输出。可以用图1.1表示： 2、算法的重要特性 （1）确定性 算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须相当清楚、无二义性。 （2）能行性 算法中有待实现的运算都是相当基本的，每种运算在原理上能在有限时间内完成。 （3）输入 这些算法有0个或多个输入，这些输入是在算法开始之前给出的量，它取自特定的对象集合。 （4）输出 没有输出的算法是无效的算法，因此算法要有一个或多个输出，这些输出是同输入有某种特定关系的量。 （5）有穷性 一个算法总是在执行了有穷步运算后终止。 3.算法举例 采用三种不同的方法求两个不全为0的非负整数m和n的最大公约数。 设gcd(m,n)为最大公约数 解1：欧几里得算法 利用递归公式：gcd(m,n)=gcd(n,m mod n) 可得m最后的取值就是m和n的最大公约数。 因为由gcd(m,n)=gcd(n,m mod n)公式可知：m的值逐渐变小，n的值也逐渐变小，且不断向0靠近，m mod n的值也不会小于0，又有gcd(m,0)=m，所以m最后的取值就是m和n的最大公约数。 如gcd(60,24)=gcd(24,12)=gcd(12,0)=12 算法语言描述： S1：如果n=0，返回m的值作为结果，同时过程结束；否则，进入S2； S2：用m对n求模运算，将余数赋给r； S3：将n的值赋给m，将r的值赋给n，返回S1。 算法伪代码描述： Euclid(m,n) While n0 do M mod n-r n-m r-n return m 解2：用于计算gcd(m,n)的连续整数检测算法 这样理解：两个全不为0的非负整数m和n的最大公约数就是能够同时整除它们的最大正整数。（注意前提是两个全不为0的非负整数m和n，若有一个为0，则结果错误。） 经分析可知，两个数的最大公约数不会大于两个数中的任何一个数，我们可以从两个数中的较小者找起。设t=min{m,n}若t能整除m和n，t就是最大公约数，否则，将t减1，继续尝试。 算法语言描述 S1：min(m,n)-t； S2：m除以t，如果余数为0，进入S3，否则进入S4； S3：n除以t，如果余数为0，返回t的值作为结果；否则进入S4； S4：t-1-t，返回S2。 算法伪代码描述 min(m,n)-t While 1 do If m mod t=0 then If n mod t=0 then return t Else t-1-t Else t-1-t 解3：中学里计算gcd(m,n)的过程 方法描述 S1：找到m的所有质因数； S2：找到n的所有质因数； S3：找出S1与S2中的公因数，（如果P是一个公因数，而且在m和n的质因数分解式分别出现Pm和Pn次，那么应该将P重复min{Pm,Pn}次）； S4：将S3中的公因数相乘，其结果作为给定数字的最大公约数。 如：60=2*2*3*5 24=2*2*2*3 Gcd(60,24)=2*2*3 为什么称此做法为方法，而不是算法，我们知道，算法的一个很重要的特性是确定性，即每一步要做的事情都是确定的，不存在二义性，而该法中的S1与S2中要求质因数，那么1是否可以作为质因数，存在争论。此外，由于S1与S2的不确定性，导致了S3中的定义也