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

《计算机学科导论课件：第6章 问题求解与程序设计》由会员分享，可在线阅读，更多相关《计算机学科导论课件：第6章 问题求解与程序设计（53页珍藏版）》请在金锄头文库上搜索。

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 1 12 1 0 02 1 0 0AB

7、CDA 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; / degree存储通过节点存储通过节点i的桥

8、数，初始化为的桥数，初始化为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 程序设计：程序设计：是给出解决特定问题的程序的过程，是软件是给出解决特定问题的程序的过程，是软件构造活动中的重要组成部分，程序设计往往以构造活动中的重要组成部分，程序设计往往以某种程序设某种程序设计语言为工具计语言为工具，给出这种语言下的程序。，给出这种语言下的程序。n 专业的程序设计人员常被称为专业的程序设计人员常被称为程序员程序员。 第第 6 章

14、章 问题求解与程序设计问题求解与程序设计程序设计程序设计计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的关键程序设计的关键 第第 6 章章 问题求解与程序设计问题求解与程序设计程序设计程序设计n 程序设计的关键是数据表示和数据处理。程序设计的关键是数据表示和数据处理。n 数据表示数据表示完成的任务是从问题抽象出数据模型，并将该模完成的任务是从问题抽象出数据模型，并将该模型从机外表示转换为机内表示；型从机外表示转换为机内表示；n 数据处理数据处理完成的任务是对问题的求解方法进行抽象描述，完成的任务是对问题的求解方法进行抽象描述，即设计算法，再将算法的指令转换为

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

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

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

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

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

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

21、：顺序存储和链接存储。n 顺序存储的基本思想顺序存储的基本思想是：用一组是：用一组连续连续的存储单元的存储单元依次依次存存储数据元素，数据元素之间的逻辑关系由元素的储数据元素，数据元素之间的逻辑关系由元素的存储位置存储位置来表示；来表示；n 链接存储的基本思想链接存储的基本思想是：用一组是：用一组任意的任意的存储单元存储数存储单元存储数据元素，数据元素之间的逻辑关系用据元素，数据元素之间的逻辑关系用指针指针来表示。来表示。 第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存储结构 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章

22、章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存储结构 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计数据结构数据结构存储结构存储结构 ABCDEFGHIJ计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社算法的定义算法的定义第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法n 算算法法（Algorithm）:对对特特定定问问题题求求解解步步骤骤的的一一种种描描述述，是是指令指令的的有限序列有限序列。n 算法的五大特性：算法的五大特性： 输入输入：一个算法有零个或

23、多个输入。：一个算法有零个或多个输入。 输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。且每一步都在有穷时间内完成。 确定性确定性：算法中的每一条指令必须有确切的含义，对：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。于相同的输入只能得到相同的输出。 可行性可行性：算法描述的操作可以通过已经实现的基本操：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。作执行有限次来实现。计算机学科概论（第计算机学科概论（第2版）版）清华大学

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

25、计计的的求求解解步步骤骤记记录录下下来来，即即描描述述算算法法。通通常常用伪代码来描述算法。用伪代码来描述算法。n 伪伪代代码码是是介介于于自自然然语语言言和和程程序序设设计计语语言言之之间间的的方方法法，保保留留了了程程序序设设计计语语言言严严谨谨的的结结构构、语语句句的的形形式式和和控控制制成成分分，忽忽略略了了繁繁琐琐的的变变量量说说明明，在在抽抽象象地地描描述述算算法法时时一一些些处处理理和和条条件件允允许许使使用用自自然然语语言言来来表表达达。至至于于算算法法中中自自然然语语言言的的成成份有多少，取决于算法的份有多少，取决于算法的抽象级别抽象级别。n 由由于于伪伪代代码码书书写写方方

