算法与数据结构：第1章 算法与程序

《算法与数据结构：第1章 算法与程序》由会员分享，可在线阅读，更多相关《算法与数据结构：第1章 算法与程序（100页珍藏版）》请在金锄头文库上搜索。

1、算法与数据结构算法与数据结构第1章 算法与程序 第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序1.1 算法的基本概念1.1.1 什么是算法1.1.2 算法的基本特性什么是算法 早在公元前300年左右出现的著名的欧几里德算法，就描述了求解两个整数的最大公因子的解题步骤。要求解的问题描述为：“给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大整数”。欧几里德当时给出的算法如下： 以n除m，并令所得余数为r（必有rn）； 若r=0，输出结果n，算法结束；否则继续步骤； 令m=n和n=r，返回步骤继续进行。 什么是算法（续）定义：

2、算法就是求解问题的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序的规则；每一个规则都是有效的，且是明确的；按此顺序将在有限次数下终止。 什么是算法（续）最为著名的定义是计算机科学家D.E.Kunth在其巨著计算机程序的艺术（ Art of Computer Program）第一卷中所做的有关描述。其非形式化的定义是： 一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题的运算序列。 什么是算法（续）算法的形式化定义如下所述：算法是一个四元组，即（Q，I，F）。其中：n Q是一个包含子集I和的集合，它表示计计算的状态算的状态；n I表示计算的输入集合输入集合；n 表示

3、计算的输出集合输出集合；n F表示计计算算的的规规则则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q Q，有F(q)=q。什么是算法（续）n一个算法是对于任何的输入元素x，都在有穷步骤内终止的一个计算方法。n在算法的形式化定义中，对任何一个元素xI，x均满足性质 x0=x，xk+1=F(xk)，（k0） 该性质表示任何一个输入元素x均为一个计算序列，即x0，x1，x2，xk；该序列在第k步结束计算。 1.1 算法的基本概念1.1.1 什么是算法1.1.2 算法的基本特性算法的基本特性n输入（Input）n输出（Output）n确定性（Definiteness）n有穷性（Finite

4、ness）n有效性（Effectiveness）第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 自然语言表示 自然语言即人们日常使用的语言，如汉语、英语、日语、法语、德语等等。使用自然语言描述算法，人们比较容易接受和理解。如前面的欧几里德算法就是用自然语言描述的。然而，自然语言也具有许多缺点，在使用自然语言描述算法时一定要引起注意：n自然语言存在着歧义性，容易导致算法的不确定性；n自然语言容易冗长，使得描

5、述不够简洁；n自然语言的表示形式是顺序的，描述分支选择和转移时不够直观；n自然语言与计算机程序设计语言的差别较大，不易转换为程序。 1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 流程图表示 流程图是描述算法的图形工具，它采用如下所示的一组图形符号来表示算法： 起止框，表示算法的开始或结束；只有一个入口或一个出口。输入输出框，表示算法中数据信息的输入和输出；有一个入口和一个出口。判断框，表示条件判断；有一个入口和多个出口。处理框，表示算法中的一个（或一组）运算或处理；有一个入口和一个出口。流程线，表示算法

6、中各步骤之间的次序关系。连接点，表示算法中的连接位置，主要用于同一算法在不同页描述时的接续等情况。注释框，用于对算法中某些操作的注释说明。 流程图表示举例欧几里德算法的流程图描述如图1-1所示 图1-1欧几里德算法的流程图表示noyesmmodnrend读入m,nr=0beginNm,rn输出nm,n为正整数，算法求其最大公因子流程图表示（续）同自然语言相比，用流程图描述算法直观，可以一目了然；算法步骤间用流程线连接，次序关系清楚，容易理解；可以很方便地表示顺序、选择和循环结构，不依赖于任何计算机和计算机程序设计语言，有利于不同环境下的程序设计。流程图表示（续）但是，流程图也还存在一些缺点，诸

