《算法与数据结构》第1章算法与程序ppt.ppt

算法与数据结构,第1章 算法与程序 第2章 常用数据结构 第3章 简单数据结构 第4章 树和二叉树 第5章 图与网 第6章 数据结构的程序实现 第7章 检索及基本算法 第8章 排序及基本算法,算法与数据结构,第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，返回步骤继续进行。,什么是算法（续）,由此，我们可以得出这样的结论，算法就是求解问题的方法和步骤。这里的方法和步骤是一组严格定义了运算顺序的规则；每一个规则都是有效的，且是明确的；按此顺序将在有限次数下终止。 有关算法（Algorithm）一词的定义不少，但其内涵基本上是一致的。最为著名的定义是计算机科学家D.E.Kunth在其巨著计算机程序的艺术（ Art of Computer Program）第一卷中所做的有关描述。其非形式化的定义是： 一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题的运算序列。,什么是算法（续）,算法的形式化定义如下所述： 算法是一个四元组，即（Q，I，F）。 其中： Q是一个包含子集I和的集合，它表示计算的状态； I表示计算的输入集合； 表示计算的输出集合； F表示计算的规则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q Q，有F(q)=q。,什么是算法（续）,一个算法是对于任何的输入元素x，都在有穷步骤内终止的一个计算方法。 在算法的形式化定义中，对任何一个元素xI，x均满足性质 x0=x，xk+1=F(xk)，（k0） 该性质表示任何一个输入元素x均为一个计算序列，即x0，x1，x2，xk；该序列在第k步结束计算。,1.1 算法的基本概念,1.1.1 什么是算法 1.1.2 算法的基本特性,算法的基本特性,输入（Input） 输出（Output） 确定性（Definiteness） 有穷性（Finiteness） 有效性（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 程序语言表示,自然语言表示,自然语言即人们日常使用的语言，如汉语、英语、日语、法语、德语等等。使用自然语言描述算法，人们比较容易接受和理解。如前面的欧几里德算法就是用自然语言描述的。然而，自然语言也具有许多缺点，在使用自然语言描述算法时一定要引起注意： 自然语言存在着歧义性，容易导致算法的不确定性； 自然语言容易冗长，使得描述不够简洁； 自然语言的表示形式是顺序的，描述分支选择和转移时不够直观； 自然语言与计算机程序设计语言的差别较大，不易转换为程序。,1.2 算法的表示,1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示 1.2.5 程序语言表示,流程图表示,流程图是描述算法的图形工具，它采用如下所示的一组图形符号来表示算法：,起止框，表示算法的开始或结束；只有一个入口或一个出口。 输入输出框，表示算法中数据信息的输入和输出；有一个入口和一个出口。 判断框，表示条件判断；有一个入口和多个出口。 处理框，表示算法中的一个（或一组）运算或处理；有一个入口和一个出口。 流程线，表示算法中各步骤之间的次序关系。 连接点，表示算法中的连接位置，主要用于同一算法在不同页描述时的接续等情况。 注释框，用于对算法中某些操作的注释说明。,流程图表示举例,欧几里德算法的流程图描述如图1-1所示,流程图表示（续）,同自然语言相比，用流程图描述算法直观，可以一目了然；算法步骤间用流程线连接，次序关系清楚，容易理解；可以很方便地表示顺序、选择和循环结构，不依赖于任何计算机和计算机程序设计语言，有利于不同环境下的程序设计。但是，流程图也还存在一些缺点，诸如： 不易于表示算法的层次结构； 不易于表示数据结构和模块调用关系等重要信息； 容易使人过早地考虑算法的控制流程，而忽视算法的全局结构； 用流程线代表控制流，控制转移随意性较大。若对流程线的使用不加限制，随着求解问题规模和复杂度的增加，流程图会变得很复杂，使人难以阅读、理解和修改，从而使算法的可靠性难以保证。,1.2 算法的表示,1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示 1.2.5 程序语言表示,NS图表示,为了克服传统流程图的缺点，1973年美国学者纳斯（I.Nassi）和施内德曼（B.Shneiderman）提出了一种表示算法的较好工具N-S图。 它独立于任何计算机和计算机语言，又能很方便地转换为计算机语言程序； 它去掉了流程线全部用矩形方框来描述，限制了算法流程转移控制的随意性，又节省了篇幅； 它很容易表示算法中的嵌套关系和模块中的层次关系，功能域可以从框图中直接反映出来； 它仍是图形工具，阅读起来直观、明确、容易理解。,NS图表示（续）,N-S图的基本图形符号如下：,顺序结构，由两个或多个矩形框组成。其中A和B可以是基本操作，也可以是其它基本结构（如选择结构，循环结构）。 选择结构，当条件P成立时执行操作A，否则执行操作B。 当型循环结构。当条件P成立时反复执行操作A，直到条件P不成立时止。 直到型循环结构。反复执行操作A，直到条件P成立时止。,NS图表示举例,由于N-S图象一个多层的盒子，所以也称作盒图。用N-S图表示欧几里德算法如图1-2所示。,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(算法结束),1.2 算法的表示,1.2.1 自然语言表示 1.2.2 流程图表示 1.2.3 NS图表示 1.2.4 伪代码表示 1.2.5 程序语言表示,程序语言表示,计算机程序设计语言，是计算机能够接受、理解和执行的算法描述工具。 计算机不能直接识别自然语言、流程图、N-S图和伪代码等工具描述的算法，而设计算法的目的就是要用计算机来解决问题，算法最终都要用某一具体的计算机程序设计语言来表示。 从这个意义上讲，流程图、N-S图和伪代码都仅仅是为了求解问题而设计算法时的辅助工具。 为了更好更准确地描述算法，人们使用图形或表格还创造了许多专用的算法设计辅助工具，如PAD图、判定表、数据流图、Warnier-rr图等等。,程序语言表示（续）,和自然语言一样，计算机程序设计语言也是串行的描述，很不直观。 对于较复杂的问题，人们很难用计算机程序设计语言直接写出程序。 所以在算法设计阶段，一般是先采用某个专用的辅助工具来描述算法，在算法设计好之后，再把它转化为某一具体程序设计语言描述的程序。,程序语言表示（续）,作为例子，下面我们给出欧几里德算法的C语言描述如下： #include ”stdio.h” main() int m,n,r; printf(“请输入两个正整数：”)； scanf(“%d%d”, ,运行结果： 请输入两个正整数：56 32 56和32的最大公约数是：8,第1章 算法与程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的设计与评价 1.4 算法与程序,1.3 算法的设计与评价,1.3.1 评价算法的标准 1.3.2 算法的环路复杂度 1.3.3 算法的时空效率 1.3.4 常见的算法设计方法,评价算法的标准,评价一个算法优劣的五条标准： 正确性 可读性 健壮性 高效性 简洁性 一个好的算法是满足这五条标准要求的算法。,评价算法的“正确性”标准,所设计出来的算法要能够正确求解给定的问题。 这就要求算法中的每一个步骤的描述是准确无歧义的，并且是可以执行的； 要求算法能够满足问题要求，并在有限步骤内获得结果； 否则就不具备正确性要求，更谈不上解决给定的实际问题了。 算法要能经得起一切可能的输入数据的考验。,评价算法的“正确性”标准（续）,在将算法用程序语言表示为特定语言的程序后还必须注意： 程序中不含有语法错误； 对于一切合法的输入数据，程序能够产生满足要求的输出结果； 对于一切非法的输入数据，程序能够得出满足规格说明的结果； 对于精心选择的，甚至是带有刁难性的典型测试数据，程序都有满足要求的输出结果。,评价算法的“可读性”标准,表示出来的算法要能够方便地供人们阅读、理解和交流。 算法的可读性好是保证正确性的前提，良好的可读性有利于人们理解算法思想，减少出错机会，便于检查和修改。 可适当地增加注释，增强算法或程序的可读性。,评价算法的“健壮性”标准,算法对意外情况的反映能力要强。 当输入数据非法、0作除数、负数开平方等，算法应能做出相应的处理，给出错误信息或终止算法执行，避免产生错误的或莫明其妙的输出结果。,评价算法的“高效性”标准,算法的执行效率要高。 算法的效率可分为时间效率和空间效率。 时间效率是通过该算法转化的程序在计算机上运行的时间耗费来确定，在算法设计与分析阶段用执行基本操作的次数（是问题规模的函数）相对于问题规模的渐近阶来表示。 空间效率主要考虑除存储数据结构之外的辅助存储空间。一个高效算法是指执行算法耗费时间少，使用辅助存储空间小的算法。,评价算法的“简洁性 ”标准,所设计出来的算法要尽可能地简洁。 对于同一问题所设计的不同算法，越简洁明了的越好。 越简洁的算法可读性越好，越易于理解、编码和调试、测试，越受人们欢迎。,评价算法的标准（续）,在评价一个算法时，要对这五个方面综合考虑，不要片面追求某一指标。 有些指标之间往往是相互制约的，如时间效率与空间效率，简洁性与高效性等等； 要学会针对具体问题要求和软硬件实现环境进行综合平衡，设计出满足需要的好算法。,1.3 算法的设计与评价,1.3.1 评价算法的标准 1.3.2 算法的环路复杂度 1.3.3 算法的时空效率 1.3.4 常见的算法设计方法,算法的环路复杂度,算法的复杂性很大程度上取决于控制流程的复杂性。单一的顺序结构最简单； 循环结构和选择结构所构成的环路越多算法就越复杂。 基于这一种观点，针对算法的流程图表示，我们先介绍算法的环路复杂度的概念和度量方法。,算法的环路复杂度（续）,算法（或程序）的环路复杂度度量方法，以图论为工具，先画出程序图，然后用该程序图的环路作为算法（或程序）复杂性的度量值。 所谓程序图可以看成是退化了的流程图，也就是把算法（或程序）流程图中的每个处理框都退化成为一个点，原来连接不同框之间的流程线变成连接不同点的有向弧，这样得到的有向图称之为程序图。 程序图是连通图，这是因为从算法流程的入口点总是能够到达图中的任何一个结点；如果我们再增加一条由出口到达入口的虚弧，则从图中任何一个结点出发都可以到达其它所有结点，使得程序图变为强连通的有向图。,算法的环路复杂度举例,例如图1-1所示的欧几里德算法的流程图所对应的程序图如图1-3所示。,算法的环路复杂度的计算方法,强连通图中线性无关的环路个数我们可以用如下的公式确定： V(G)=e-n+p 其中： V(G)是图G中环路的个数； e是图G中有向弧的条数，包括由出口到入口增加的一条虚弧； n是图G中结点的个数； p是图G中连通分量的个数，对于连通图而言p恒为1。,环路复杂度的计算方法举例,例1：前述的欧几里德算法的程序图（图1-3）中，有8条有向弧和7个结点，由该公式可以确定其环路复杂度如下： V(G)=8-7+1=2,例2：如图1-4所示的程序图中， 有11条弧和7个结点，由该公式 可如下确定其环路复杂度： V(G)=11-7+1=5,算法的环路复杂度的计算方法（续）,除了应用上述的公式法计算之外，还有如下的两种方法可以用来确定程序图的环路复杂度： 观察法，即观察强连通的程序图在平面上所围成的独立区域的个数。如图1-3中由有向弧（含虚弧，下同）和结点围成的独立区域有两个，即环路数为2，环路复杂度为2；而图1-4中的独立区域有五个，环路数为5，环路复杂度为5。,算法的环路复杂度的计算方法（续）,利用判定语句计算法，即把程序图中所有出现的分支结点处所需要的判定的总个数加起来再加1。每一个分支结点处所需要的判定数为该结点分支数（即出度）减1，即二路分支需要一个判定，三路分支需要两个判定，依此类推。如图1-3中只有一个结点（第四个）是分支结点且为二路分支，故所需要的判定为一个，其环路复杂度（即环路数）为2；而图1-4中有两个结点（上数第二个和左下结点）是分支结点且结点都为三路分支，故所需的判定为2+2=4个，其环路复杂度为5。,算法的环路复杂度（续）,算法的环路复杂度越高，说明算法的控制越复杂，在转化为程序时的难度就越大，转化后的程序测试难度也就越大问题越多。在设计算法时，一般地应控制模块的环路复杂度在10以内为宜。 环路复杂度的度量方法的最大优点在于它的简明性，只要知道算法中的判定个数即可。然而它也有许多不足之处，如没有区分不同类型控制流的不同复杂性（如选择结构和循环结构之间，嵌套选择结构和多选择结构之间的不同复杂性）等。在评价和度量算法复杂性时，可根据实际需要结合其它方法一块使用。,1.3 算法的设计与评价,1.3.1 评价算法的标准 1.3.2 算法的环路复杂度 1.3.3 算法的时空效率 1.3.4 常见的算法设计方法,算法的时空效率,如果算法是用N-S图、伪代码、程序语言或其它方式表示的，要度量其环路复杂度需要先把它们的表示转化为流程图表示，然后把流程图退化为程序图再确定其环路数。 环路复杂度是一种定量地评价算法复杂度的方法。 下面我们再介绍一种适应面更广泛的定性评价算法复杂度的方法，即大O方法。,算法的时空效率（续）,执行一个算法的时间代价，是指将该算法转化为程序后在计算机上运行的时间耗费，即算法中每条语句在计算机上执行的时间总和，大致上可以认为它等于计算机执行一种基本操作（如赋值运算、比较运算、移动操作等）所需的时间与算法中进行基本操作总次数的乘积。 而每条语句的执行时间则应该是执行该语句一次所需的时间与该语句执行的次数（也称之为频度）的乘积。 某条语句执行一次所需的时间一般地是随机器而异的，取决于具体机器的性能、速度和编译代码的质量，是由机器本身的软、硬件环境所决定的，与算法无关。所以，我们可以假设执行每条语句所需的时间均为单位时间。 因此，对算法执行时间的讨论就可以转化为对算法中所有语句的执行次数（即频度）的讨论。,大O方法计算举例,两个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方法计算举例（续）,其中，每一条语句的频度说明在注释中。我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则该算法的时间耗费T(n)可表示为 T(n)=2n3+3n2+2n+1 显然，它是矩阵的阶（该问题的规模）n的函数。并且当n时，T(n)/n32。这表示当n趋于无穷大时，T(n)与n3是同阶函数或者说是同量级的。引入大O记号可记作 T(n)=O(n3),时间复杂度,引入大O记号表示的算法的时间耗费T(n)通常称之为算法的时间复杂度，如矩阵相乘算法的时间复杂度为O(n3)。 这种时间复杂度的大O表示法，实质上是把算法的基本操作总数表示为问题规模n的函数之后，寻找出当问题规模n趋于无穷大时该函数的同阶最简形式即渐近性态下的同阶最简函数，有时也简称之为渐近阶。 问题的规模是指算法中要处理的数据量的规模，通常用一个整型量n来表示。对于求解不同的问题，规模n具有不同的值。,时间复杂度（续）,时间复杂性的渐近阶表示，是对算法时间性能优劣的宏观定性评价。 例如，为了求解同一问题所设计的两个不同的算法A1和A2，其时间耗费分别为T1(n)=40n2和T2(n)=5n3；显然当问题规模nT2(n)，算法A2比A1时间花费少；利用渐近阶表示的时间复杂度O(n2)和O(n3)反映了对这两个算法时间性能优劣的宏观定性评价结论。 由于是宏观的定性评价，算法中频度最大的语句的频度，与算法中每条语句频度的和T(n)是同阶函数； 所以人们在计算算法时间复杂度时，往往只需考虑算法中频度最大的语句的频度就可以了。,时间复杂度计算举例,例如对于下面的程序段： x=0; for(i=1;in;i+) for(j=1;ji;j+) for(k=1;kj;k+) x+; 我们只须关心程序段中执行频度最大的语句最内层循环的循环体语句x+，它的执行次数是 由于n3是它的渐近性态下的同阶最简函数，可得上述程序段的时间复杂度为T(n)= O(n3)。,简明实用的程序分析法则,执行一条基本操作如读写或赋值语句等，需要O(1)的时间花费。 对于顺序结构，需要执行一系列语句，所用时间用求和准则估计。 对于选择结构如if语句，主要时间耗费是执行then子句或else子句所用的时间；此外，检验条件还需用O(1)的时间。多选择结构的时间耗费与if语句类同。 对于循环结构，执行时间为多次迭代中循环体的执行和检验循环条件的耗时，常用乘法准则估计。 对于复杂算法，可以将它分成几个容易估算的部分分别估计，然后利用求和准则和乘法准则计算整个算法的时间复杂度。,简明实用的程序分析法则（续）,大O下的求和准则 若T1(m)=O(f(m)，T2(n)=O(g(n) （不相同问题规模时） 则T1(m)+ T2(n)=O(f(m)+g(n) 若T1(n)=O(f(n)，T2(n)=O(g(n) （相同问题规模时） 则T1(n)+ T2(n)=O(max(f(n), g(n) 若g(n) =O(f(n) （特殊运算规则） 则O(f(n) +O(g(n)=O(f(n),简明实用的程序分析法则（续）,大O下的乘法准则 若T1(m)=O(f(m)，T2(n)=O(g(n) （不相同问题规模时） 则T1(m)*T2(n)=O(f(m)*g(n) 若T1(n)=O(f(n)，T2(n)=O(g(n) （相同问题规模时） 则T1(n)*T2(n)=O(f(n)*g(n) 若c是一个正常数 （特殊运算规则） 则O(cf(n)=O(f(n),程序分析法则举例,如对前述的矩阵相乘算法，它是三层嵌套的循环结构，我们可以从最内层循环的循环体开始分析： 是赋值语句，与问题规模无关，时间复杂度为常数阶O(1)，即T5(n)=O(1)； 对于第条语句，T4(n)=O(n)，它与第条语句是循环关系应该用乘法准则，即T4(n)*T5(n)=O(1*n)=O(n)； 对于第条语句T3(n)=O(1)，它与第、是顺序结构应该用求和准则，即T3(n)+T4(n)* T5(n)=O(max(1,n)=O(n)； 第条语句其T2(n)=O(n)，到是它的循环体适用乘法准则，故有T2(n)*(T3(n)+T4(n)*T5(n)=O(n*n)=O(n2)； 第条语句的耗时T1(n)=O(n)，到是它的循环体适用乘法准则，所以有T1(n)*(T2(n)*(T3(n)+T4(n)*T5(n)=O(n* n2)=O(n3)。,时间复杂度（续）,利用这组程序分析法则可得矩阵相乘算法的时间复杂度为T(n)=O(n3)，它与我们在前面用所有语句执行频度的总和关于问题规模的函数表达后求渐近阶得出的结果一致，但却省去了计算所有语句执行频度总和的麻烦。 实际上，算法或程序的执行时间不仅依赖于所求解问题的规模，还与它所处理的数据的状态有关。 一般在不做任何说明的情况下，讨论其时间复杂度是指在最坏情况下的时间复杂度，通常可记作Tmax(n)；有时还要讨论其平均情况下的时间复杂度Tavg(n)。,空间复杂度,衡量一个算法优劣的另一个因素是空间代价，即执行由算法转化的程序时所占用存储空间的大小。为了执行算法所占用的存储空间包括如下三个方面： 为了在计算机上存储程序本身所占用的存储空间。 算法或程序中的输入和输出数据所占用的存储空间。 算法或程序在执行过程中临时占用的存储空间。这部分空间是与算法本身密切相关的，因算法设计的不同而异，是我们讨论算法的空间代价时所要着重讨论的方面。 度量一个算法或程序在执行过程中所花费的额外存储开销（即临时存储工作单元）的大小也是用大O方法，度量的结果称之为算法的空间复杂度。空间复杂度和时间复杂度一样，也是用相对于问题规模函数的渐近阶形式给出，如O(1)、O(n)等。,时（空）间复杂度,常见的时间（或空间）复杂度有： 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) 指数阶O(2n) 指数阶的算法效率极低，当问题规模n稍大时就无法使用。,1.3 算法的设计与评价,1.3.1 评价算法的标准 1.3.2 算法的环路复杂度 1.3.3 算法的时空效率 1.3.4 常见的算法设计方法,常见的算法设计方法,为了获得有效的算法，必须了解一些解题的基本思想和方法。对于许多问题，只要仔细分析了数据对象后，相应的处理方法就有了；对于有些问题则不然。然而，作为探寻问题求解思路的基本思想和方法，对于任何算法设计都是有用的。下面我们简要介绍一些常用的算法设计方法和技术： 穷举法 迭代法 递推法 递归法 回溯法 贪婪法 分治法,1.穷举法,穷举法亦称作枚举法。它的基本思想是： 首先根据求解问题的部分条件确定答案的大致范围，即列举出解的所有可能的情况； 然后在此范围内对所有可能的情况逐一验证，若某个情况经过验证符合问题条件则为一个解，若全部情况验证后均不符合题目条件则问题无解，从而得出求解问题的完整解。 例如要找出200到500之间的所有素数，我们只要对这个范围内的每一个数逐个用素数的定义去判断就行了。 穷举法的特点是算法简单，但有时运算量大效率较低。在可以确定解的取值范围，但一时又找不到更好的算法时，就可以使用穷举法求解。,2.迭代法,迭代法的基本思想是，由一个量的原值求出它的新值，不断地再用新值替代原值求出它的下一个新值，直到得到满意的解。新值与原值之间存在一定的关系，这种关系可以用一个公式来表示，称之为迭代公式。 迭代法主要用于那些很难用或无法用解析法求解的一类计算问题，如高次方程和超越方程等；使得复杂问题的求解过程，转化为相对较简单的迭代算式的重复执行过程，用数值方法求出问题的近似解。,迭代法（续）,使用迭代法构造这一类问题求解算法的基本方法是： 先确定一个收敛性能好（即收敛速度快）的迭代公式，选取解的一个近似值（即迭代初值）和解的精度要求（即允许的最大误差范围）， 然后用循环处理实现迭代过程，终止循环的条件是前后两次得到的近似值之差的绝对值小于解的精度要求，并认为最后一次得到的近似解为问题的解。 这种迭代方法称作逼近迭代，如著名的牛顿迭代法就是这种逼近迭代方法。 此外，精确值的计算也可以使用迭代法。例如计算s=1+2+3+1000，可选取迭代公式s+is和迭代初值0（即0s）。,3.递推法,递推法是从前面的一些量推出后面的一些量的一种方法，它从已知的初始条件出发，逐次推出所需要求解的各中间结果和最终结果。 递推过程往往表现为迭代，即由一些量的原值推出它的新值，不断地用新值替代原值推出下一个新值，直到推出最终结果，新值与原值之间的关系用递推公式表示。 例如Fibonacci数列存在着递推关系 F(1)=1，F(2)=1，F(n)= F(n-1)+ F(n-2) (n2),递推法（续）,需要求出Fibonacci数列中某一项的值，利用递推公式逐步求出F(3)，F(4)直到求出该项的值，也许有人会说，如果使用通项公式计算岂不更方便吗？事实上，有些递推问题的通项公式是很难找出的，即使找出通项公式计算也不一定简便。如Fibonacci数列的通项公式为 显而易见，找出这个通项公式不易，利用它计算F(n)也相当费力。相反地，若利用递推初值和递推公式计算F(n)就容易和方便多了。,4.递归法,如果一个过程直接或间接地调用它自身，则称该过程是递归的；直接调用自身称作直接递归，间接调用自身则称作间接递归。 递归是构造算法的一种基本方法，它将一个复杂问题归结为若干个较为简单的问题，然后将这些较为简单的问题进一步归结为更简单的问题，这个过程一直进行下去直到归结为最简单的问题时为止。这个最简单的问题即为递归终止条件，也称作递归出口。 在高级语言程序设计课程中介绍的著名的汉诺（Hanoi）塔问题的求解算法和后续章节中介绍的有关树和二叉树的许多算法，都是递归法的典型运用。,递归法和递推法比较,递归和递推是既有区别又有联系的两个概念。 递推是从已知初始条件出发逐次推出最后所求的值； 递归则是从函数本身出发，逐次上溯调用其本身求解过程直到递归出口，然后再从里向外倒推回来得到最终的值。 一般地说，一个递推算法总可以转换为一个递归算法。对于同一问题所设计的递归算法往往要比相应的非递归算法（如递推算法）付出更多的执行时间代价和更多的辅助存储空间开销。,递归法和递推法比较（续）,然而，利用递归方法分析和设计算法可使难度大幅度降低，且程序设计语言中一般都提供递归机制；利用递归过程描述问题求解算法不仅非常自然，而且算法的正确性证明要比相应的非递归算法容易得多；另外有成熟的方法和技术，可以很方便地把递归算法改写为非递归算法。 所以，递归技术是算法设计的基本技术，递归方法是降低分析设计难度提高设计效率的重要手段和工具。,5.回溯法,回溯法是算法设计中的一种基本策略，它通过对问题的分析找出一个解决问题的线索，然后沿这个线索逐步试探。 对于每一步试探，若成功就继续下一步试探；若不成功就逐步退回换别的路线再进行试探，直至探索成功得到问题的解或试探完所有的线索问题无解。 在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，许多都可以用回溯法来求解。 例如，在国际象棋棋盘上的骑士周游问题和我们平时参加的走迷宫游戏，都是使用回溯法进行的。,6.贪婪法,贪婪法也称作贪心算法，它是通过一系列的选择来得到问题的一个解。 贪婪法在每一步所做出的选择，都总是在当前状态下看来是最好的选择即贪婪选择，并希望通过每次所作的贪婪选择导致最终结果是求解问题的一个最优解。 换句话说，贪婪法并不从整体最优上加以考虑，它做出的选择只是在某种意义上的局部最优选择，但希望算法得到的最终结果也是整体最优的。虽然这种贪婪策略不能对所有问题都得到整体最优解，然而在许多情况下的确能够产生整体最优解。 在一些情况下，即使贪婪算法不能得到整体最优解，其最终结果却是最优解的很好近似。,7.分治法,求解一个复杂问题时，尽可能地把这个问题分解为若干较小的子问题，在找出各个较小问题的解之后再组合成为整个问题的解，这就是所谓的分治法。 使用分治法时，往往要按问题的输入规模来衡量问题的大小；当要求解问题的输入规模相当大时，应选择适当策略将输入划分成若干子集合得到一组子问题，在求出各子问题的解之后用适当的方法把它们合并成整个问题的解，分治法便应用成功了。 如果得到的子问题还相对过大，可再次使用分治法将这些子问题进一步划分成更小的子问题。,第1章 算法与程序,1.1 算法的基本概念 1.2 算法的表示 1.3 算法的设计与评价 1.4 算法与程序,算法与程序,算法与程序是密切相关的两个概念。 研究和讨论算法是为了设计出更好的程序，设计好的算法都要转化为某种语言描述的程序才能在计算机上运行； 或者说程序是算法表示的最终形态，程序只有装入计算机中运行（即程序的执行）时才能够起到对实际问题求解的作用。,1.4 算法与程序,1.4.1 程序的基本概念 1.4.2 问题求解与实现策略 1.4.3 程序调试与查错策略 1.4.4 程序设计方法概述,程序的基本概念,在低级语言中，程序表现为一组指令和有关数据； 在高级语言中，程序表现为一组说明和语句。 程序既是软件的固有部分，又是软件研究的对象，程序的质量决定着软件的质量。 衡量一个程序的质量，除了对程序结构进行静态考察外，还必须考察其执行过程。 与执行无关的特性称之为程序的静态特性， 与执行有关的特性称之为程序的动态特性。,程序的特征,程序描述解决某一问题的特定任务与功能，回答“解决什么问题”或“做什么”的问题。 程序遵循一定的规则和步骤，而不是指令或语句的随意堆砌。 程序的执行者是计算机。 程序是由人来编写或设计的，是人针对要处理和解决的问题而设计的求解方法和步骤交由计算机操作、运算和处理的说明。 程序的运行是自动完成的。 程序是算法的程序设计语言描述，但程序并不一定就是算法，因为程序没有有穷性要求。,1.4 算法与程序,1.4.1 程序的基本概念 1.4.2 问题求解与实现策略 1.4.3 程序调试与查错策略 1.4.4 程序设计方法概述,解决一个实际问题的一般过程,明确问题要求。 建立数学模型。 算法设计。 编写程序。 调试程序。 运行及结果分析。 编写程序文档。,程序文档的内容,编写文档是最容易被忽视了的一个重要环节。没有文档资料对于软件的维护会带来许多困难，即使是设计者自己也不例外。文档资料要写得完整、清楚和准确，一般应包含如下内容： 算法或程序的功能描述和适用范围； 运行环境，包括机型、操作系统平台、语言种类、占用空间等； 使用说明，即使用该程序的操作命令、I/O格式、各种情况下的操作等说明； 流程图及说明； 程序清单及注释。,实现策略,在拿到一个设计问题之后，有两种不同的方法可供选择： 一种是自顶向下逐步求精细化； 一种是自底向上逐步堆砌积累。 由于人脑思维很难一下子触及问题细节，所以自底向上方法较难运用；即使运用，也难设计出清晰的程序层次结构。 结构化程序设计提倡自顶向下逐步求精细化的分析设计方法，从求解问题本身到得出一系列基本操作逐层次展开细化，是一种将问题求解方法由抽象逐步到具体化的过程。 采用自顶向下逐步求精细化的设计方法，易于保证和验证程序的正确性。,1.4 算法与程序,1.4.1 程序的基本概念 1.4.2 问题求解与实现策略 1.4.3 程序调试与查错策略 1.4.4 程序设计方法概述,程序调试,程序调试是开发过程中最艰巨的脑力劳动。面对错误征兆，如何在浩如烟海的程序元素中找出有错误的元素，这是调试过程中最关键的技术问题。 现有的调试技术有如下三类： 输出存储器内容。常以八进制或十六进制形式打印出存储器内容并检查分析。 在程序中插入打印语句，调试结束后要将为了调试而插入的语句删掉。 借助调试工具。调试工具可以提供程序动态行为的有关信息，但不需要修改源程序。例如，在turbo C中提供了专门的程序调试工具debugger程序。,调试策略,试探法 回溯法 对分查找法 归纳法。其步骤为： 收集已知的使程序出错与不出错的一切数据； 整理数据以发现规律或矛盾； 提出关于故障的若干假设； 证明假设并据此设法排除故障。 演绎法。其步骤为： 设想并列出所有可能产生错误的原因； 利用已有的数据排除不正确的假设； 精化剩余的假设； 证明假设并据此设法排除故障。,查错策略,查错策略主要有两种：黑盒子测试和白盒子测试 如果已知产品的功能，可以测试它的每一个功能是否都达到了预期的要求，这种方法叫黑盒子测试。 如果已知产品的内部活动方式，可以测试它的内部活动是否都符合设计要求，这种方法称之为白盒子测试。 无论使用哪一种方法，对程序的穷举测试是不可能的，我们所能做到的是通过有限的测试尽可能多地发现错误。测试只能发现错误，而不能保证程序没有错误。查错的关键在于设计好测试用例，即确定一组最有可能发现某个或某类错误的测试数据的设计。,常用的测试用例设计方法,逻辑覆盖。它是一种白盒子测试技术。常用的逻辑覆盖有语句覆盖、分支覆盖、条件覆盖、分支/条件覆盖、多重覆盖和循环覆盖等。 等价类划分。是一种黑盒子测试技术。 边界值分析。是一种黑盒子测试技术。 图形技术。它提供设计测试用例的工具，常见的有因果图和程序图。 测试的目的是为了发现错误，而纠错则是确定错误在程序中的确切位置和性质并改正它。纠错的关键在于确定错误的位置（即错误定位），常用的纠错技术有试探法、回溯法、对分查找法、归纳法和演译法。,1.4 算法与程序,1.4.1 程序的基本概念 1.4.2 问题求解与实现策略 1.4.3 程序调试与查错策略 1.4.4 程序设计方法概述,程序设计方法概述,程序是软件的重要组成部分，程序设计是软件开发的重要方面。 程序设计方法对程序设计工作的质量以及所设计出来的程序的质量影响重大，因而对程序设计方法的研究也越来越受到人们的重视。 程序设计方法学主要研究涉及用于指导程序设计工作的原理和原则，研究基于这些原理和原则的具体设计方法和技术，研究各种方法的共性和理论基础。,程序设计方法概述（续）,程序设计方法可以分为两类： 全局性的 局部性的 全局性的。如结构化程序设计方法，它不仅要求编出的程序结构良好，而且要求程序设计过程是结构化、层次式、逐层降低抽象级别的。 局部性的。如子例程方法、协同例程方法等。,程序设计方法与技术,结构化程序设计 软件工程方法 面向对象的程序设计 多媒体程序设计 可视化编程 函数程序设计 逻辑程序设计 并行程序设计 分布式程序设计 文化程序设计,