26、便便、格格式式紧紧凑凑、容容易易理理解解和和修修改改，因因此被称为此被称为算法语言算法语言。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算法第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法例例6.4 设计算法，在含有算法，在含有n个元素的集合中个元素的集合中查找最大找最大值元素。元素。解：解：设最大最大值为max，可以假定第，可以假定第1个元素个元素为最大最大值元素，依元素，依次将第次将第2、3、n个元素与个元素与max比比较，max中保存的始中保存的始终是是每次比每次比较后的最大后的最大值元素，算法用元素，算法用伪代代码描述如下：描述如下

27、： step1: max 第第1个元素；个元素； step2: 初始化被比初始化被比较元素的序号元素的序号i 2； step3: 当当i小于等于小于等于n时重复重复执行下述操作：行下述操作： step3.1: 如果第如果第i个元素大于个元素大于max，则max 第第i个元素；个元素； step3.2: i i + 1；step4: 输出出max；计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社描述算法描述算法第第 6 章章 问题求解与程序设计问题求解与程序设计算法算法例例6.5 设计算法，实现欧几里德算法。设计算法，实现欧几里德算法。解：设两个自然数是解：设两个自然数

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

29、循环直到循环直到r等于等于0 step2.1: m n; step2.2: n r; step2.3: r m mod n; step3: 输出输出n;计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社算法分析：对算法所需要的计算机资源进行估算。算法分析：对算法所需要的计算机资源进行估算。时间复杂度（时间复杂度（Time Complexity）空间复杂度（空间复杂度（Space Complexity）n撇开与计算机软硬件有关的因素，影响算法时间代价的最撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是主要因素是问题规模问题规模。n问题规模问题规模：输入量的多少

30、，一般来说，它可以从问题描述：输入量的多少，一般来说，它可以从问题描述中得到。例如，找出中得到。例如，找出100以内的所有素数，问题规模是以内的所有素数，问题规模是100。n一个显而易见的事实是：几乎所有的算法，对于规模更大一个显而易见的事实是：几乎所有的算法，对于规模更大的输入需要运行更长的时间。例如，找出的输入需要运行更长的时间。例如，找出10 000以内的所有以内的所有素数比找出素数比找出100以内的所有素数需要更多的时间。所以运行以内的所有素数需要更多的时间。所以运行算法所需要的时间算法所需要的时间 T 是问题规模是问题规模n的函数，记作的函数，记作T(n)。算法分析算法分析第第 6

31、章章 问题求解与程序设计问题求解与程序设计算法算法计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社n为了客观地反映一个算法的执行时间，可以用算法中为了客观地反映一个算法的执行时间，可以用算法中基本基本语句语句的执行次数来度量算法的工作量。的执行次数来度量算法的工作量。n基本语句基本语句：执行次数与整个算法的执行次数成正比的操作：执行次数与整个算法的执行次数成正比的操作指令。指令。n基本语句对算法运行时间的贡献最大，是算法中最重要的基本语句对算法运行时间的贡献最大，是算法中最重要的操作。操作。n分析算法的时间复杂度的基本方法是：找出所有语句中执分析算法的时间复杂度的基本

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

33、解：基本语句是解：基本语句是step3.1的比较语句，即第的比较语句，即第 i 个元素是否大个元素是否大于于max，该语句需要重复执行，该语句需要重复执行n 1次，因此，算法的时间次，因此，算法的时间复杂度是复杂度是O(n)。 step1: max 第第1个元素；个元素； step2: 初始化被比初始化被比较元素的序号元素的序号i 2； step3: 当当i小于等于小于等于n时重复重复执行下述操作：行下述操作： step3.1: 如果第如果第i个元素大于个元素大于max，则max 第第i个元素；个元素； step3.2: i i + 1；step4: 输出出max；计算机学科概论（第计算机学科

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

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

36、2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第三代程序设计语言（第三代程序设计语言（3GL）高级语言高级语言 n 高级语言高级语言：高级程序设计语言，相应地，机器语言和汇编：高级程序设计语言，相应地，机器语言和汇编语言称为语言称为低级语言低级语言，低级意味着要求程序员从机器