7、如： n不易于表示算法的层次结构；n不易于表示数据结构和模块调用关系等重要信息；n容易使人过早地考虑算法的控制流程，而忽视算法的全局结构；n用流程线代表控制流，控制转移随意性较大。若对流程线的使用不加限制，随着求解问题规模和复杂度的增加，流程图会变得很复杂，使人难以阅读、理解和修改，从而使算法的可靠性难以保证。1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 NS图表示（续） N-S图的基本图形符号如下： ABTFPAB当PAA直到P顺序结构，由两个或多个矩形框组成。其中A和B可以是基本操作，也可以是其它基

8、本结构（如选择结构，循环结构）。选择结构，当条件P成立时执行操作A，否则执行操作B。当型循环结构。当条件P成立时反复执行操作A，直到条件P不成立时止。直到型循环结构。反复执行操作A，直到条件P成立时止。 NS图表示n它独立于任何计算机和计算机语言，又能很方便地转换为计算机语言程序；n它去掉了流程线全部用矩形方框来描述，限制了算法流程转移控制的随意性，又节省了篇幅；n它很容易表示算法中的嵌套关系和模块中的层次关系，功能域可以从框图中直接反映出来；n它仍是图形工具，阅读起来直观、明确、容易理解。 NS图表示举例 由于N-S图象一个多层的盒子，所以也称作盒图。用N-S图表示欧几里德算法如图1-2所示

9、。 读入正整数m,n读入正整数m,nm mod nrmr当r0反复做nm, rnnm, rnm mod nrm mod nr直到r=0时止输出最大公因子n输出最大公因子n(a)当型循环结构实现(b)直到型循环结构实现图1-2 欧几里德算法的N-S图表示1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 伪代码表示（续）下面，我们给出欧几里德算法的一种伪代码描述如下： Begin(算法开始) Read(m,n) m mod nr while r0 do nm rn m mod nr write(n) End(算

10、法结束)伪代码表示n伪代码是介乎于自然语言和计算机程序语言之间的一种表示算法的工具。n 它用文字和符号描述问题的求解方法和步骤而不使用图形符号。n 如同一篇文章自上而下书写，每行写一个基本操作，而用若干行写出一个基本结构。n 因而书写方便，格式紧凑，清晰易读好理解，也更容易转化为某一计算机程序语言表示的程序。n 和图形工具相比较，便于修改，但直观性能较弱。 1.2 算法的表示1.2.1 自然语言表示1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示1.2.5 程序语言表示 程序语言表示（续）作为例子，下面我们给出欧几里德算法的C语言描述如下： #include ”stdio

11、.h” main() int m,n,r; printf(“请输入两个正整数：”)； scanf(“%d%d”,&m,&n); printf(“n%d和%d的最大公约数是：”，m,n); r=m%n; while(r!=0) m=n; n=r; r=m%n; printf(“%dn”,n); 运行结果：请输入两个正整数：56 3256和32的最大公约数是：8 程序语言表示（续）n和自然语言一样，计算机程序设计语言也是串行的描述，很不直观。n对于较复杂的问题，人们很难用计算机程序设计语言直接写出程序。n所以在算法设计阶段，一般是先采用某个专用的辅助工具来描述算法，在算法设计好之后，再把它转化为某

12、一具体程序设计语言描述的程序。 第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序1.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法评价算法的标准n评价一个算法优劣的五条标准：n正确性n可读性n健壮性n高效性n简洁性n一个好的算法是满足这五条标准要求的算法。 评价算法的“正确性”标准n所设计出来的算法要能够正确求解给定的问题。n这就要求算法中的每一个步骤的描述是准确无歧义的，并且是可以执行的；n要求算法能够满足问题要求，并在有限步骤内获得结果；n否则就不具备正

