第6章 问题求解及程序设计

1、第第 3 部分部分 程序设计程序设计程序设计在计算机系统的位置程序设计在计算机系统的位置 进度14第第 6 章章 问题求解与程序设计问题求解与程序设计本章讨论的主要问题是：本章讨论的主要问题是： 1. 什么是程序？什么是程序设计？什么是程序设计语言？什么是程序？什么是程序设计？什么是程序设计语言？ 2. 程序是怎么设计出来的？程序设计的关键是什么？程序是怎么设计出来的？程序设计的关键是什么？ 3. 计算机运行程序的过程就是对数据的加工处理过程，如计算机运行程序的过程就是对数据的加工处理过程，如何将数据存储到计算机的内存中？如何描述问题的处理方法何将数据存储到计算机的内存中？如何描述问题的处理方

2、法和具体步骤才能让计算机和具体步骤才能让计算机“看懂看懂”呢？呢？ 4. 为了方便编写程序，现代程序设计普遍采用高级程序设为了方便编写程序，现代程序设计普遍采用高级程序设计语言，高级语言程序如何转换为等价的机器指令？计语言，高级语言程序如何转换为等价的机器指令？情景问题情景问题七桥问题七桥问题 n从而将哥尼斯堡七桥问题抽象为一个数学问题：n一幅图，寻找一条只通过每边一次的路径一幅图，寻找一条只通过每边一次的路径叫做叫做欧拉路径欧拉路径。如果这条路径的起点和终点是同一。如果这条路径的起点和终点是同一点，那么这条路径叫做点，那么这条路径叫做欧拉回路欧拉回路。情景问题情景问题七桥问题七桥问题 【基本

3、思路基本思路】是否存在欧拉路径的判定规则：】是否存在欧拉路径的判定规则：（1 1）如果通奇数桥的地方多于两个，则不存在欧拉回路；）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2 2）如果只有两个地方通奇数桥，可以从这两个地方之一出）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；发，找到欧拉回路；（3 3）如果没有一个地方通奇数桥，则无论从哪里出发，都能）如果没有一个地方通奇数桥，则无论从哪里出发，都能找到欧拉回路。找到欧拉回路。 由上述判定规则得到求解七桥问题的基本思路由上述判定规则得到求解七桥问题的基本思路：依次计算依次计算图中与每个节点相关联的边的个数（称为节点的度

4、），根据图中与每个节点相关联的边的个数（称为节点的度），根据度为奇数的节点个数判定是否存在欧拉回路。度为奇数的节点个数判定是否存在欧拉回路。 情景问题情景问题七桥问题七桥问题 n【数据表示数据表示数据结构数据结构】设邻接矩阵设邻接矩阵arcnn存储图。存储图。n【数据处理数据处理算法算法】算法用伪代码描算法用伪代码描述如下：述如下： 1. 通奇数桥的顶点个数通奇数桥的顶点个数count初始化为初始化为0； 2. 下标下标 i 从从0 n 1重复执行下述操作：重复执行下述操作： 2.1 计算矩阵计算矩阵arcnn第第i行元素之和行元素之和degree; 2.2 如果如果degree为奇数，则为奇

5、数，则count+; 3. 如果如果count等于等于0或或2，则存在欧拉回路；否则不存在，则存在欧拉回路；否则不存在欧拉回路；欧拉回路；0 1 2 21 0 1 12 1 0 02 1 0 0ABCDA B C D情景问题情景问题七桥问题七桥问题 【程序实现程序实现】以下是用】以下是用C语言编写的程序：语言编写的程序： int EulerCircuit(int mat1010, int n) /函数定义，二维数组作为形参函数定义，二维数组作为形参 int i, j, count = 0, degree; /count累计通奇数桥的节点个数累计通奇数桥的节点个数 for (i = 0; i n

6、; i+) /依次累加每一行的元素依次累加每一行的元素 degree = 0; / degree存储通过节点存储通过节点i的桥数，初始化为的桥数，初始化为0 for (j = 0; j n; j+) /依次处理每一列的元素依次处理每一列的元素 degree = degree + matij; /将通过节点将通过节点i的桥数求和的桥数求和 if (degree % 2 != 0) /桥数为奇数桥数为奇数 count+; return count; /结束函数，并将结束函数，并将count返回到调用处返回到调用处 问问 题题算算 法法程程 序序想想 法法抽象模型抽象模型基本思路基本思路数据表示数据