37、的层次上，低级意味着要求程序员从机器的层次上考虑问题。考虑问题。n 结构化程序设计语言结构化程序设计语言： BASIC 、 PASCAL、C等。等。n 面向对象程序设计语言面向对象程序设计语言：Java、C+、C#等。等。n 可视化程序设计语言可视化程序设计语言：VB、Delphi、Visual C+等。等。n 网络程序设计语言网络程序设计语言：ASP、PHP和和JSP等。等。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，

38、其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第四代程序设计语言（第四代程序设计语言（4GL）非过程式语言非过程式语言 n 利用利用4GL开发软件只需要考虑开发软件只需要考虑“做什么做什么”而不必考虑而不必考虑“如如何做何做”，不涉及太多的算法细节，从而大大提高软件生产率。，不涉及太多的算法细节，从而大大提高软件生产率。n 到目前为止，使用最广泛的到目前为止，使用最广泛的4GL是数据库查询语言，许多是数据库查询语言，许多大型数据库语言如大型数据库语言如Or

39、acle、Sybase、Informix等都包含有等都包含有4GL成分。成分。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的发展程序设计语言的发展 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第五代程序设计语言（第五代程序设计语言（5GL）知识型语言知识型语言 n 5GL主要应用在人工智能研究上，典型代表

40、是主要应用在人工智能研究上，典型代表是LISP语言和语言和PROLOG语言。语言。n 目前，目前，4GL和和5GL的发展都不是很成熟，在效率、应用等的发展都不是很成熟，在效率、应用等方面都存在诸多问题，常用的程序设计语言仍然是方面都存在诸多问题，常用的程序设计语言仍然是3GL。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的基本要素程序设计语言的基本要素 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言自然语言与程序设计语言的类比：文章由段落、句子、单词自然语言与程序设计语言的类比：文章由段落、句子、单词和字母组成，类似地，程序设计

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

42、n语语法法包包括括词词法法规规则则和和语语法法规规则则，词词法法规规则则规规定定了了如如何何从从语语言言的的基基本本符符号号构构成成词词法法单单位位（也也称称单单词词），语语法法规规则则规规定定了了如如何何由由单单词词构构成成语语法法单单位位（例例如如语语句句），这这些些规规则则是是判判断断一一个字符串是否构成一个形式上正确的程序的依据；个字符串是否构成一个形式上正确的程序的依据；n语语义义规规则则规规定定了了各各语语法法单单位位的的具具体体含含义义，程程序序设设计计语语言言的的语语义义具具有有上上下下文文无无关关性性，程程序序文文本本所所表表示示的的语语义义是是单单一一的的、确定的。确定的。

43、n从某种角度说，学习程序设计语言主要就是学习这些规则。从某种角度说，学习程序设计语言主要就是学习这些规则。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计语言的基本要素程序设计语言的基本要素 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言n学习程序设计语言的最终目的是能够表示问题的解决方案。学习程序设计语言的最终目的是能够表示问题的解决方案。n实实际际上上，所所有有程程序序设设计计语语言言的的最最终终目目的的都都是是控控制制计计算算机机按按照人们的意愿去工作。照人们的意愿去工作。n共共同同的的目目的的使使各各种种各各样样的的程程序序设设计

44、计语语言言具具有有共共同同的的基基本本内内容容，无无论论哪哪一一种种程程序序设设计计语语言言，都都是是以以数数据据的的表表示示（常常量量、变变量量、数数据据类类型型等等）、数数据据的的组组织织（数数组组、结结构构体体、类类等等）、数数据据处处理理（赋赋值值运运算算、算算术术运运算算、逻逻辑辑运运算算等等）、程程序序的的流流程程控控制制（顺顺序序、分分支支、循循环环等等）、数数据据传传递递（全全局局变变量量、函函数数调调用用、消消息息传传递递等等）为为基基本本内内容容，只只是是不不同同的的语语言言采采用用不不同同的的方方法法实实现现上上述述基基本本内内容容，体体现现为为不不同同的的程程序序设设计