13、确性要求，更谈不上解决给定的实际问题了。n算法要能经得起一切可能的输入数据的考验。评价算法的“正确性”标准（续）n在将算法用程序语言表示为特定语言的程序后还必须注意：n程序中不含有语法错误；n对于一切合法的输入数据，程序能够产生满足要求的输出结果；n对于一切非法的输入数据，程序能够得出满足规格说明的结果；n对于精心选择的，甚至是带有刁难性的典型测试数据，程序都有满足要求的输出结果。评价算法的“可读性”标准n表示出来的算法要能够方便地供人们阅读、理解和交流。n算法的可读性好是保证正确性的前提，良好的可读性有利于人们理解算法思想，减少出错机会，便于检查和修改。n可适当地增加注释，增强算法或程序的可

14、读性。 评价算法的“健壮性”标准n算法对意外情况的反映能力要强。n当输入数据非法、0作除数、负数开平方等，算法应能做出相应的处理，给出错误信息或终止算法执行，避免产生错误的或莫明其妙的输出结果。 评价算法的“高效性”标准n算法的执行效率要高。n算法的效率可分为时间效率和空间效率。n 时间效率是通过该算法转化的程序在计算机上运行的时间耗费来确定，在算法设计与分析阶段用执行基本操作的次数（是问题规模的函数）相对于问题规模的渐近阶来表示。n 空间效率主要考虑除存储数据结构之外的辅助存储空间。n一个高效算法是指执行算法耗费时间少，使用辅助存储空间小的算法。 评价算法的“简洁性 ”标准n所设计出来的算法

15、要尽可能地简洁。n对于同一问题所设计的不同算法，越简洁明了的越好。n越简洁的算法可读性越好，越易于理解、编码和调试、测试，越受人们欢迎。 评价算法的标准（续）n在评价一个算法时，要对这五个方面综合考虑，不要片面追求某一指标。n有些指标之间往往是相互制约的，如时间效率与空间效率，简洁性与高效性等等；n要学会针对具体问题要求和软硬件实现环境进行综合平衡，设计出满足需要的好算法。1.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法算法的环路复杂度n算法的复杂性很大程度上取决于控制流程的复杂性。n单一的顺序结构最简单；n

16、循环结构和选择结构所构成的环路越多算法就越复杂。n基于这一种观点，针对算法的流程图表示，我们先介绍算法的环路复杂度的概念和度量方法。 算法的环路复杂度（续）n算法（或程序）的环路复杂度度量方法，以图论为工具，先画出程序图，然后用该程序图的环路作为算法（或程序）复杂性的度量值。算法的环路复杂度举例n例如图1-1所示的欧几里德算法的流程图所对应的程序图如图1-3所示。 图1-3欧几里德算法流程图的程序图图1-1欧几里德算法的流程图表示noyesmmodnrend读入m,nr=0beginNm,rn输出n （1）观察法 程序图中封闭区域的数量对应于环路的复杂性如图1-3所示，图中有2个明显封闭区域，

17、因此环复杂度为2。 图1-3欧几里德算法流程图的程序图 （2）公式法 计算公式：V(G)=e-n+1其中，e表示图中边的数目，n表示节点总数。如图1-3所示，图中V(G)=8条边7结点+1，则环路复杂度为2。图1-3欧几里德算法流程图的程序图（ 3）判定节点法 利用代码中独立判定节点的数目来计算环路复杂度。 计算公式：V(G)=P+1 其中，P表示所有判定结点处所需要的判定的总个数。如图1-3所示，图中V(G)=1个判定1，则环路复杂度为2。 图1-3欧几里德算法流程图的程序图环路复杂度的计算方法举例图1-4程序图的复杂度n例2：如图1-4所示的程序图中， 有11条弧和7个结点，由该公式 可如

18、下确定其环路复杂度： V(G)=11-7+1=51.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法算法的时空效率n环路复杂度是一种定量地评价算法复杂度的方法。n下面我们再介绍一种适应面更广泛的定性评价算法复杂度的方法，即大O方法。 N-S图伪代码流程图程序图算法的时空效率（续）n执行一个算法的时间代价，是指将该算法转化为程序后在计算机上运行的时间耗费n即算法中每条语句在计算机上执行的时间总和：n计算机执行一种基本操作（如赋值运算、比较运算、移动操作等）所需的时间与算法中进行基本操作总次数的乘积。算法的时空效率（

