算法与程序设计基础.ppt

第2章算法与程序设计基础,2.1算法2.2程序设计方法与风格2.3结构化程序设计2.4面向对象的程序设计2.5小结,2.1算法,2.2.1算法的基本概念2.2.2算法的复杂度,2.1.1算法的基本概念,1算法的定义,算法是指对解题方案的准确而完整的描述，即解决问题的操作步骤。算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，然后再用具体的程序设计语言描述此算法（即编程）。在编程时，由于要受到计算机系统运行环境的限制，程序的编制通常不能优于算法的设计。,2算法的基本特征,可行性确定性有穷性拥有足够的情报,操作步骤为有限个，每个步骤都能在有限时间内完成。,算法执行应当能够得出满意的结果，即必须有一个或多个输出。,对算法中每一步的描述都是明确的，没有多义性，只要输入相同，初始状态相同，则无论执行多少遍，所得的结果都应该相同。,算法在拥有足够的输入信息和初始化信息时，才是有效的。,3.算法的基本要素,算法的功能取决于两个方面因素：选用的操作和各个操作之间的顺序一个算法通常由两种基本要素组成,对数据对象的运算和操作,算法的控制结构，即运算或操作间的顺序。,4类基本的运算和操作,算法的控制结构,算法的控制结构是算法中各个操作之间的执行顺序。算法一般由顺序、选择（又称分支）和循环（又称重复）3种基本结构组合而成。描述算法的工具有传统的流程图、N-S结构化流程图和算法描述语言等。,顺序结构流程图,图中A和B两个框是顺序执行的，即在执行完A框所指定的操作后，必然接着执行B框所指定的操作。,顺序结构是最简单的一种基本结构,选择结构流程图,选择结构根据给定的条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框。无论走哪一条路径，在执行完A或B之后，都脱离本选择结构。A或B两个框中可以有一个是空的，即不执行任何操作。,当型（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图当型循环结构直到型循环结构,4.算法基本设计方法,常用的几种算法设计方法有列举法、递推法、递归法、贪婪法、分治法和动态规划法等。,2.1.2算法的复杂度,一个算法的质量可以用算法的复杂度来衡量。算法的复杂度包括算法的时间复杂度和算法的空间复杂度两种。,1算法的时间复杂度,算法的时间复杂度是指执行算法所需要计算工作量。算法执行程序的具体时间和算法的时间复杂度并不是一致的。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是所要解决的问题的规模（通常用整数n表示）的函数算法的工作量=f(n)，其中整数n表示要解决的问题的规模。,算法的时间复杂度举例,第一个程序段如下：x+；s=0在这个程序段中，基本运算“x+”只执行了一次这个程序段的时间复杂度为O(1)。,算法的时间复杂度举例,第二个程序段如下：for（i=1；i=n；i+）x+；s+=x；/*一个简单的for循环，循环体内操作执行了n次*/在这个程序段中，由于有一个循环，所以基本运算“x+”执行了n次。这个程序段的时间复杂度为O(n)。,算法的时间复杂度举例,第三个程序段如下：for（i=1；i=n；i+）for（j=1；j=n；j+）x+；s+=x；/*嵌套的双层for循环，循环体内操作执行了n2次*/在这个程序段中，是一个嵌套的双层循环，所以基本运算“x+”执行了n2次。这个程序段的时间复杂度O(n2)。,2算法的空间复杂度,算法的空间复杂度是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括3部分：输入数据所占的存储空间、程序本身所占的存储空间、算法执行过程中所需要的额外空间。,2.2程序设计方法与风格,程序设计是指设计、编制、调试程序的方法和过程。程序设计并不等同于通常意义上的编程。优先考虑清晰性，效率第二程序的质量主要受到程序设计方法、技术和程序设计风格等因素的影响。本节主要介绍程序设计风格(也可看成程序设计时应遵循的一组规范),程序设计由多个步骤组成，编程只是程序设计整个过程中的一小步。,(1)下列叙述中，不符合良好程序设计风格要求的是(A)A)程序的效率第一，清晰第二B)程序的可读性好C)程序中要有必要的注释D)输入数据前要有提示信息,(2)结构化程序设计主要强调的是(B)A)程序的规模B)程序的易读性C)程序的执行效率D)程序的可移植性,(3)在设计程序时，应采纳的原则之一是(A)A)程序结构应有助于读者理解B)不限制goto语句的使用C)减少或取消注解行D)程序越短越好,程序设计规范,源程序文档化数据说明的方法语句的结构输入和输出,1源程序文档化,源程序文档化是指在源程序中可包含一些内部文档，以帮助阅读和理解源程序。对源程序文档化的过程中，应考虑符号名的命名、程序注释、视觉组织等问题。,命名应具有一定的实际含义,在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。,程序注释,在源程序中添加正确的注释可以帮助理解程序。程序注释可以分为序言行注释和功能性注释。序言性注释位于程序的起始部分，说明整个程序模块的功能。功能性注释一般嵌套在源程序语句内，主要描述相关语句或程序段的功能。,2数据说明的方法,为使程序中的数据说明易于理解和维护，可采用次序应规范化、变量安排有序化和使用注释等数据说明风格。,3语句的结构,为使程序简单易懂，语句构造应该简单直接，每条语句都能直截了当地反映程序员的意图，不能为了提高效率而把语句复杂化。,4输入和输出,设计好的程序能否被用户接受，往往取决于输入和输出的风格。输入和输出的方式和格式应尽量友好，方便用户使用。,2.3结构化程序设计,2.3.1结构化程序设计方法的重要原则2.3.2结构化程序的基本结构与特点2.3.3结构化程序设计的注意事项,2.3.1结构化程序设计方法的重要原则,结构化程序设计方法的重要原则是：自顶向下逐步求精模块化限制使用goto语句,程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。,对复杂问题，应设计一些子目标做过渡，逐步细化。,模块化就是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。,程序中大量使用goto语句，会导致程序结构的混乱，滥用goto语句对程序结构有害，应尽量避免使用。,2.3.2结构化程序的基本结构与特点,1顺序结构,按照程序语句行的先后顺序，一条语句接着一条语句地执行程序。,2选择结构,选择结构又称分支结构,包括简单选择和多分支选择结构,可根据条件，判断应该选择哪一条分支来执行相应的语句序列。,3重复结构,重复结构又称循环结构，可根据给定条件，判断是否需要重复执行某一相同或类似的程序段，该程序段称为循环体;利用重复结构可以大量简化程序行;主要有两类循环结构，它们是当（WHILE）型循环结构和直到（UNTIL）型循环结构。,下面描述中，符合结构化程序设计风格的是(A)A)使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B)模块只有一个入口，可以有多个出口C)注重提高程序的执行效率D)不使用goto语句,(2)结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、_和限制使用goto语句。答：模块化,(3)结构化程序所要求的基本结构不包括(B)A)顺序结构B)GOTO跳转C)选择（分支）结构D)重复（循环）结构,2.3.3结构化程序设计的注意事项,使用程序设计语言中的三种控制结构表示程序的控制逻辑选用的控制结构只允许有一个入口和一个出口复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现语言中所有没有的控制结构，应该采用前后一致的方法来模拟严格控制goto语句的使用。,2.4面向对象的程序设计,2.4.1面向对象方法的基本概念2.4.2面向对象方法的优点,2.4.1面向对象方法的基本概念,1对象（Object）,对象是面向对象方法中最基本的概念，它可以用来表示客观世界中的任何实体。例：书本，课桌，老师，学生等,2类和实例,类是具有共同属性、共同方法的对象的集合，是关于对象的抽象描述，它描述了属于该对象类型的所有对象的性质。例：教师类(类)教师(实例)任何一个具体对象都是该对象所属类的一个具体实例，即一个对象是其对应类的一个实例。,3消息,消息是一个实例与另一个实例之间传递的信息。它统一了数据流和控制流;一个对象通过向另一个对象发送消息来请求其服务;消息只包含传递者的要求，它告诉接受者需要做哪些处理，并不指示接受者怎样去完成这些处理。,4继承,继承是指能够直接获得已有的性质和特征，而不必重复地定义它们。继承具有传递性，如果类Z继承类Y，类Y继承类X，则类Z继承类X。一个类继承它上层的全部基类的特性,5多态性,对象根据所接收的信息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行为，该现象称为多态性。,(1)下面概念中，不属于面向对象方法的是(D)A)对象B)继承C)类D)过程调用,(2)在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送(D)A)调用语句B)命令C)口令D)消息,(3)下面对对象概念描述错误的是(A)A)任何对象都必须有继承性B)对象是属性和方法的封装体C)对象间的通讯靠消息传递D)操作是对象的动态性属性,(4)下列选项中属于面向对象设计方法主要特征的是(A)A)继承B)自顶向下C)模块化D)逐步