计算机学科导论课件：第6章 问题求解与程序设计

1、计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 3 部分部分 程序设计程序设计程序设计在计算机系统的位置程序设计在计算机系统的位置 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计本章讨论的主要问题是：本章讨论的主要问题是： 1. 什么是程序？什么是程序设计？什么是程序设计语言？什么是程序？什么是程序设计？什么是程序设计语言？ 2. 程序是怎么设计出来的？程序设计的关键是什么？程序是怎么设计出来的？程序设计的关键是什么？ 3. 计算机运行程序的过程就是对数据的加工处理过程，如计算机运行

2、程序的过程就是对数据的加工处理过程，如何将数据存储到计算机的内存中？如何描述问题的处理方法何将数据存储到计算机的内存中？如何描述问题的处理方法和具体步骤才能让计算机和具体步骤才能让计算机“看懂看懂”呢？呢？ 4. 为了方便编写程序，现代程序设计普遍采用高级程序设为了方便编写程序，现代程序设计普遍采用高级程序设计语言，高级语言程序如何转换为等价的机器指令？计语言，高级语言程序如何转换为等价的机器指令？计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社情景问题情景问题七桥问题七桥问题 【问题问题】17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里世纪的东普鲁士有一座哥尼斯堡城（

3、现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区岛区4个区域，全城共有七座桥将个区域，全城共有七座桥将4个城区连接起来，于是，个城区连接起来，于是，产生了一个有趣的问题：一个人是否能在一次步行中穿越全产生了一个有趣的问题：一个人是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次。部的七座桥后回到起点，且每座桥只经过一次。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社情景问题情景问题

4、七桥问题七桥问题 东区东区北区北区岛区岛区南区南区CADB 抽象抽象【想法想法抽象模型抽象模型】可以用】可以用A、B、C、D表示表示4个城区，用个城区，用 7 条线表示条线表示 7 座桥，将七桥问题抽象为一个图模型。座桥，将七桥问题抽象为一个图模型。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社情景问题情景问题七桥问题七桥问题 【想法想法基本思路基本思路】是否存在欧拉回路的判定规则是：】是否存在欧拉回路的判定规则是：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之

5、一出）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；发，找到欧拉回路；（3）如果没有一个地方通奇数桥，则无论从哪里出发，都能）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。找到欧拉回路。 由上述判定规则得到求解七桥问题的基本思路：依次计算由上述判定规则得到求解七桥问题的基本思路：依次计算图中与每个节点相关联的边的个数（称为节点的度），根据图中与每个节点相关联的边的个数（称为节点的度），根据度为奇数的节点个数判定是否存在欧拉回路。度为奇数的节点个数判定是否存在欧拉回路。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社情景问题情景问题

6、七桥问题七桥问题 n【数据表示数据表示数据结构数据结构】设邻接矩阵设邻接矩阵arcnn存储图。存储图。n【数据处理数据处理算法算法】算法用伪代码描算法用伪代码描述如下：述如下： 1. 通奇数桥的顶点个数通奇数桥的顶点个数count初始化为初始化为0； 2. 下标下标 i 从从0 n 1重复执行下述操作：重复执行下述操作： 2.1 计算矩阵计算矩阵arcnn第第i行元素之和行元素之和degree; 2.2 如果如果degree为奇数，则为奇数，则count+; 3. 如果如果count等于等于0或或2，则存在欧拉回路；否则不存在，则存在欧拉回路；否则不存在欧拉回路；欧拉回路；0 1 2 21 0

7、 1 12 1 0 02 1 0 0ABCDA B C D计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社情景问题情景问题七桥问题七桥问题 【程序实现程序实现】以下是用】以下是用C语言编写的程序：语言编写的程序： int EulerCircuit(int mat1010, int n) /函数定义，二维数组作为形参函数定义，二维数组作为形参 int i, j, count = 0, degree; /count累计通奇数桥的节点个数累计通奇数桥的节点个数 for (i = 0; i n; i+) /依次累加每一行的元素依次累加每一行的元素 degree = 0; /