19、续）n而每条语句的执行时间则应该是执行该语句一次所需的时间与该语句执行的次数（也称之为频度）的乘积。n因此，对算法执行时间的讨论就可以转化为对算法中所有语句的执行次数（即频度）的讨论。 大O方法计算举例n两个n*n矩阵相乘的算法描述如下： for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /* n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k=n;k+) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ 大O方法计算举例（续）n其中，每一条语句的频度说明在注释中。我们把算法所耗费的时间定义为该算法中

20、每条语句的频度之和，则该算法的时间耗费T(n)可表示为T(n)=2n3+3n2+2n+1n显然，它是矩阵的阶（该问题的规模）n的函数。并且当n时，T(n)/n32。这表示当n趋于无穷大时，T(n)与n3是同阶函数或者说是同量级的。引入大O记号可记作T(n)=O(n3) 时间复杂度n引入大O记号表示的算法的时间耗费T(n)通常称之为算法的时间复杂度，如矩阵相乘算法的时间复杂度为O(n3)。n这种时间复杂度的大O表示法，实质上是把算法的基本操作总数表示为问题规模n的函数之后，寻找出当问题规模n趋于无穷大时该函数的同阶最简形式即渐近性态下的同阶最简函数，有时也简称之为渐近阶。n问题的规模是指算法中要

21、处理的数据量的规模，通常用一个整型量n来表示。对于求解不同的问题，规模n具有不同的值。 时间复杂度（续）n时间复杂性的渐近阶表示，是对算法时间性能优劣的宏观定性评价。n例如，为了求解同一问题所设计的两个不同的算法A1和A2，其时间耗费分别为T1(n)=40n2和T2(n)=5n3；显然当问题规模nT2(n)，算法A2比A1时间花费少；利用渐近阶表示的时间复杂度O(n2)和O(n3)反映了对这两个算法时间性能优劣的宏观定性评价结论。n由于是宏观的定性评价，算法中频度最大的语句的频度，与算法中每条语句频度的和T(n)是同阶函数；n所以人们在计算算法时间复杂度时，往往只需考虑算法中频度最大的语句的频

22、度就可以了。时间复杂度计算举例n例如对于下面的程序段：x=0;for(i=1;in;i+)for(j=1;ji;j+)for(k=1;kj;k+)x+;n我们只须关心程序段中执行频度最大的语句最内层循环的循环体语句x+，它的执行次数是n由于n3是它的渐近性态下的同阶最简函数，可得上述程序段的时间复杂度为T(n)=O(n3)。简明实用的程序分析法则 n执行一条基本操作如读写或赋值语句等，需要O(1)的时间花费。n对于顺序结构，需要执行一系列语句，所用时间用求和准则估计。n对于选择结构如if语句，主要时间耗费是执行then子句或else子句所用的时间；此外，检验条件还需用O(1)的时间。多选择结构

23、的时间耗费与if语句类同。n对于循环结构，执行时间为多次迭代中循环体的执行和检验循环条件的耗时，常用乘法准则估计。n对于复杂算法，可以将它分成几个容易估算的部分分别估计，然后利用求和准则和乘法准则计算整个算法的时间复杂度。简明实用的程序分析法则（续）n大O下的求和准则n若T1(m)=O(f(m)，T2(n)=O(g(n)（不相同问题规模时） 则T1(m)+T2(n)=O(f(m)+g(n)n若T1(n)=O(f(n)，T2(n)=O(g(n)（相同问题规模时）则T1(n)+T2(n)=O(max(f(n),g(n)n 若g(n)=O(f(n)（特殊运算规则）则O(f(n)+O(g(n)=O(f

24、(n)简明实用的程序分析法则（续）n大O下的乘法准则n若T1(m)=O(f(m)，T2(n)=O(g(n) （不相同问题规模时）则T1(m)*T2(n)=O(f(m)*g(n)n 若T1(n)=O(f(n)，T2(n)=O(g(n)（相同问题规模时）则T1(n)*T2(n)=O(f(n)*g(n)n 若c是一个正常数（特殊运算规则） 则O(cf(n)=O(f(n)程序分析法则举例n如对前述的矩阵相乘算法，它是三层嵌套的循环结构，我们可以从最内层循环的循环体开始分析：n两个n*n矩阵相乘的算法描述如下： for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /*

25、n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k=n;k+) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ n是赋值语句，与问题规模无关，时间复杂度为常数阶O(1)，即T5(n)=O(1)；n对于第条语句，T4(n)=O(n)，它与第条语句是 循 环 关 系 应 该 用 乘 法 准 则 ， 即T4(n)*T5(n)=O(1*n)=O(n)；程序分析法则举例n对于第条语句T3(n)=O(1)，它与第、是顺序结构应该用求和准则，即T3(n)+T4(n)*T5(n)=O(max(1,n)=O(n)；n第条语句其T2(n)=O(n)，到是

26、它的循环体适用乘法准则，故有T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n)=O(n2)；n两个n*n矩阵相乘的算法描述如下： for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /* n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k=n;k+) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ 程序分析法则举例n第条语句的耗时T1(n)=O(n)，到是它的循环体适用乘法 准 则 ， 所 以 有 T1(n)*(T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n2)=O(n3)。

27、n两个n*n矩阵相乘的算法描述如下： for(i=1;i=n;i+) /* n+1次 */ for(j=1;j=n;j+) /* n(n+1)次 */ cij=0; /* n2次 */ for(k=1;k=n;k+) /* n2(n+1)次 */ cij=cij+aik*bkj; /* n3次 */ 时间复杂度（续）n实际上，算法或程序的执行时间不仅依赖于所求解问题的规模，还与它所处理的数据的状态有关。n一般在不做任何说明的情况下，讨论其时间复杂度是指在最坏情况下的时间复杂度，通常可记作Tmax(n)；有时还要讨论其平均情况下的时间复杂度Tavg(n)。 空间复杂度n衡量一个算法优劣的另一个因

