算法与程序设计基础

1、第第2 2章章 算法与程序设计基础算法与程序设计基础2.1 2.1 算法算法2.2 2.2 程序设计方法与风格程序设计方法与风格2.3 2.3 结构化程序设计结构化程序设计2.4 2.4 面向对象的程序设计面向对象的程序设计2.5 2.5 小结小结2.1 2.1 算法算法2.2.1 2.2.1 算法的基本概念算法的基本概念2.2.2 2.2.2 算法的复杂度算法的复杂度 2.1.1 2.1.1 算法的基本概念算法的基本概念1 1算法的定义算法的定义 是指对解题方案的准确而完整的描述，即解决问题的操作步骤。 算法数学上的，也。 在用计算机，往往，再用具体的程序设计语言描述此算法（即）。 在编程时

2、，由于要受到计算机系统运行环境的限制，。2 2算法的基本特征算法的基本特征v 可行性可行性v 确定性确定性v 有穷性有穷性 v 拥有足够的情报拥有足够的情报 3. 3. 算法的基本要素算法的基本要素v算法的功能取决于两个方面因素：v 和v一个算法通常由组成 ，即运算或操作间的顺序。，即运算或操作间的顺序。+ +、2+32+3、8 82 2 与（）、或（与（）、或（| | |）、）、非（！）非（！）！1 1、1| |01| |0、1&11&1 、 bab、a=ca=c、bcbc赋值、输入、输出赋值、输入、输出A=0A=0、b=3b=3算法的控制结构算法的控制结构 v算法的控制结构是算法中。一般、

3、（又称分支）和（又称重复）。有、和等。 A B图中图中A A和和B B两个框是顺序执行的，两个框是顺序执行的，即在执行完即在执行完A A框所指定的操作后，框所指定的操作后，必然接着执行必然接着执行B B框所指定的操作。框所指定的操作。v 选择结构根据给定的条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框。v 无论走哪一条路径，在执行完A或B之后，都脱离本选择结构。A或B两个框中可以有一个是空的，即不执行任何操作 。ABPPA 当型循环结构的功能是当给当型循环结构的功能是当给定的条件定的条件P成立时，执行成立时，执行A框操作，执行完框操作

4、，执行完A后，再判后，再判断条件断条件P是否成立，如果仍是否成立，如果仍然成立，再执行然成立，再执行A框，如此框，如此反复执行反复执行A框，直到某一次框，直到某一次P条件不成立为止，此时不条件不成立为止，此时不执行执行A框，脱离本循环结构框，脱离本循环结构 直到型循环结构的功能是先直到型循环结构的功能是先执行执行A框，然后判断给定的框，然后判断给定的P条件是否成立，如果条件是否成立，如果P条条件不成立，则再执行件不成立，则再执行A，然，然后再对后再对P条件进行判断，如条件进行判断，如果果P条件仍然不成立，又执条件仍然不成立，又执行行A，如此反复执行，如此反复执行A，直，直到给定的到给定的P条件

5、成立为止，条件成立为止，此时不再执行此时不再执行A，脱离本循，脱离本循环结构。环结构。 v顺序结构的顺序结构的N-S图图 v选择结构的选择结构的N-S图图v当型循环结构当型循环结构 v直到型循环结构直到型循环结构 P成立 不成立 A B 当p成立 A A 直到p成立4.4.算法基本设计方法算法基本设计方法 常用的几种算法设计方法有、和等。v一个的可以的。算法的和算法的两种。1 1算法的时间复杂度算法的时间复杂度度是指。v 算法执行程序的算法的。，而算法所执行的基本运算次数是所要解决的问题的规模（通常用整数n表示）的函数v算法的工作量 = f (n) ，其中整数n表示要解决的问题的规模。 v在这

6、个程序段中，基本运算“x+”只这个程序段的为 。 /* 一个简单的for循环，循环体内操作执行了n次 */v在这个程序段中，由于有一个循环，所以基本运算“x+”。这个程序段的为。 / /* * 嵌套的双层嵌套的双层forfor循环，循环体内操作执行了循环，循环体内操作执行了n n2 2次次 * */ /v在这个程序段中，是一个嵌套的双层循环，所以基本在这个程序段中，是一个嵌套的双层循环，所以基本运算运算“x+”x+”。这个程序段的时间复杂度这个程序段的时间复杂度。2 2算法的空间复杂度算法的空间复杂度是指这个。v算法执行期间所需要的存储空间包括3部分： 的存储空间、 的存储空间、 所需要的额外