8、degree存储通过节点存储通过节点i的桥数，初始化为的桥数，初始化为0 for (j = 0; j n; j+) /依次处理每一列的元素依次处理每一列的元素 degree = degree + matij; /将通过节点将通过节点i的桥数求和的桥数求和 if (degree % 2 != 0) /桥数为奇数桥数为奇数 count+; return count; /结束函数，并将结束函数，并将count返回到调用处返回到调用处 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社问问 题题算算 法法程程 序序想想 法法抽象模型抽象模型基本思路基本思路数据表示数据表示数据处

9、理数据处理程序语言程序语言设计方法设计方法编程环境编程环境人（设计方案）人（设计方案）计算机计算机(执行方案执行方案)第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计程序设计的一般过程程序设计的一般过程 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社为问题建立模型，为问题建立模型，抽象化、模型化抽象化、模型化将算法转换程序，将算法转换程序，掌握程序语言、熟掌握程序语言、熟悉编程环境，悉编程环境，设计解决方案，设计解决方案，需要数据结构和需要数据结构和算法的知识。算法的知识。问问 题题算算 法法程程 序序想想 法法第第 6 章章 问题求解与程序设计

10、问题求解与程序设计程序设计程序设计程序设计的一般过程程序设计的一般过程 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社理解程序理解程序第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计n 计算机是一个大容量、高速运转、但是没有思维的机器。计算机是一个大容量、高速运转、但是没有思维的机器。n 计算机只认识计算机只认识 0 和和 1，听不懂人说的话，听不懂人说的话计算机如何接计算机如何接收人的指令？收人的指令？有问题需要解有问题需要解决的人决的人可以解决问题可以解决问题的计算机的计算机Hello计算机学科概论（第计算机学科概论（第2版）版）清华大学出版

11、社清华大学出版社理解程序理解程序如何实现人和计算机的交流？如何实现人和计算机的交流？第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计n 计算机是一个大容量、高速运转、但是没有思维的机器。计算机是一个大容量、高速运转、但是没有思维的机器。n 计算机输出了计算机输出了 0 和和 1 的编码，可是人看不懂的编码，可是人看不懂如何解释如何解释计算机的运算结果？计算机的运算结果？有问题需要解有问题需要解决的人决的人可以解决问题可以解决问题的计算机的计算机0101000110计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社理解程序理解程序第第 6 章章 问题求

12、解与程序设计问题求解与程序设计程序设计程序设计有 问 题 需 要 解有 问 题 需 要 解决的人决的人可以解决问题的可以解决问题的计算机计算机程序是跨越这条鸿沟的桥梁，人要和计算机有效地交流，程序是跨越这条鸿沟的桥梁，人要和计算机有效地交流，必须通过程序。必须通过程序。 程序程序计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社n 程序：程序：是能够实现特定功能的一组是能够实现特定功能的一组指令指令序列的集合，是序列的集合，是描述对某一问题的解决步骤。其中，指令可以是描述对某一问题的解决步骤。其中，指令可以是机器指令机器指令、汇编语言汇编语言的语句，也可以是的语句，也可

13、以是高级语言高级语言的语句，甚至还可以的语句，甚至还可以是用是用自然语言自然语言描述的指令。描述的指令。n 用高级语言编写的程序称为用高级语言编写的程序称为源程序源程序；用机器语言（或汇；用机器语言（或汇编语言）编写的程序称为编语言）编写的程序称为目标程序目标程序；由二进制代码表示的；由二进制代码表示的程序称为程序称为机器代码机器代码。n 程序设计：程序设计：是给出解决特定问题的程序的过程，是软件是给出解决特定问题的程序的过程，是软件构造活动中的重要组成部分，程序设计往往以构造活动中的重要组成部分，程序设计往往以某种程序设某种程序设计语言为工具计语言为工具，给出这种语言下的程序。，给出这种语言

14、下的程序。n 专业的程序设计人员常被称为专业的程序设计人员常被称为程序员程序员。 第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的关键程序设计的关键 第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计n 程序设计的关键是数据表示和数据处理。程序设计的关键是数据表示和数据处理。n 数据表示数据表示完成的任务是从问题抽象出数据模型，并将该模完成的任务是从问题抽象出数据模型，并将该模型从机外表示转换为机内表示；型从机外表示转换为机内表示；n 数据处理数据处理完成的任务是对问题的求