28、素是空间代价，即执行由算法转化的程序时所占用存储空间的大小。为了执行算法所占用的存储空间包括如下三个方面：n 为了在计算机上存储程序本身所占用的存储空间。n 算法或程序中的输入和输出数据所占用的存储空间。n 算法或程序在执行过程中临时占用的存储空间。空间复杂度n度量一个算法或程序在执行过程中所花费的额外存储开销（即临时存储工作单元）的大小也是用大O方法，度量的结果称之为算法的空间复杂度。空间复杂度和时间复杂度一样，也是用相对于问题规模函数的渐近阶形式给出，如O(1)、O(n)等。 时（空）间复杂度n常见的时间（或空间）复杂度有：n常数阶O(1)n对数阶O(log2n)n线性阶O(n)n线性对数

29、阶O(nlog2n)n平方阶O(n2)n立方阶O(n3)n指数阶O(2n)n指数阶的算法效率极低，当问题规模n稍大时就无法使用。1.3 算法的设计与评价1.3.1 评价算法的标准1.3.2 算法的环路复杂度1.3.3 算法的时空效率1.3.4 常见的算法设计方法常见的算法设计方法n常用的算法设计方法和技术： n穷举法n迭代法n递推法n递归法n回溯法n贪婪法n分治法1.穷举法n穷举法亦称作枚举法。它的基本思想是：n首先根据求解问题的部分条件确定答案的大致范围，即列举出解的所有可能的情况；n然后在此范围内对所有可能的情况逐一验证，若某个情况经过验证符合问题条件则为一个解，若全部情况验证后均不符合题

