算法与程序设计基础.ppt

下面描述中，符合结构化程序设计风格的是(A)

A)使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B)模块只有一个入口，可以有多个出口C)注重提高程序的执行效率D)不使用goto语句

(2)结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、______和限制使用goto语句。??答：模块化(3)结构化程序所要求的基本结构不包括(B)A)顺序结构B)GOTO跳转C)选择（分支）结构D)重复（循环）结构算法1程序设计方法与风格2结构化程序设计3面向对象的程序设计4小结5第2章 算法与程序设计基础算法的基本概念算法的复杂度2.1算法1．算法的定义2.1.1算法的基本概念算法是指对解题方案的准确而完整的描述，即解决问题的操作步骤。算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，然后再用具体的程序设计语言描述此算法（即编程）。在编程时，由于要受到计算机系统运行环境的限制，程序的编制通常不能优于算法的设计。2．算法的基本特征?可行性?确定性?有穷性拥有足够的情报操作步骤为有限个，每个步骤都能在有限时间内完成。算法执行应当能够得出满意的结果，即必须有一个或多个输出。对算法中每一步的描述都是明确的，没有多义性，只要输入相同，初始状态相同，则无论执行多少遍，所得的结果都应该相同。算法在拥有足够的输入信息和初始化信息时，才是有效的。算法的功能取决于两个方面因素：选用的操作和各个操作之间的顺序一个算法通常由两种基本要素组成对数据对象的运算和操作算法的控制结构，即运算或操作间的顺序。0103023.算法的基本要素4类基本的运算和操作运算类型操作例子算术运算+、－、×、÷2+3、8－2…逻辑运算与（＆）、或（||）、非（！）！1、1||0、11…关系运算、、=、≠ab、a=c、b≠c…数据传输赋值、输入、输出A=0、b=3…A算法的控制结构是算法中各个操作之间的执行顺序。B算法一般由顺序、选择（又称分支）和循环（又称重复）3种基本结构组合而成。C描述算法的工具有传统的流程图、N-S结构化流程图和算法描述语言等。算法的控制结构顺序结构流程图顺序结构是最简单的一种基本结构BA图中A和B两个框是顺序执行的，即在执行完A框所指定的操作后，必然接着执行B框所指定的操作。选择结构流程图选择结构根据给定的条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框。无论走哪一条路径，在执行完A或B之后，都脱离本选择结构。A或B两个框中可以有一个是空的，即不执行任何操作。ABPPA当型（While型）循环结构的流程图当型循环结构的功能是当给定的条件P成立时，执行A框操作，执行完A后，再判断条件P是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次P条件不成立为止，此时不执行A框，脱离本循环结构直到型（Until型）循环结构直到型循环结构的功能是先执行A框，然后判断给定的P条件是否成立，如果P条件不成立，则再执行A，然后再对P条件进行判断，如果P条件仍然不成立，又执行A，如此反复执行A，直到给定的P条件成立为止，此时不再执行A，脱离本循环结构。三种结构的N-S结构化流程图顺序结构的N-S图选择结构的N-S图当型循环结构直到型循环结构ＡＢP成立不成立AB当p成立AA直到p成立常用的几种算法设计方法有列举法、递推法、递归01法、贪婪法、分治法和动态规划法等。024.算法基本设计方法一个算法的质量可以用算法的复杂度来衡量。01算法的复杂度包括算法的时间复杂度和算法的空间复杂度两种。022.1.2算法的复杂度04030102算法的时间复杂度是指执行算法所需要计算工作量。算法执行程序的具体时间和算法的时间复杂度并不是一致的。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是所要解决的问题的规模（通常用整数n表示）的函数算法的工作量=f(n)，其