15、解方法进行抽象描述，完成的任务是对问题的求解方法进行抽象描述，即设计算法，再将算法的指令转换为某种程序设计语言对应即设计算法，再将算法的指令转换为某种程序设计语言对应的语句，转换所依据的规则就是某种程序设计语言的语法。的语句，转换所依据的规则就是某种程序设计语言的语法。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的关键程序设计的关键 第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计n 计算机能够求解的问题一般可以分为数值问题和非数值问计算机能够求解的问题一般可以分为数值问题和非数值问题，题，数值问题数值问题抽象出的数据模型通常是抽象出的

16、数据模型通常是数学方程数学方程，非数值问非数值问题题抽象出的数据模型通常是线性表、树、图等抽象出的数据模型通常是线性表、树、图等数据结构数据结构。n 存储程序存储程序意味着需要将抽象出的数据模型从意味着需要将抽象出的数据模型从机外表示机外表示转换转换为为机内表示机内表示，也就是将数据模型存储到计算机的内存中，典，也就是将数据模型存储到计算机的内存中，典型方法就是用程序设计语言描述数据模型。型方法就是用程序设计语言描述数据模型。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的关键程序设计的关键 第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序

17、设计n 问题的解决方案最终需要借助程序设计语言来表示，也就问题的解决方案最终需要借助程序设计语言来表示，也就是将算法转换为程序，只有在计算机上能够运行良好的程序是将算法转换为程序，只有在计算机上能够运行良好的程序才能为人们解决特定的实际问题。才能为人们解决特定的实际问题。n 数据处理的核心是数据处理的核心是算法设计算法设计，一般来说，对不同求解方法，一般来说，对不同求解方法的抽象描述产生了相应的不同算法，不同的算法将设计出不的抽象描述产生了相应的不同算法，不同的算法将设计出不同的程序。同的程序。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解

18、与程序设计问题求解与程序设计数据结构数据结构n 数据数据：所有能输入到计算机中并能被计算机程序识别和处：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。包括数值、字符、图形、图像、声音等。理的符号集合。包括数值、字符、图形、图像、声音等。n 数据元素数据元素：数据的基本单位，在计算机程序中通常作为一：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。个整体进行考虑和处理。n 数据结构数据结构：相互之间存在一定关系的数据元素的集合，通：相互之间存在一定关系的数据元素的集合，通常，数据元素之间具有以下三种基本关系：常，数据元素之间具有以下三种基本关系：（1）一对一的线性关系：

19、线性结构；）一对一的线性关系：线性结构；（2）一对多的层次关系：树结构；）一对多的层次关系：树结构；（3）多对多的任意关系：图结构。）多对多的任意关系：图结构。数据结构的基本概念数据结构的基本概念 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构例例6.1 为学籍管理问题抽象数据模型。为学籍管理问题抽象数据模型。数据结构的基本概念数据结构的基本概念 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构例例6.2

20、为人机对弈问题抽象数据模型。为人机对弈问题抽象数据模型。数据结构的基本概念数据结构的基本概念 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构例例6.3 为七巧板涂色问题抽象数据模型。为七巧板涂色问题抽象数据模型。数据结构的基本概念数据结构的基本概念 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社n 为现实世界的问题建立数据模型后，还要将该模型存储为现实世界的问题建立数据模型后，还要将该模型存储在计算机的内存中，即将数据从机外表示转换为机内表示。在计算机的内存中，即将数据从

21、机外表示转换为机内表示。n 通常有两种存储表示方法：顺序存储和链接存储。通常有两种存储表示方法：顺序存储和链接存储。n 顺序存储的基本思想顺序存储的基本思想是：用一组是：用一组连续连续的存储单元的存储单元依次依次存存储数据元素，数据元素之间的逻辑关系由元素的储数据元素，数据元素之间的逻辑关系由元素的存储位置存储位置来表示；来表示；n 链接存储的基本思想链接存储的基本思想是：用一组是：用一组任意的任意的存储单元存储数存储单元存储数据元素，数据元素之间的逻辑关系用据元素，数据元素之间的逻辑关系用指针指针来表示。来表示。 第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存