30、目条件则问题无解，从而得出求解问题的完整解。1.穷举法n穷举法亦称作枚举法。n例如要找出200到500之间的所有素数，我们只要对这个范围内的每一个数逐个用素数的定义去判断就行了。n穷举法的特点是算法简单，但有时运算量大效率较低。在可以确定解的取值范围，但一时又找不到更好的算法时，就可以使用穷举法求解。 2.迭代法n迭代法的基本思想是，由一个量的原值求出它的新值，不断地再用新值替代原值求出它的下一个新值，直到得到满意的解。新值与原值之间存在一定的关系，这种关系可以用一个公式来表示，称之为迭代公式。2.迭代法n迭代法主要用于那些很难用或无法用解析法求解的一类计算问题，如高次方程和超越方程等；使得复

31、杂问题的求解过程，转化为相对较简单的迭代算式的重复执行过程，用数值方法求出问题的近似解。迭代法（续）n使用迭代法构造这一类问题求解算法的基本方法是：n先确定一个收敛性能好（即收敛速度快）的迭代公式，选取解的一个近似值（即迭代初值）和解的精度要求（即允许的最大误差范围），n然后用循环处理实现迭代过程，终止循环的条件是前后两次得到的近似值之差的绝对值小于解的精度要求，并认为最后一次得到的近似解为问题的解。n这种迭代方法称作逼近迭代，如著名的牛顿迭代法就是这种逼近迭代方法。n此外，精确值的计算也可以使用迭代法。例如计算s=1+2+3+1000，可选取迭代公式s+is和迭代初值0（即0s）。3.递推法

32、n递推法是从前面的一些量推出后面的一些量的一种方法，它从已知的初始条件出发，逐次推出所需要求解的各中间结果和最终结果。n递推过程往往表现为迭代，即由一些量的原值推出它的新值，不断地用新值替代原值推出下一个新值，直到推出最终结果，新值与原值之间的关系用递推公式表示。n例如Fibonacci数列存在着递推关系 F(1)=1，F(2)=1，F(n)= F(n-1)+ F(n-2) (n2)递推法（续）n需要求出Fibonacci数列中某一项的值，利用递推公式逐步求出F(3)，F(4)直到求出该项的值，也许有人会说，如果使用通项公式计算岂不更方便吗？事实上，有些递推问题的通项公式是很难找出的，即使找出

33、通项公式计算也不一定简便。如Fibonacci数列的通项公式为 n显而易见，找出这个通项公式不易，利用它计算F(n)也相当费力。相反地，若利用递推初值和递推公式计算F(n)就容易和方便多了。 4.递归法 n如果一个过程直接或间接地调用它自身，则称该过程是递归的；直接调用自身称作直接递归，间接调用自身则称作间接递归。n递归是构造算法的一种基本方法，它将一个复杂问题归结为若干个较为简单的问题，然后将这些较为简单的问题进一步归结为更简单的问题，这个过程一直进行下去直到归结为最简单的问题时为止。这个最简单的问题即为递归终止条件，也称作递归出口。递归法和递推法比较 n递归和递推是既有区别又有联系的两个概

34、念。n递推是从已知初始条件出发逐次推出最后所求的值；n递归则是从函数本身出发，逐次上溯调用其本身求解过程直到递归出口，然后再从里向外倒推回来得到最终的值。n一般地说，一个递推算法总可以转换为一个递归算法。对于同一问题所设计的递归算法往往要比相应的非递归算法（如递推算法）付出更多的执行时间代价和更多的辅助存储空间开销。递归法和递推法比较（续） n然而，利用递归方法分析和设计算法可使难度大幅度降低，且程序设计语言中一般都提供递归机制；利用递归过程描述问题求解算法不仅非常自然，而且算法的正确性证明要比相应的非递归算法容易得多；另外有成熟的方法和技术，可以很方便地把递归算法改写为非递归算法。n所以，递