7、空间。是指、的。v程序设计通常意义上的。v v 主要程序、和程序等因素的。v本节主要介绍程序设计风格(也可看成程序设计时应遵循的一组规范) (1) (1) 下列叙述中，不符合良好程序设计风格要求的是下列叙述中，不符合良好程序设计风格要求的是 ( (A A) ) A) A) 程序的效率第一，清晰第二程序的效率第一，清晰第二 B) B) 程序的可读性好程序的可读性好 C) C) 程序中要有必要的注释程序中要有必要的注释 D) D) 输入数据前要有提示信息输入数据前要有提示信息(2) (2) 结构化程序设计主要强调的是结构化程序设计主要强调的是 ( (B B) ) A) A) 程序的规模程序的规模

8、B) B) 程序的易读性程序的易读性 C) C) 程序的执行效率程序的执行效率 D) D) 程序的可移植性程序的可移植性(3) (3) 在设计程序时，应采纳的原则之一是在设计程序时，应采纳的原则之一是 ( (A A) ) A) A) 程序结构应有助于读者理解程序结构应有助于读者理解 B) B) 不限制不限制gotogoto语句的使用语句的使用 C) C) 减少或取消注解行减少或取消注解行 D) D) 程序越短越好程序越短越好v 源程序文档化源程序文档化 v 数据说明的方法数据说明的方法v 语句的结构语句的结构v 输入和输出输入和输出1 1源程序文档化源程序文档化是指在源程序中可包含一些，以。v

9、对源程序文档化的过程中，应考虑 、问题。程序注释程序注释v在源程序中添加正确的注释。v程序可以和。程序的，。一般语句，主要。 为使程序中的，可采用次序应规范化、变量安排有序化和使用注释等数据说明风格。 为使程序简单易懂，应该，每条语句都能直截了当地反映程序员的意图，不能为了提高效率而把语句复杂化。 设计好的程序能否被用户接受，往往取决于输入和 输出的风格。输入和输出的方式和格式应，。 使用程序设计语言中的三种控制结构表示程序的控使用程序设计语言中的三种控制结构表示程序的控制制逻辑逻辑 选用的控制结构只允许有一个入口和一个出口选用的控制结构只允许有一个入口和一个出口 复杂结构应该用嵌套的基本控制

10、结构进行组合嵌套来复杂结构应该用嵌套的基本控制结构进行组合嵌套来 实现实现 语言中所有没有的控制结构，应该采用前后一致的方语言中所有没有的控制结构，应该采用前后一致的方 法来模拟法来模拟 严格控制严格控制gotogoto语句的使用。语句的使用。 2.4.1 2.4.1 面向对象方法的基本概念面向对象方法的基本概念2.4.2 2.4.2 面向对象方法的优点面向对象方法的优点2.4.1 2.4.1 面向对象方法的基本概念面向对象方法的基本概念是面向对象方法中最基本的概念，它可以用来表示的。v例：书本，课桌，老师，学生等 2 2类和实例类和实例 是，是关于 对象的抽象描述，它描述了属于该对象类型的所

11、有对 象的性质。 例：教师类(类) 教师(实例) 任何一个具体对象都是该对象所属类的一个具体实例，即一个对象是其对应类的一个实例。 3 3消息消息是一个实例与另一个实例之间传递的信息。v它统一了数据流和控制流;v一个对象通过向另一个对象发送消息来请求其服务;v消息只包含传递者的要求，它告诉接受者需要做哪些处理，并不指示接受者怎样去完成这些处理。4 4继承继承是指能够直接获得已有的性质和特征，而不必重 复地定义它们。 ， 如果类Z继承类Y，类Y继承类X，则类Z继承类X。 一个类继承它上层的全部基类的特性5 5多态性多态性 对象根据所接收的信息而做出动作，该现象称为多态性。v 与人类习惯的思维方法一致与人类习惯的思维方法一致v 稳定性好稳定性好v 可重用性好可重用性好v 易于开发大型软件产品易于