7、表示数据处理数据处理程序语言程序语言设计方法设计方法编程环境编程环境人（设计方案）人（设计方案）计算机计算机(执行方案执行方案)6.1.1程序设计的一般过程程序设计的一般过程 理解程序理解程序n 计算机是一个大容量、高速运转、但是没有思维的机器。计算机是一个大容量、高速运转、但是没有思维的机器。n 计算机只认识计算机只认识 0 和和 1，听不懂人说的话，听不懂人说的话计算机如何接计算机如何接收人的指令？收人的指令？有问题需要解有问题需要解决的人决的人可以解决问题可以解决问题的计算机的计算机Hello理解程序理解程序如何实现人和计算机的交流？如何实现人和计算机的交流？n 计算机是一个大容量、高速

8、运转、但是没有思维的机器。计算机是一个大容量、高速运转、但是没有思维的机器。n 计算机输出了计算机输出了 0 和和 1 的编码，可是人看不懂的编码，可是人看不懂如何解释如何解释计算机的运算结果？计算机的运算结果？有问题需要解有问题需要解决的人决的人可以解决问题可以解决问题的计算机的计算机0101000110理解程序理解程序有 问 题 需 要 解有 问 题 需 要 解决的人决的人可以解决问题的可以解决问题的计算机计算机程序是跨越这条鸿沟的桥梁，人要和计算机有效地交流，程序是跨越这条鸿沟的桥梁，人要和计算机有效地交流，必须通过程序。必须通过程序。 程序程序n 程序：程序：是能够实现特定功能的一组是

9、能够实现特定功能的一组指令指令序列的集合，是序列的集合，是描述对某一问题的解决步骤。描述对某一问题的解决步骤。其中，指令可以是机器指令、汇编语言的语句，也可以是高级语言的语句，甚至还可以是用自然语言描述的指令。n 用高级语言编写的程序称为用高级语言编写的程序称为源程序源程序；用机器语言（或汇；用机器语言（或汇编语言）编写的程序称为编语言）编写的程序称为目标程序目标程序；由二进制代码表示的；由二进制代码表示的程序称为程序称为机器代码机器代码。n 程序设计：程序设计：是给出解决特定问题的程序的过程，是软件是给出解决特定问题的程序的过程，是软件构造活动中的重要组成部分，程序设计往往以构造活动中的重要

10、组成部分，程序设计往往以某种程序设某种程序设计语言为工具计语言为工具，给出这种语言下的程序。，给出这种语言下的程序。n程序员程序员:专业的程序设计人员。专业的程序设计人员。 几个概念几个概念6.1.2程序设计的关键程序设计的关键 程序设计的关键是程序设计的关键是数据表示数据表示和和数据处理数据处理。n 数据表示数据表示：从问题抽象出数据模型，并将该模型从机外表示转换为机内表示；n 数据处理数据处理：对问题的求解方法进行抽象描述，即设计算法，再将算法的指令转换为某种程序设计语言对应的语句。6.2 数据结构数据结构n 数据数据：所有能输入到计算机中并能被计算机程序识别和处：所有能输入到计算机中并能

11、被计算机程序识别和处理的符号集合。理的符号集合。包括数值、字符、图形、图像、声音等。n 数据元素数据元素：数据的基本单位，在计算机程序中通常作为一：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成，据项组成，例如，一本书的书目信息为一个数据元素，而书目信息的每一项（如书名、作者名等）为一个数据项。数据项是数据的不可分割的最小单位。n 数据结构数据结构：相互之间存在一定关系的数据元素的集合，通：相互之间存在一定关系的数据元素的集合，通常，数据元素之间具有以下三种基本关系：常，数据元素之间具有以

12、下三种基本关系：（1）一对一的线性关系：）一对一的线性关系：线性结构线性结构；（2）一对多的层次关系：）一对多的层次关系：树结构树结构；（3）多对多的任意关系：）多对多的任意关系：图结构图结构。6.2.1 基本的数据结构基本的数据结构例例6.1 为学籍管理问题抽象数据模型。为学籍管理问题抽象数据模型。例例6.2 为人机对弈问题抽象数据模型。为人机对弈问题抽象数据模型。例例6.3 为七巧板涂色问题抽象数据模型。为七巧板涂色问题抽象数据模型。引入：引入：为现实世界的问题建立数据模型后，还要将该模型存储在计算机的内存中，即将数据从机外表示转换为机内表示。通常有两种存储表示方法：通常有两种存储表示方法