35、归技术是算法设计的基本技术，递归方法是降低分析设计难度提高设计效率的重要手段和工具。 5.回溯法n回溯法是算法设计中的一种基本策略，它通过对问题的分析找出一个解决问题的线索，然后沿这个线索逐步试探。n对于每一步试探，若成功就继续下一步试探；若不成功就逐步退回换别的路线再进行试探，直至探索成功得到问题的解或试探完所有的线索问题无解。n在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，许多都可以用回溯法来求解。n例如，在国际象棋棋盘上的骑士周游问题和我们平时参加的走迷宫游戏，都是使用回溯法进行的。 6.贪婪法n贪婪法也称作贪心算法，它是通过一系列的选择来得到问题的一个解。n贪婪法在

36、每一步所做出的选择，都总是在当前状态下看来是最好的选择即贪婪选择，并希望通过每次所作的贪婪选择导致最终结果是求解问题的一个最优解。n换句话说，贪婪法并不从整体最优上加以考虑，它做出的选择只是在某种意义上的局部最优选择，但希望算法得到的最终结果也是整体最优的。虽然这种贪婪策略不能对所有问题都得到整体最优解，然而在许多情况下的确能够产生整体最优解。n在一些情况下，即使贪婪算法不能得到整体最优解，其最终结果却是最优解的很好近似。7.分治法n求解一个复杂问题时，尽可能地把这个问题分解为若干较小的子问题，在找出各个较小问题的解之后再组合成为整个问题的解，这就是所谓的分治法。n使用分治法时，往往要按问题的

37、输入规模来衡量问题的大小；当要求解问题的输入规模相当大时，应选择适当策略将输入划分成若干子集合得到一组子问题，在求出各子问题的解之后用适当的方法把它们合并成整个问题的解，分治法便应用成功了。n如果得到的子问题还相对过大，可再次使用分治法将这些子问题进一步划分成更小的子问题。第1章 算法与程序1.1 算法的基本概念 1.2 算法的表示1.3 算法的设计与评价1.4 算法与程序算法与程序n算法与程序是密切相关的两个概念。n研究和讨论算法是为了设计出更好的程序，设计好的算法都要转化为某种语言描述的程序才能在计算机上运行；n或者说程序是算法表示的最终形态，程序只有装入计算机中运行（即程序的执行）时才能

38、够起到对实际问题求解的作用。 1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述程序的基本概念n在低级语言中，程序表现为一组指令和有关数据；n在高级语言中，程序表现为一组说明和语句。n程序既是软件的固有部分，又是软件研究的对象，程序的质量决定着软件的质量。n衡量一个程序的质量，除了对程序结构进行静态考察外，还必须考察其执行过程。n与执行无关的特性称之为程序的静态特性，n与执行有关的特性称之为程序的动态特性。 程序的特征n程序描述解决某一问题的特定任务与功能，回答“解决什么问题”或“做什么”的问题。n程序遵循一定的规则和步

39、骤，而不是指令或语句的随意堆砌。n程序的执行者是计算机。n程序是由人来编写或设计的，是人针对要处理和解决的问题而设计的求解方法和步骤交由计算机操作、运算和处理的说明。n程序的运行是自动完成的。n程序是算法的程序设计语言描述，但程序并不一定就是算法，因为程序没有有穷性要求。 1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述解决一个实际问题的一般过程n明确问题要求。n建立数学模型。n算法设计。n编写程序。n调试程序。n运行及结果分析。n编写程序文档。 程序文档的内容n编写文档是最容易被忽视了的一个重要环节。没有文档资料对于

40、软件的维护会带来许多困难，即使是设计者自己也不例外。文档资料要写得完整、清楚和准确，一般应包含如下内容：n算法或程序的功能描述和适用范围；n运行环境，包括机型、操作系统平台、语言种类、占用空间等；n使用说明，即使用该程序的操作命令、I/O格式、各种情况下的操作等说明；n流程图及说明；n程序清单及注释。实现策略n在拿到一个设计问题之后，有两种不同的方法可供选择：n一种是自顶向下逐步求精细化；n一种是自底向上逐步堆砌积累。n结构化程序设计提倡自顶向下逐步求精细化的分析设计方法，从求解问题本身到得出一系列基本操作逐层次展开细化，是一种将问题求解方法由抽象逐步到具体化的过程。n采用自顶向下逐步求精细化