22、储结构 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存储结构 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存储结构 ABCDEFGHIJ计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社算法的定义算法的定义第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法n 算法算法（Algorithm）:对对特定问题特定问题求解步骤的一种描述，求解步骤的一种描述，是

23、是指令指令的的有限序列有限序列。n 算法的五大特性：算法的五大特性： 输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。 输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。且每一步都在有穷时间内完成。 确定性确定性：算法中的每一条指令必须有确切的含义，对：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。于相同的输入只能得到相同的输出。 可行性可行性：算法描述的操作可以通过已经实现的基本操：算法描述的操作可以通过已经实现的基本

24、操作执行有限次来实现。作执行有限次来实现。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社算法的定义算法的定义第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法n 算法算法（Algorithm）:对对特定问题特定问题求解步骤的一种描述，求解步骤的一种描述，是是指令指令的的有限序列有限序列。操作步骤操作步骤（有穷性、确定性、可行性）（有穷性、确定性、可行性） 1. 2. 3. 输 入输 入计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算法第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法n 算法的设计者在构思和

25、设计了一个算法之后，必须清楚算法的设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即准确地将所设计的求解步骤记录下来，即描述算法描述算法。通常。通常用伪代码来描述算法。用伪代码来描述算法。n 伪代码伪代码是介于自然语言和程序设计语言之间的方法，保是介于自然语言和程序设计语言之间的方法，保留了程序设计语言严谨的结构、语句的形式和控制成分，留了程序设计语言严谨的结构、语句的形式和控制成分，忽略了繁琐的变量说明，在抽象地描述算法时一些处理和忽略了繁琐的变量说明，在抽象地描述算法时一些处理和条件允许使用自然语言来表达。至于算法中自然语言的成条件允许使用自然语言来表达。至于算

26、法中自然语言的成份有多少，取决于算法的份有多少，取决于算法的抽象级别抽象级别。n 由于伪代码书写方便、格式紧凑、容易理解和修改，因由于伪代码书写方便、格式紧凑、容易理解和修改，因此被称为此被称为算法语言算法语言。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算法第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法例例6.4 设计算法，在含有设计算法，在含有n个元素的集合中查找最大值元素。个元素的集合中查找最大值元素。解：设最大值为解：设最大值为max，可以假定第，可以假定第1个元素为最大值元素，依个元素为最大值元素，依次将第次将第2、3、n个元素

27、与个元素与max比较，比较，max中保存的始终是中保存的始终是每次比较后的最大值元素，算法用伪代码描述如下：每次比较后的最大值元素，算法用伪代码描述如下： step1: max 第第1个元素；个元素； step2: 初始化被比较元素的序号初始化被比较元素的序号i 2； step3: 当当i小于等于小于等于n时重复执行下述操作：时重复执行下述操作： step3.1: 如果第如果第i个元素大于个元素大于max，则，则max 第第i个元素；个元素； step3.2: i i + 1；step4: 输出输出max；计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算

28、法第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法例例6.5 设计算法，实现欧几里德算法。设计算法，实现欧几里德算法。解：设两个自然数是解：设两个自然数是m和和n并满足并满足mn，欧几里德算法的基本，欧几里德算法的基本思想是将思想是将m和和n辗转相除直到余数为辗转相除直到余数为0。例如，。例如，m = 35，n = 25，m除以除以n的余数用的余数用r表示，计算过程如下：表示，计算过程如下：当余数当余数r为为0时，被除数时，被除数n就是就是m和和n的最大公约数。的最大公约数。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算法第第 6 章章

29、问题求解与程序设计问题求解与程序设计算法算法例例6.5 设计算法，实现欧几里德算法。设计算法，实现欧几里德算法。 step1: r m mod n; step2: 循环直到循环直到r等于等于0 step2.1: m n; step2.2: n r; step2.3: r m mod n; step3: 输出输出n;计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社算法分析：对算法所需要的计算机资源进行估算。算法分析：对算法所需要的计算机资源进行估算。时间复杂度（时间复杂度（Time Complexity）空间复杂度（空间复杂度（Space Complexity）n撇开与