13、：顺序存储和链接存储。n 顺序存储：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示；n 链接存储：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。 6.2.2 数据结构的存储表示数据结构的存储表示 图6.8 线性结构的顺序存储示意图ABCDEFGHIJ图6.10 树结构的链接存储示意图6.3.1 算法及描述算法的方法算法及描述算法的方法6.3 算法和算法分析算法和算法分析n 算法算法（Algorithm）:对对特定问题特定问题求解步骤的一种描述，求解步骤的一种描述，是是指令指令的的有限序列有限序列。n 算法的五大特性：算法的五大特性：

14、输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。n 伪代码：伪代码：是介于自然语言和程序设计语言之间的方法，保留了程序设计语言严谨的结构、语句的形式和控制成分，忽略了繁琐的变量说明，在抽象地描述算法时一些处理和条件允许使用自然语言来表达。n 由于伪代码书写方便、格式紧凑、容易理解和修改，因此被称为算法语言算法语言。描述算法-伪代码伪代码例例6.4 设计算法

15、，在含有设计算法，在含有n个元素的集合中查找最大值元素。个元素的集合中查找最大值元素。（考点）（考点）解：设最大值为解：设最大值为max，可以假定第，可以假定第1个元素为最大值元素，依个元素为最大值元素，依次将第次将第2、3、n个元素与个元素与max比较，比较，max中保存的始终是中保存的始终是每次比较后的最大值元素，算法用伪代码描述如下：每次比较后的最大值元素，算法用伪代码描述如下： step1: max 第第1个元素；个元素； step2: 初始化被比较元素的序号初始化被比较元素的序号i 2； step3: 当当i小于等于小于等于n时重复执行下述操作：时重复执行下述操作： step3.1:

16、 如果第如果第i个元素大于个元素大于max，则，则max 第第i个元素；个元素； step3.2: i i + 1；step4: 输出输出max；例例6.5 设计算法，实现欧几里德算法。设计算法，实现欧几里德算法。解：解：设两个自然数是m和n并满足mn，欧几里德算法的基本思想是将m和n辗转相除直到余数为0。例如，m = 35，n = 25，m除以n的余数用r表示，计算过程如下：当余数当余数r为为0时，被除数时，被除数n就是就是m和和n的最大公约数。的最大公约数。 例例6.5 设计算法，实现欧几里德算法。设计算法，实现欧几里德算法。 step1: r m mod n; step2: 循环直到循环

17、直到r等于等于0 step2.1: m n; step2.2: n r; step2.3: r m mod n; step3: 输出输出n;算法分析：算法分析：对算法所需要的计算机资源进行估算。时间复杂度（时间复杂度（Time Complexity）空间复杂度（空间复杂度（Space Complexity）1.时间复杂度时间复杂度n撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是问题规模问题规模。问题规模问题规模：输入量的多少，一般来说，它可以从问题描述中：输入量的多少，一般来说，它可以从问题描述中得到。得到。例如，找出100以内的所有素数，问题规模是100。几乎所有的算法，对于规

18、模更大的输入需要运行更长的时间。几乎所有的算法，对于规模更大的输入需要运行更长的时间。例如，找出10 000以内的所有素数比找出100以内的所有素数需要更多的时间。所以运行算法所需要的时间 T 是问题规模n的函数，记作T(n)。6.3.2 算法分析算法分析n使用使用“基本语句基本语句”度量算法的时间复杂度度量算法的时间复杂度n基本语句基本语句：执行次数与整个算法的执行次数成正比的操作指令。n分析时间复杂度的方法：分析时间复杂度的方法：找出所有语句中执行次数最多的那条语句作为基本语句，计算基本语句的执行次数，取其数量级放入大中即可。例例6.6 分析下列算法的时间复杂度。分析下列算法的时间复杂度。

19、解：基本语句是解：基本语句是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；2.空间复杂空间