41、的设计方法，易于保证和验证程序的正确性。 1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述程序调试n程序调试是开发过程中最艰巨的脑力劳动。面对错误征兆，如何在浩如烟海的程序元素中找出有错误的元素，这是调试过程中最关键的技术问题。n现有的调试技术有如下三类：n输出存储器内容。常以八进制或十六进制形式打印出存储器内容并检查分析。 n在程序中插入打印语句，调试结束后要将为了调试而插入的语句删掉。n借助调试工具。调试工具可以提供程序动态行为的有关信息，但不需要修改源程序。例如，在turbo C中提供了专门的程序调试工具debu

42、gger程序。 调试策略n试探法n回溯法n对分查找法n归纳法。其步骤为：n收集已知的使程序出错与不出错的一切数据；n整理数据以发现规律或矛盾；n提出关于故障的若干假设；n证明假设并据此设法排除故障。n演绎法。其步骤为：n设想并列出所有可能产生错误的原因；n利用已有的数据排除不正确的假设；n精化剩余的假设；n证明假设并据此设法排除故障。 查错策略n查错策略主要有两种：黑盒子测试和白盒子测试n如果已知产品的功能，可以测试它的每一个功能是否都达到了预期的要求，这种方法叫黑盒子测试。n如果已知产品的内部活动方式，可以测试它的内部活动是否都符合设计要求，这种方法称之为白盒子测试。查错策略n查错策略主要有

43、两种：黑盒子测试和白盒子测试n无论使用哪一种方法，对程序的穷举测试是不可能的，我们所能做到的是通过有限的测试尽可能多地发现错误。测试只能发现错误，而不能保证程序没有错误。查错的关键在于设计好测试用例，即确定一组最有可能发现某个或某类错误的测试数据的设计。 常用的测试用例设计方法n逻辑覆盖。它是一种白盒子测试技术。常用的逻辑覆盖有语句覆盖、分支覆盖、条件覆盖、分支/条件覆盖、多重覆盖和循环覆盖等。n等价类划分。是一种黑盒子测试技术。n边界值分析。是一种黑盒子测试技术。n图形技术。它提供设计测试用例的工具，常见的有因果图和程序图。n测试的目的是为了发现错误，而纠错则是确定错误在程序中的确切位置和性

44、质并改正它。纠错的关键在于确定错误的位置（即错误定位），常用的纠错技术有试探法、回溯法、对分查找法、归纳法和演译法。1.4 算法与程序1.4.1程序的基本概念1.4.2问题求解与实现策略1.4.3程序调试与查错策略1.4.4程序设计方法概述程序设计方法概述 n程序是软件的重要组成部分，程序设计是软件开发的重要方面。n程序设计方法对程序设计工作的质量以及所设计出来的程序的质量影响重大，因而对程序设计方法的研究也越来越受到人们的重视。n程序设计方法学主要研究涉及用于指导程序设计工作的原理和原则，研究基于这些原理和原则的具体设计方法和技术，研究各种方法的共性和理论基础。 程序设计方法概述（续）n程序设计方法可以分为两类：n全局性的n局部性的n全局性的。如结构化程序设计方法，它不仅要求编出的程序结构良好，而且要求程序设计过程是结构化、层次式、逐层降低抽象级别的。n局部性的。如子例程方法、协同例程方法等。程序设计方法与技术n结构化程序设计 n软件工程方法n面向对象的程序设计n多媒体程序设计n可视化编程n函数程序设计n逻辑程序设计n并行程序设计n分布式程序设计n文化程序设计