30、计算机软硬件有关的因素，影响算法时间代价的最撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是主要因素是问题规模问题规模。n问题规模问题规模：输入量的多少，一般来说，它可以从问题描述：输入量的多少，一般来说，它可以从问题描述中得到。例如，找出中得到。例如，找出100以内的所有素数，问题规模是以内的所有素数，问题规模是100。n一个显而易见的事实是：几乎所有的算法，对于规模更大一个显而易见的事实是：几乎所有的算法，对于规模更大的输入需要运行更长的时间。例如，找出的输入需要运行更长的时间。例如，找出10 000以内的所有以内的所有素数比找出素数比找出100以内的所有素数需要更多的时间。所

31、以运行以内的所有素数需要更多的时间。所以运行算法所需要的时间算法所需要的时间 T 是问题规模是问题规模n的函数，记作的函数，记作T(n)。算法分析算法分析第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社n为了客观地反映一个算法的执行时间，可以用算法中为了客观地反映一个算法的执行时间，可以用算法中基本基本语句语句的执行次数来度量算法的工作量。的执行次数来度量算法的工作量。n基本语句基本语句：执行次数与整个算法的执行次数成正比的操作：执行次数与整个算法的执行次数成正比的操作指令。指令。n基本语句对算法运行时间的贡

32、献最大，是算法中最重要的基本语句对算法运行时间的贡献最大，是算法中最重要的操作。操作。n分析算法的时间复杂度的基本方法是：找出所有语句中执分析算法的时间复杂度的基本方法是：找出所有语句中执行次数最多的那条语句作为行次数最多的那条语句作为基本语句基本语句，计算基本语句的，计算基本语句的执行执行次数次数，取其，取其数量级数量级放入大放入大中即可。中即可。n这种衡量效率的方法得出的不是时间量，而是一种增长趋这种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。势的度量。算法分析算法分析第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法计算机学科概论（第计算机学科概论（第2版）版）清华

33、大学出版社清华大学出版社算法分析算法分析第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法例例6.6 分析下列算法的时间复杂度。分析下列算法的时间复杂度。解：基本语句是解：基本语句是step3.1的比较语句，即第的比较语句，即第 i 个元素是否大个元素是否大于于max，该语句需要重复执行，该语句需要重复执行n 1次，因此，算法的时间复次，因此，算法的时间复杂度是杂度是O(n)。 step1: max 第第1个元素；个元素； step2: 初始化被比较元素的序号初始化被比较元素的序号i 2； step3: 当当i小于等于小于等于n时重复执行下述操作：时重复执行下述操作： step3.1

34、: 如果第如果第i个元素大于个元素大于max，则，则max 第第i个元素；个元素； step3.2: i i + 1；step4: 输出输出max；计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第一代程序设计语言（第一代程序设计语言（1GL

35、）机器语言机器语言 如果不小心弄错了一如果不小心弄错了一个二进制位，该如何个二进制位，该如何找出来？找出来？计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第二代程序设计语言（第二代程序设计语言（2GL）汇编语言汇编语言 例如，例如，ADD表

36、示机器表示机器指令指令00000100。相对于。相对于机器语言，汇编语言简机器语言，汇编语言简化了程序编写，而且不化了程序编写，而且不容易出错容易出错计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第三代程序设计语言（第三代程序设计语言（3G

37、L）高级语言高级语言 n 高级语言高级语言：高级程序设计语言，相应地，机器语言和汇编：高级程序设计语言，相应地，机器语言和汇编语言称为语言称为低级语言低级语言，低级意味着要求程序员从机器的层次上，低级意味着要求程序员从机器的层次上考虑问题。考虑问题。n 结构化程序设计语言结构化程序设计语言： BASIC 、 PASCAL、C等。等。n 面向对象程序设计语言面向对象程序设计语言：Java、C+、C#等。等。n 可视化程序设计语言可视化程序设计语言：VB、Delphi、Visual C+等。等。n 网络程序设计语言网络程序设计语言：ASP、PHP和和JSP等。等。计算机学科概论（第计算机学科概论（

38、第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第四代程序设计语言（第四代程序设计语言（4GL）非过程式语言非过程式语言 n 利用利用4GL开发软件只需要考虑开发软件只需要考虑“做什么做什么”而不必考虑而不必考虑“如如何做何做”，不涉及太多的算法细节，从而大大提高软件生产率。