45、计语语言言具具有不同的表述格式（即语法规则）。有不同的表述格式（即语法规则）。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的环境程序设计的环境 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言n程程序序设设计计的的环环境境是是指指利利用用程程序序设设计计语语言言进进行行程程序序开开发发的的编编程环境。程环境。n目目前前的的编编程程环环境境大大都都是是交交互互式式集集成成开开发发环环境境（Integrated Design Environment，IDE），包包括括程程序序编编辑辑、程程序序编编译译、运行调试等功能。此外，还包括许多编程的

46、实用程序。运行调试等功能。此外，还包括许多编程的实用程序。n熟熟练练使使用用编编程程工工具具和和环环境境，也也是是提提高高编编程程效效率率的的因因素素之之一一，初学者应该尽快熟悉编程环境。初学者应该尽快熟悉编程环境。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社程序设计的环境程序设计的环境 第第 6 章章 问题求解与程序设计问题求解与程序设计程序语言程序语言编辑窗口编辑窗口执行按钮执行按钮编译按钮编译按钮信息窗口信息窗口计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计

47、问题求解与程序设计翻译程序翻译程序n 利用高级语言编写的程序不能直接在计算机上执行，因为利用高级语言编写的程序不能直接在计算机上执行，因为计算机只能执行二进制的机器指令，所以，必须将高级语言计算机只能执行二进制的机器指令，所以，必须将高级语言编写的程序（称为编写的程序（称为源程序源程序）转换为在逻辑上等价的机器指令）转换为在逻辑上等价的机器指令（称为（称为目标程序目标程序），实现这种转换的程序称为），实现这种转换的程序称为翻译程序翻译程序。n 不同的程序设计语言需要有不同的翻译程序。不同的程序设计语言需要有不同的翻译程序。n 同一种程序设计语言在不同类型的计算机上也需要配置不同一种程序设计语言

48、在不同类型的计算机上也需要配置不同的翻译程序。同的翻译程序。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序同一种程序设计语言在不同类型的计算机上也需要配置不同一种程序设计语言在不同类型的计算机上也需要配置不同的翻译程序。同的翻译程序。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n解释方式解释方式一般是翻译一句执行一句，在翻译过程

49、中，并不一般是翻译一句执行一句，在翻译过程中，并不把源程序翻译成一个完整的目标程序，而是按照源程序中语把源程序翻译成一个完整的目标程序，而是按照源程序中语句的顺序逐条语句翻译成机器可执行的指令并立即予以执行。句的顺序逐条语句翻译成机器可执行的指令并立即予以执行。n由于解释方式不产生目标代码，所以，由于解释方式不产生目标代码，所以，源程序的执行不能源程序的执行不能脱离其解释环境脱离其解释环境，并且每次运行都需要重新解释。，并且每次运行都需要重新解释。nBASIC语言和语言和JAVA语言都具有逐条解释执行程序的功能。语言都具有逐条解释执行程序的功能。计算机学科概论（第计算机学科概论（第2版）版）清

50、华大学出版社清华大学出版社翻译程序的工作方式翻译程序的工作方式 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n编编译译方方式式是是一一个个整整体体理理解解和和翻翻译译的的过过程程，先先由由编编译译程程序序把把源程序翻译成目标程序，然后再由计算机执行目标程序。源程序翻译成目标程序，然后再由计算机执行目标程序。n由由于于编编译译后后形形成成了了可可执执行行的的目目标标代代码码，所所以以，目目标标程程序序可可以脱离其语言环境独立执行以脱离其语言环境独立执行。C、C+语言都是编译型语言。语言都是编译型语言。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版

51、社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n编编译译程程序序是是把把源源程程序序翻翻译译成成目目标标程程序序，因因此此，编编译译程程序序需需要根据要根据源语言的具体特点源语言的具体特点和对和对目标程序的具体要求目标程序的具体要求来设计。来设计。n如如同同自自然然语语言言的的翻翻译译，编编译译程程序序的的翻翻译译规规则则是是源源语语言言的的语语法规则和语义规则。法规则和语义规则。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求

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

