程序设计基础第3章.ppt

1、算法的概念算法的概念3.13.2算法的特征算法的特征3.3算法的描述算法的描述算法设计中常用的算法设计中常用的基本方法基本方法3.43.5算法的设计要求算法的设计要求3.6算法的评价算法的评价 算法就是为解决一个特定问题而采取的方法和步骤。非数值运算算非数值运算算法法数值运算算数值运算算法法1212计算机算法的分类计算机算法的分类 一个算法必须具有以下特性：（1 1）有穷性）有穷性（2 2）确定性）确定性（5 5）可行性）可行性（4 4）有一个或）有一个或 多个输出多个输出（3 3）有零个或多个输入）有零个或多个输入3 3.3 3.1 1 用自然语言描述算法用自然语言描述算法 自然语言就是人们

2、日常生活中使用的语言，用自然语言来描述算法具有很明显的优点，那就是通俗易懂，便于阅读。缺点：自然语言固有的不严密性也会使得要简单清晰地描述算法变得很困难，并且易产生歧义。流程图是一种传统的算法表示法，它利用几何图形的框来代表各种不同性质的操作，用流程线来指示算法的执行方向。用流程图描述算法的方式比较直观形象，易于理解。3 3.3 3.2 2 用传统流程图描述算法用传统流程图描述算法 缺点：在设计比较复杂的算法时，画流程图是十分花费时间的，也容易在流程控制上出错。3 3.3 3.2 2 用传统流程图描述算法用传统流程图描述算法 流程图符号流程图符号3 3.3 3.3 3 用用 N-S 流程图描述

3、算法流程图描述算法 三种基本结构，及其 N-S 流程图的表示形式：顺序结构选择结构循环结构3 3.3 3.4 4 用伪代码描述算法用伪代码描述算法 伪代码是介于自然语言与编程语言之间的一种算法描述语言，使用伪代码来描述算法可以容易地以任何一种编程语言实现。优点：结构清晰、代码简单、书写方便、可读性好，既类似于自然语言，又便于向计算机语言算法（即程序）过渡。3 3.3 3.5 5 用计算机语言描述算法用计算机语言描述算法 用计算机语言来描述的算法，可以说是算法描述的终极形式。当然，用计算机语言表示算法必须严格遵循所采用的语言的语法规则。3 3.4 4.1 1 迭代法迭代法 迭代法也称辗转法，是一

4、种不断用变量的旧值递推新值的过程。迭代法又分为精确迭代和近似迭代两种。欧几里德算法属于精确迭代法，牛顿迭代法属于近似迭代法。用迭代算法解决一个具体问题时，需要考虑以下三个方面：迭代变量的确迭代变量的确立。立。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。迭代关系式的迭代关系式的建立。建立。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代过程的控制。迭代过程的控制。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

5、对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件3 3.4 4.1 1 迭代法迭代法 最经典的迭代算法是欧几里德算法，也叫辗转相除法，用于计算两个整数a，b的最大公约数（假定ab），其计算原理可表示为：gcd(a,b)=gcd(b,a mod b)，即（a,b)和（b,a mod b)的公约数是一样的。欧几里德算法就是一个反复迭代执行，直到余数为0才停止的算法，这实际是一个循环结构。1.1.欧几里德算法欧几里德算法 迭代法也是用于求方程或方程组近似根的一种常用的算法设计方法，牛顿迭代法就是其中的一种。设方程为 f(x)=0

6、，用某种数学方法导出等价的形式 x=g(x)。2.2.牛顿迭代法牛顿迭代法3 3.4 4.1 1 迭代法迭代法 使用牛顿迭代法求根时应注意以下两种可能发生的情况：方程虽然有解，但迭代公式选择不当或迭代的初始近似根选择不合理，也会导致迭代失败。2 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制。1 穷举法也叫列举法。其基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题

7、。这种方法的好处是最大限度考虑了各种情况,从而为求出最优解创造了条件。对于许多毫无规律的问题而言，穷举法用时间上的牺牲换来了解的全面性保证3 3.4 4.2 2 穷举法穷举法 递归是设计和描述算法的一种有力的工具，在用计算机解决某些复杂的问题时，使用递归是十分有效的。递归过程一般通过函数或子过程来实现，在函数或子过程的内部，直接或者间接地又调用到了自身，这种用递归来描述的算法称之为递归算法。3 3.4 4.3 3 递归法递归法 能采用递归描述的算法的特点：能采用递归描述的算法的特点：将求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小

8、的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为N）的求解推到比原问题简单一些的问题（规模小于N）的求解。3 3.4 4.3 3 递归法递归法 在使用递归的算法中，必须包含下面两个关键点：在使用递归的算法中，必须包含下面两个关键点：必须有一个明确的必须有一个明确的递归终止条件，即递归终止条件，即递归出口递归出口函数或过程的调用函数或过程的调用中包含它本身中包含它本身3 3.4 4.4 4 回溯法回溯法 回溯法也称为试探法，该方法放弃

