第6章 程序设计与算法 计算机应用基础 数学与计算机工程学院.

Presentation on theme: "第6章 程序设计与算法 计算机应用基础 数学与计算机工程学院."— Presentation transcript:

1 第6章 程序设计与算法 计算机应用基础 数学与计算机工程学院

2 5.1 程序设计概述 1 .计算机语言的产生和发展 程序设计是一门技术，甚至更是一门艺术。程序设计方法与技术的发展经历了结构化程序设计和面向对象程序设计两个阶段。 计算机语言是指用于人与计算机之间通讯的语言，它是人与计算机之间传递信息的媒介。 计算机语言可以分成机器语言，汇编语言，高级语言三大类。

3 5.1 程序设计概述 1．机器语言 机器语言通常是指一台计算机全部的指令集合。 机器语言由计算机中所有二进制指令构成。
在一种计算机上执行的机器语言程序，想要移植到另一种计算机上执行，几乎是不可能的。也就是说，机器语言因机器而异。 利用机器语言编写的计算机程序可以直接在计算机上运行，其运行效率是所有语言中最高的。机器语言是第一代计算机语言。

4 5.1 程序设计概述 2．汇编语言 汇编语言是一种符号化了的机器语言，它用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串。
需要一种专门的程序，将汇编语言中的符号翻译成二进制机器指令，这种翻译程序被称为汇编程序。 和机器语言一样，汇编语言同样依赖于机器硬件，移植性不好，但效率仍十分高。 计算机机器语言与汇编语言统称为低级语言。

5 5.1 程序设计概述 3.高级语言 高级语言是一种接近于数学语言或人类的自然语言的计算机语言，同时不依赖于计算机硬件。
发展经历了从早期语言到结构化程序设计语言，从高级语言的下一个发展目标是面向应用。 编写的程序有很好的可读性和可移植性，程序运行效率较低。 编写的源程序必须经过“翻译”才能在计算机上运行。高级语言源程序“翻译”的方法主要有解释和编译两种，其区别在于是否形成“目标程序”。

6 5.1 程序设计概述 2 .程序设计风格与方法 程序设计是计算机工作者一成不变的传统工作，编写好的计算机程序不仅要有良好的程序设计思想、方法和技术之外，程序设计风格也是很重要的。良好的程序设计风格可以使程序结构合理并且源程序代码易于维护。

7 5.1 程序设计概述 1．程序设计风格 程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。
对程序进行阅读和跟踪，程序设计总的风格是简单和清晰，任何计算机程序首先必须是可以读懂和理解的。这就是著名的“清晰第一，效率第二”。 要养成良好的程序设计风格，需要考虑下面一些因素。

8 5.1 程序设计概述 （1）源程序的文档化 （2）数据说明的方法 （3）语句的结构 （4）输入与输出
源程序文档化是指在源程序中必须包含一些内部文档，以帮助阅读和理解源程序。 比如： ① 符号名的命名规则② 程序注释③ 视觉组织 （2）数据说明的方法 比如： ① 数据说明的次序规范化。 ②说明语句中的变量安排有序。 ③合理利用注释 （3）语句的结构 （4）输入与输出

9 5.1 程序设计概述 2．结构化程序设计 （1）设计的原则 （2）基本结构与特点 自顶向下、逐步求精、模块化及限制使用goto语句。
结构化程序主要有三种结构： 顺序结构、选择结构、重复/循环结构

10 5.1 程序设计概述 图 5-2 选择结构 图 5-1顺序结构

11 5.1 程序设计概述 图5-3 当型循环与直到型循环

12 5.1 程序设计概述 3．面向对象程序设计 （1）面向对象的程序设计简介 （2）面向对象的基本概念 ① 对象
对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。 面向对象的程序设计方法中的对象是属性和方法的封装体。 一个对象由对象名、属性和操作3部分组成。 对象的基本特点是标识唯一性、分类性、多态性、封装性、模块独立性好。

13 5.1 程序设计概述 ④ 消息 ⑤ 继承 ⑥ 多态性 ② 类 ③ 封装性 指从外面看只能看到对象的外部特性，即只需知道数据的取值
范围和可以对该数据施加的操作，根本无需知道数据的具体结构 以及实现操作的算法。 ④ 消息 消息是一个实例与另一个实例之间传递的信息。 ⑤ 继承 ⑥ 多态性 多态性是指同样的消息被不同的对象接受时可导致完全不同的行为的现 象。

14 5.2 算法概述 1 .算法的定义和特征 算法（Algorithm）是指解题方案的准确而完整的描述，是一组严谨地定义运算顺序的指令的有序序列，并且每一个指令都是有效的、明确的，此序列被执行有限的次数后终止。 2 .算法的基本特征 算法应具有以下5个基本特征。 ① 可行性：② 确定性③ 有穷性④ 有限的输入（足够的信息）⑤ 有限的输出