53、法法分分析析是是编编译译程程序序的的核核心心部部分分，它它的的任任务务是是对对词词法法分分析析得得到到的的单单词词序序列列按按照照语语法法规规则则分分析析出出一一个个个个的的语语法法单单位位，如如表表达式、语句等。达式、语句等。 计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n语语义义分分析析的的任任务务是是检检查查程程序序中中语语义义的的正正确确性性，以以保保证证单单词词或语法单位能有意义地结合在一起。或语法单位能有意义地结合在一起。n语语义义分分析析的的一一

54、个个重重要要任任务务是是类类型型检检查查，即即对对每每个个运运算算符符的的运算对象，检查它们的类型是否合法。运算对象，检查它们的类型是否合法。 为什么计算机不能直接将一个整数和一个小数相加？为什么计算机不能直接将一个整数和一个小数相加？计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n 为了降低编译的难度，一般先将源程序转换为某种中间形为了降低编译的难度，一般先将源程序转换为某种中间形式，然后再转换为目标代码。式，然后再转换为目标代码。n 中间代码中间代码是复杂性

55、介于源语言和机器语言之间的一种表现是复杂性介于源语言和机器语言之间的一种表现形式，常用的中间代码有三元式（运算符，运算对象形式，常用的中间代码有三元式（运算符，运算对象1，运，运算对象算对象2）、四元式（运算符，运算对象）、四元式（运算符，运算对象1，运算对象，运算对象2，结，结果）、逆波兰式（运算对象果）、逆波兰式（运算对象1，运算对象，运算对象2，运算符）等。，运算符）等。n Java程序的编译过程只到中间代码阶段，然后再由安装在程序的编译过程只到中间代码阶段，然后再由安装在计算机上的计算机上的Java虚拟机把中间代码形式的虚拟机把中间代码形式的Java程序转换为特程序转换为特定机器上的目

56、标程序，以实现定机器上的目标程序，以实现Java程序的跨平台特性。程序的跨平台特性。计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社编译程序的基本过程编译程序的基本过程 第第 6 章章 问题求解与程序设计问题求解与程序设计翻译程序翻译程序n目目标标代代码码的的任任务务是是将将中中间间代代码码转转换换为为特特定定机机器器的的目目标标程程序序，这这涉涉及及到到计计算算机机硬硬件件系系统统功功能能部部件件的的使使用用、机机器器指指令令的的使使用用、存储空间的分配以及寄存器的调度等。存储空间的分配以及寄存器的调度等。n显显然然，高高级级语语言言和和计计算算机机的的多多样样性性

57、为为目目标标代代码码生生成成的的理理论论研究和实现技术带来很大的复杂性。研究和实现技术带来很大的复杂性。源文件源文件.cpp编译0101000010100101010100101001000000100010000100111110101010010011010目目标文件文件.obj计算机学科概论（第计算机学科概论（第2版）版）清华大学出版社清华大学出版社第第 6 章章 问题求解与程序设计问题求解与程序设计回答问题回答问题学完本章，你将如何回答下列问题：学完本章，你将如何回答下列问题： 1. 什么是程序？什么是程序设计？什么是程序设计语言？什么是程序？什么是程序设计？什么是程序设计语言？ 2. 程序是怎么设计出来的？程序设计的关键是什么？程序是怎么设计出来的？程序设计的关键是什么？ 3. 计算机运行程序的过程就是对数据的加工处理过程，如计算机运行程序的过程就是对数据的加工处理过程，如何将数据存储到计算机的内存中？如何描述问题的处理方法何将数据存储到计算机的内存中？如何描述问题的处理方法和具体步骤才能让计算机和具体步骤才能让计算机“看懂看懂”呢？呢？ 4. 为了方便编写程序，现代程序设计普遍采用高级程序设为了方便编写程序，现代程序设计普遍采用高级程序设计语言，高级语言程序如何转换为等价的机器指令？计语言，高级语言程序如何转换为等价的机器指令？