9、关于问题规模大小的限制，并将问题的方案按某种顺序逐一枚举和试验。发现当前方案不可能有解时，就选择下一个方案，倘若当前方案不满足问题的要求时，继续扩大当前方案的规模，并继续试探。如果当前方案满足所有要求时，该方案就是问题的一个解。在回溯中，放弃当前方案，寻找下一个方案的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。运用回溯法解题的步骤：运用回溯法解题的步骤：（1 1）针对所给问题，定义问题的解空间）针对所给问题，定义问题的解空间3 3.4 4.4 4 回溯法回溯法 （2 2）确定易于搜索的解空间结构确定易于搜索的解空间结构（3 3）以深度优先的方式搜索解空间，并且在搜索以深度

10、优先的方式搜索解空间，并且在搜索 过程中用剪枝函数避免无效搜索过程中用剪枝函数避免无效搜索由于回溯法是对解空间的深度优先搜由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数索，因此在一般情况下可用递归函数来实现回溯法来实现回溯法3 3.4 4.5 5 分治法分治法 分治法，顾名思义，就是“分而治之”的意思。就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单直接求解，原问题的解即子问题的解的合并。1.1.分治法概述分治法概述 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分

11、治法的分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分割为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。3 3.4 4.5 5 分治法分治法 该问题的规模缩小到该问题的规模缩小到一定的程度就可以容一定的程度就可以容易地解决易地解决该问题可以该问题可以分割为若干个规模较分割为若干个规模较小的相同问题，即该问题小的相同问题，即该问题具有最优子结构性质具有最优子结构性质该问题可以分割为若干该问题可以分割为若干个规模较小的相同问题，个规模较小的相同问题，即该问题具有即该问题具有最

12、优子结构最优子结构性质性质利用该问利用该问题分割出的子问题题分割出的子问题的解可以合并为该问题的解可以合并为该问题的解的解分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：3 3.4 4.5 5 分治法分治法 分治法在每一层递归上都有分治法在每一层递归上都有3个步骤：个步骤：分割：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。求解：若子问题规模较小而且容易解决则直接解决，否则递归地解各个子问题。合并：将各个子问题的解合并为原问题的解。2313 3.4 4.5 5 分治法分治法 2.2.分治法在实际问题中的应用分治法在实际问题中的应用 二分查

13、找法就是分治法的一种简单形式，适用于在有序的线性表中查找某个数据元素的位置。利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素。二分查找法划分简单、均匀，是经常采用的一种有效方法。一个好的算法应便于理解，便于编码，便于修改等。从书写角度来说，结构上要直观、清晰、美观，在必要的地方要加上注释说明，另外算法的描述不要拘泥于一种形式，在算法的每个部分可以采用最便于理解的描述形式。2 2）可读性）可读性1 1）正确性）正确性（1）程序中的每一条语句都符合语法规定。（2）程序对于所有合法的输入数据都能产生满足要求的结果。效率指的是执行算法所花费的时间。对于解决同一问题的多个算法

14、，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。这两者决定着一个算法的运行效率，也就是按该算法编制的程序在计算机上执行所花费时间和所占用空间。4 4）高效率与）高效率与低储存量需求低储存量需求3 3）健壮性）健壮性所谓健壮性，主要指一个算法除了能对合法的输入数据得到正确的结果外，还应对非法的或不合乎要求的输入数据做出正确合理的处理。3 3.6 6.1 1 时间复杂度时间复杂度 时间复杂度描述了一个算法在计算机上执行时占用计算机时间资源的情况。使用绝对的时间单位衡量算法的效率是不合适的。可以认为一个特定算法“运行时间”的大小，只依赖于问题的规模（通常用整数n表示），它是

15、问题规模的某个函数，记为T(n)，反映在算法中就是算法中语句的执行次数。一个算法中的语句执行次数称为语句频度。当n不断变化时，语句频度T(n)也会不断变化。若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。采用“大O表示法”记作T(n)=O(f(n)，称O(f(n)为算法的渐进时间复杂度，简称时间复杂度。3 3.6 6.1 1 时间复杂度时间复杂度 随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率降低。常见的时间复杂度，按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）

16、、线性对数阶O（nlog2n）平方阶O（n 2）、立方阶O（n 3）、k次方阶O（n k）、指数阶O（2 n）3 3.6 6.2 2 空间复杂度空间复杂度 一个算法的空间复杂度S(n)定义为算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数。记作：S(n)=O(f(n)空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面.对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间3 3.6 6.2 2 空间复杂度空间复杂度