39、，不涉及太多的算法细节，从而大大提高软件生产率。n 到目前为止，使用最广泛的到目前为止，使用最广泛的4GL是数据库查询语言，许多是数据库查询语言，许多大型数据库语言如大型数据库语言如Oracle、Sybase、Informix等都包含有等都包含有4GL成分。成分。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动

40、力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第五代程序设计语言（第五代程序设计语言（5GL）知识型语言知识型语言 n 5GL主要应用在人工智能研究上，典型代表是主要应用在人工智能研究上，典型代表是LISP语言和语言和PROLOG语言。语言。n 目前，目前，4GL和和5GL的发展都不是很成熟，在效率、应用等的发展都不是很成熟，在效率、应用等方面都存在诸多问题，常用的程序设计语言仍然是方面都存在诸多问题，常用的程序设计语言仍然是3GL。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的基本要素程序设计语言的基本要素 第第 6 章章

41、 问题求解与程序设计问题求解与程序设计程序语言程序语言自然语言与程序设计语言的类比：文章由段落、句子、单词自然语言与程序设计语言的类比：文章由段落、句子、单词和字母组成，类似地，程序设计语言的一个程序由模块、语和字母组成，类似地，程序设计语言的一个程序由模块、语句、单词和基本字符组成。句、单词和基本字符组成。 文章文章程序程序 段落段落模块模块 句子句子语句语句 单词单词单词单词 字母字母基本字符基本字符基本符号基本符号单词单词语句语句函数函数程序程序词法规则词法规则语法规则语法规则功能逻辑功能逻辑有机组合有机组合计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设

42、计语言的基本要素程序设计语言的基本要素 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言n程序设计语言由语法和语义两方面定义的。程序设计语言由语法和语义两方面定义的。n语法语法包括词法规则和语法规则，包括词法规则和语法规则，词法规则词法规则规定了如何从语规定了如何从语言的基本符号构成词法单位（也称单词），言的基本符号构成词法单位（也称单词），语法规则语法规则规定了规定了如何由单词构成语法单位（例如语句），这些规则是判断一如何由单词构成语法单位（例如语句），这些规则是判断一个字符串是否构成一个形式上正确的程序的依据；个字符串是否构成一个形式上正确的程序的依据；n语义规则规定了

43、各语法单位的具体含义，程序设计语言的语义规则规定了各语法单位的具体含义，程序设计语言的语义具有上下文无关性，程序文本所表示的语义是单一的、语义具有上下文无关性，程序文本所表示的语义是单一的、确定的。确定的。n从某种角度说，学习程序设计语言主要就是学习这些规则。从某种角度说，学习程序设计语言主要就是学习这些规则。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的基本要素程序设计语言的基本要素 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言n学习程序设计语言的最终目的是能够表示问题的解决方案。学习程序设计语言的最终目的是能够表示问题的解决

44、方案。n实际上，所有程序设计语言的最终目的都是控制计算机按实际上，所有程序设计语言的最终目的都是控制计算机按照人们的意愿去工作。照人们的意愿去工作。n共同的目的使各种各样的程序设计语言具有共同的基本内共同的目的使各种各样的程序设计语言具有共同的基本内容，无论哪一种程序设计语言，都是以容，无论哪一种程序设计语言，都是以数据的表示数据的表示（常量、（常量、变量、数据类型等）、变量、数据类型等）、数据的组织数据的组织（数组、结构体、类等）、（数组、结构体、类等）、数据处理数据处理（赋值运算、算术运算、逻辑运算等）、（赋值运算、算术运算、逻辑运算等）、程序的流程序的流程控制程控制（顺序、分支、循环等）

45、、（顺序、分支、循环等）、数据传递数据传递（全局变量、函（全局变量、函数调用、消息传递等）为基本内容，只是不同的语言采用不数调用、消息传递等）为基本内容，只是不同的语言采用不同的方法实现上述基本内容，体现为不同的程序设计语言具同的方法实现上述基本内容，体现为不同的程序设计语言具有不同的表述格式（即语法规则）。有不同的表述格式（即语法规则）。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的环境程序设计的环境 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言n程序设计的环境是指利用程序设计语言进行程序开发的编程序设计的环境是指利用程序设计语言