15 5.2 算法概述 3 .算法设计的要求 4 .算法的基本要素 通常，一个算法由两种基本要素组成。 ① 对数据对象的运算和操作。
5.2 算法概述 3 .算法设计的要求 ① 正确性：算法应当满足具体问题的需求，是正确的，不含数据、语法错误。 ② 可读性：算法要易于理解，易于编码，易于调试。 ③ 健壮性：当输入非法数据时，算法能做出适当的反映或进行处理。 ④ 时间与空间效率：算法的执行时间要短，占用的存储空间要小。 4 .算法的基本要素 通常，一个算法由两种基本要素组成。 ① 对数据对象的运算和操作。 ② 算法的控制结构，即运算或操作时间的顺序。

16 5.2 算法概述 算法的复杂度 解决同一问题可以使用很多不同的算法，评价一个算法优劣的主要标准是算法的执行效率与存储需求，分别由算法的时间复杂度和空间复杂度来衡量。 算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。

17 5.2 算法概述 2 算法的复杂度（空间+时间=效率） 算法时间复杂度
5.2 算法概述 2 算法的复杂度（空间+时间=效率） 算法时间复杂度 算法的时间复杂度是指：执行算法所需要的计算工作量。可以用算法中基本语句的执行次数来度量。 算法空间复杂度 算法的空间复杂度是指：执行这个算法所需要的内存空间。

18 5.2 算法概述 典型算法实例 插入排序 插入排序的基本思想就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序序列。 插入排序是这样实现的： （1） 从第一个元素开始，该元素可以认为已经被排序 （2） 取出下一个元素，在已经排序的元素序列中从后向前扫描 （3） 如果该元素（已排序）大于新元素，将该元素移到下一位置 （4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 （5） 将新元素插入到下一位置中 （6） 重复步骤2

19 5.2 算法概述 例如：初始数列： [ ] 第一趟排序后： 38 49[ ] 第二趟排序后： [ ] 第三趟排序后 ： [ ] 第四趟排序后 ： [ ] 第五趟排序后 ： [27 49] 第六趟排序后 ： [49] 第七趟排序后 ： [] 最后排序结果 ：

20 5.2 算法概述 2．冒泡排序 冒泡排序（BubbleSort）的基本思想是：在排序过程中总是小数（或大数）往前放，大数（或小数）往后放，相当于气泡往上升，所以称作冒泡排序。 冒泡排序的实现过程：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。 在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。 如此下去，重复以上过程，直至最终完成排序。

21 5.2 算法概述 例如：初始数列： [ ] 第一趟排序后 ： [97] 第二趟排序后： [76 97] 第三趟排序后 ： [ ] 第四趟排序后 ： [ ] 第五趟排序后 ： [ ] 第六趟排序后 ：13 27 [ ] 第七趟排序后 ：13 [ ] 最后排序结果 ：[ ]

22 5.2 算法概述 3．选择排序 选择排序的基本思想是：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 例如：初始数列： [ ] 　　第一趟排序后 ：13 [ ] 　　第二趟排序后： [ ] 　　第三趟排序后 ： [ ] 　　第四趟排序后 ： [ ] 　　第五趟排序后 ： [ ] 　　第六趟排序后 ： [97 76] 　　第七趟排序后 ： [97] 　　最后排序结果 ：[ ]

23 5.2 算法概述 实例二：求最大值算法 有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为“捡豆子”。 求最大数的算法是： （1）首先将第一颗豆子放入口袋中。 （2）从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。直到最后一颗豆子。 （3）最后口袋中的豆子就是所有的豆子中最大的一颗。

24 5.2 算法概述 例如：数列为：[ ] 第一次“捡豆子”后：49 [ ] 第二次“捡豆子”后：49 [ ] 第三次“捡豆子”后：65 [ ] 第四次“捡豆子”后：97 [ ] 第五次“捡豆子”后：97 [ ] 第六次“捡豆子”后：97 [27 49] 第七次“捡豆子”后：97 [49] 最后结果：97

25 5.2 算法概述 实例三：求最大公约数算法 求最大公约数是数学中经常讨论的问题，两个自然数的最大公约数的算法是：
5.2 算法概述 实例三：求最大公约数算法 求最大公约数是数学中经常讨论的问题，两个自然数的最大公约数的算法是： 求两个自然数的最大公约数 设两个变量M和N （1）如果M < N，则交换M和N （2）M被N除，得到余数R （3）判断R＝0，正确则N即为“最大公约数”，否则下一步 （4）将N赋值给M，将R赋值给N，重做第一步。

26 5.2 算法概述 例如：求24与18的最大公约数 （1）因为24（M） <18（N）不成立，不交换，否则要交换24（M）和18（N）
5.2 算法概述 例如：求24与18的最大公约数 （1）因为24（M） <18（N）不成立，不交换，否则要交换24（M）和18（N） （2）24（M）被18（N）除，得到余数R=6 （3）判断R＝0不成立，将18（N）赋值给M，将6（R）赋值给N，即18（M） 6（N） （4）18（M）被6（N）除，得余数R=0 （5）6（N）为最大公约数