20、复杂n空间复杂度：空间复杂度：是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数，记作S(n)=O(f(n)。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。n比如两个矩阵的运算，在中间设置了一个中间矩阵来保存一些数据，这些空间叫做空间复杂度。n一般情况下是不考虑空间复杂度的n程序设计语言是计算机可识别的语言，是人与程序设计语言是计算机可识别的语言，是人与计算机交流的工具。人把要程序完成的工作告计算机交流的工具。人把要程序完成的工作告诉计算机，就要使用程序设计语言编写程序，诉计算机，就要使用程序设计语言编写程序，让计算机执行程序，以完成相应的工作。让计算机

21、执行程序，以完成相应的工作。6.4 程序设计语言程序设计语言6.4.1 程序设计语言的发展程序设计语言的发展 6.4 程序设计语言程序设计语言程序设计语言的发展是一个不断演化的过程，其根本的推程序设计语言的发展是一个不断演化的过程，其根本的推动力是对抽象机制的更高的要求，以及对程序设计思想的更动力是对抽象机制的更高的要求，以及对程序设计思想的更好的支持。好的支持。 第一代程序设计语言（第一代程序设计语言（1GL）机器语言机器语言 如果不小心弄错了一如果不小心弄错了一个二进制位，该如何个二进制位，该如何找出来？找出来？第二代程序设计语言（第二代程序设计语言（2GL）汇编语言汇编语言 例如，例如，

22、ADD表示机器表示机器指令指令00000100。相对于。相对于机器语言，汇编语言简机器语言，汇编语言简化了程序编写，而且不化了程序编写，而且不容易出错容易出错第三代程序设计语言（第三代程序设计语言（3GL）高级语言高级语言 n 高级语言高级语言：高级程序设计语言，相应地，机器语言和汇编语言称为低级语言，低级意味着要求程序员从机器的层次上考虑问题。n 结构化程序设计语言结构化程序设计语言： BASIC 、 PASCAL、C等。等。n 面向对象程序设计语言面向对象程序设计语言：Java、C+、C#等。等。n 可视化程序设计语言可视化程序设计语言：VB、Delphi、Visual C+等。等。n 网

23、络程序设计语言网络程序设计语言：ASP、PHP和和JSP等。等。开发语言流行程序排名开发语言流行程序排名第四代程序设计语言（第四代程序设计语言（4GL）非过程式语言非过程式语言 n 利用利用4GL开发软件只需要考虑开发软件只需要考虑“做什么做什么”而不必考虑而不必考虑“如如何做何做”，不涉及太多的算法细节，从而大大提高软件生产率。，不涉及太多的算法细节，从而大大提高软件生产率。n 到目前为止，使用最广泛的4GL是数据库查询语言，许多大型数据库语言如Oracle、Sybase、Informix等都包含有4GL成分。n例如：Select * from student where 姓名=“李明” 第

24、五代程序设计语言（第五代程序设计语言（5GL）知识型语言知识型语言 n 5GL主要应用在人工智能研究上，典型代表是主要应用在人工智能研究上，典型代表是LISP语言和语言和PROLOG语言。语言。n 目前，4GL和5GL的发展都不是很成熟，在效率、应用等方面都存在诸多问题，常用的程序设计语言仍然是常用的程序设计语言仍然是3GL。 6.4.2 程序设计语言的基本要素程序设计语言的基本要素 自然语言与程序设计语言的类比：文章由段落、句子、单词自然语言与程序设计语言的类比：文章由段落、句子、单词和字母组成，类似地，程序设计语言的一个程序由模块、语和字母组成，类似地，程序设计语言的一个程序由模块、语句、

25、单词和基本字符组成。句、单词和基本字符组成。 文章文章程序程序 段落段落模块模块 句子句子语句语句 单词单词单词单词 字母字母基本字符基本字符基本符号基本符号单词单词语句语句函数函数程序程序词法规则词法规则语法规则语法规则功能逻辑功能逻辑有机组合有机组合n程序设计语言由程序设计语言由语法语法和和语义语义两方面定义的。两方面定义的。1.语法语法包括词法规则和语法规则词法规则规定了如何从语言的基本符号构成词法单位（也称单词）语法规则规定了如何由单词构成语法单位（例如语句），这些规则是判断一个字符串是否构成一个形式这些规则是判断一个字符串是否构成一个形式上正确的程序的依据；上正确的程序的依据；2.语

26、义语义：规定了各语法单位的具体含义，程序设计语言的语义具有上下文无关性，程序文本所表示的语义是单一的、确定的。n从某种角度说，学习程序设计语言主要就是学习这些规则。从某种角度说，学习程序设计语言主要就是学习这些规则。语法正确语法正确,语义正确语义正确.sum=0;for (i=1;i=100;i+) sum=sum+i;printf(%dn,sum);语法正确语法正确,语义错误语义错误:sum=0;for (i=0;i100;i+) sum=sum+i;printf(%dn,sum); 自然语言语义自然语言语义:描述你的计算过程意思正确.例如:雪是白的. - 语法正确,语义正确.雪是红的. -

27、 语法正确,语义错误.程序语言语义：计算程序语言语义：计算1加到加到100等与几等与几 6.4.3 程序设计的环境程序设计的环境 n程序设计的环境：程序设计的环境：利用程序设计语言进行程序开发的编程环境。n目前的编程环境大都是交互式集成开发环境（Integrated Design Environment，IDE），包括程序编辑、程序编译、运行调试等功能。此外，还包括许多编程的实用程序。n熟练使用编程工具和环境，也是提高编程效率的因素之一，初学者应该尽快熟悉编程环境。 编辑窗口编辑窗口执行按钮执行按钮编译按钮编译按钮信息窗口信息窗口6.5.1 翻译程序的工作方式翻译程序的工作方式 6.5 翻译程

28、序翻译程序n翻译程序：翻译程序：利用高级语言编写的程序不能直接在计算机上执利用高级语言编写的程序不能直接在计算机上执行，必须将高级语言编写的程序（行，必须将高级语言编写的程序（称为源程序）转换为在逻）转换为在逻辑上等价的机器指令（辑上等价的机器指令（称为目标程序），实现这种转换的程），实现这种转换的程序称为序称为。p 不同的程序设计语言需要有不同的翻译程序。p 同一种程序设计语言在不同类型的计算机上也需要配置不同的翻译程序。同一种程序设计语言在不同类型的计算机上也需要配置同一种程序设计语言在不同类型的计算机上也需要配置不同的翻译程序。不同的翻译程序。n翻译程序的工作方式通常分为两种翻译程序的工

29、作方式通常分为两种n解释方式解释方式1.编译方式编译方式1.解释方式：解释方式：一般是翻译一句执行一句一般是翻译一句执行一句，在翻译过程中，并不把源程序翻译成一个完整的目标程序，而是按照源程序中语句的顺序逐条语句翻译成机器可执行的指令并立即予以执行。n由于解释方式不产生目标代码，所以，由于解释方式不产生目标代码，所以，源程序的执行不能源程序的执行不能脱离其解释环境脱离其解释环境，并且每次运行都需要重新解释。，并且每次运行都需要重新解释。nBASIC语言和语言和JAVA语言都具有逐条解释执行程序的功能。语言都具有逐条解释执行程序的功能。2.编译方式编译方式是一个整体理解和翻译的过程，先由编译程序

30、把是一个整体理解和翻译的过程，先由编译程序把源程序翻译成目标程序，然后再由计算机执行目标程序。源程序翻译成目标程序，然后再由计算机执行目标程序。n由于编译后形成了可执行的目标代码，所以，由于编译后形成了可执行的目标代码，所以，目标程序可目标程序可以脱离其语言环境独立执行以脱离其语言环境独立执行。C、C+语言都是编译型语言。语言都是编译型语言。6.5.2 编译程序的基本过程编译程序的基本过程 1.词法分析词法分析 词法分析词法分析的任务是对源程序进行扫描和分解，按照词法规则的任务是对源程序进行扫描和分解，按照词法规则识别识别出一个个的单词，出一个个的单词，如关键字、标识符、运算符等，并将单词转化为某种机内表示。 其中，单词其中，单词是关键字，单词是关键字，单词是标识符，单词是标识符，单词是运算符，是运算符，单词单词是常量，单词是常量，单词是分隔符。是分隔符。2.语法分析语法分析 语法分析语法分析是编译程序的核心部分，它的任务是对词法分析得，它的任务是对词法分析得到的单词序列按照语法规则分析出一个个的语法单位，如表到的单词序列按照语法规则分析出一个个的语法单位，如表达式、语句等。达式、语句等。 图6.20 语法树3.语义分析语义分析 n语义分析语义分析：检查程序中语义的正确性，以保证单词或语