46、进行程序开发的编程环境。程环境。n目前的编程环境大都是交互式集成开发环境（目前的编程环境大都是交互式集成开发环境（Integrated Design Environment，IDE），包括程序编辑、程序编译、），包括程序编辑、程序编译、运行调试等功能。此外，还包括许多编程的实用程序。运行调试等功能。此外，还包括许多编程的实用程序。n熟练使用编程工具和环境，也是提高编程效率的因素之一，熟练使用编程工具和环境，也是提高编程效率的因素之一，初学者应该尽快熟悉编程环境。初学者应该尽快熟悉编程环境。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的环境程序设计的环境

47、第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言编辑窗口编辑窗口执行按钮执行按钮编译按钮编译按钮信息窗口信息窗口计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n 利用高级语言编写的程序不能直接在计算机上执行，因为利用高级语言编写的程序不能直接在计算机上执行，因为计算机只能执行二进制的机器指令，所以，必须将高级语言计算机只能执行二进制的机器指令，所以，必须将高级语言编写的程序（称为编写的程序（称为源程序源程序）转换为在逻辑上等价的机器指令）转换

48、为在逻辑上等价的机器指令（称为（称为目标程序目标程序），实现这种转换的程序称为），实现这种转换的程序称为翻译程序翻译程序。n 不同的程序设计语言需要有不同的翻译程序。不同的程序设计语言需要有不同的翻译程序。n 同一种程序设计语言在不同类型的计算机上也需要配置不同一种程序设计语言在不同类型的计算机上也需要配置不同的翻译程序。同的翻译程序。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序同一种程序设计语言在不同类型的计算机上也需要配置同一种程序设计语言在不同类型的计算

49、机上也需要配置不同的翻译程序。不同的翻译程序。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n解释方式解释方式一般是翻译一句执行一句，在翻译过程中，并不一般是翻译一句执行一句，在翻译过程中，并不把源程序翻译成一个完整的目标程序，而是按照源程序中语把源程序翻译成一个完整的目标程序，而是按照源程序中语句的顺序逐条语句翻译成机器可执行的指令并立即予以执行。句的顺序逐条语句翻译成机器可执行的指令并立即予以执行。n由于解释方式不产生目标代码，所以，由于解释方式不产生目标代

50、码，所以，源程序的执行不能源程序的执行不能脱离其解释环境脱离其解释环境，并且每次运行都需要重新解释。，并且每次运行都需要重新解释。nBASIC语言和语言和JAVA语言都具有逐条解释执行程序的功能。语言都具有逐条解释执行程序的功能。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n编译方式编译方式是一个整体理解和翻译的过程，先由编译程序把是一个整体理解和翻译的过程，先由编译程序把源程序翻译成目标程序，然后再由计算机执行目标程序。源程序翻译成目标程序，然后再由计算机执

51、行目标程序。n由于编译后形成了可执行的目标代码，所以，由于编译后形成了可执行的目标代码，所以，目标程序可目标程序可以脱离其语言环境独立执行以脱离其语言环境独立执行。C、C+语言都是编译型语言。语言都是编译型语言。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n编译程序是把源程序翻译成目标程序，因此，编译程序需编译程序是把源程序翻译成目标程序，因此，编译程序需要根据要根据源语言的具体特点源语言的具体特点和对和对目标程序的具体要求目标程序的具体要求来设计。来设计。n

52、如同自然语言的翻译，编译程序的翻译规则是源语言的语如同自然语言的翻译，编译程序的翻译规则是源语言的语法规则和语义规则。法规则和语义规则。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序词法分析词法分析的任务是对源程序进行扫描和分解，按照词法规则的任务是对源程序进行扫描和分解，按照词法规则识别识别出一个个的单词，如关键字、标识符、运算符等，并将出一个个的单词，如关键字、标识符、运算符等，并将单词单词转化转化为某种机内表示。为某种机内表示。 其中，单词其中，单词是关键字，单词是关键字，单词是标识符，单词是标识符，单词是运算符，是运算符，单词单词是常量，单词是常量，单词是分隔符。是分隔符。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序语法分析语法分析是编译程序的核心部分，它的任务是对词法分析得是编译程序的核心