计算机科学导论(第2版)第6章 程序设计与算法分析

计算机科学导论 学习计算机专业的第一门基础课程 第六章 程序设计与算法分析 本章要点 初步了解程序设计的基础知识 掌握结构化程序设计和面向对象程序设计的基本方法 掌握数据结构中的基本数据类型及其实现 掌握程序设计算法的基本思想及几种经典的算法 了解编译原理的基本知识 程序的概念 程序 就是能够实现特定功能的一组指令序列的集合。 程序设计 是程序员编写一系列可存储的指令以指示计算机完成某些工作的过程。这些指令用程序设计语言写成。 程序设计语言 是一组专门设计的用来生成一系列可被计算机处理和执行的指令的符号集合。 程序设计人员用程序设计语言写成的指令称作 代码 。 程序设计基础 计算机程序设计语言 分类： 低级语言、高级语言。 1）低级语言包括两种类型：机器语言和汇编语言。 2） 机器语言 机器语言面向机器，可以由 不同的机器能够识别的机器语言是不相同的。 机器语言指令都是用一串 0、 1构成的二进制位串来表示的。 指令系统是机器提供的机器指令的集合。 用二进制编码表示的指令，称为机器指令，或称为机器码。 用机器指令编写的程序称为机器语言程序，或称为目标程序，这是计算机能够直接执行的程序。 机器语言难以阅读和理解，编写和修改都比较困难，而且通用性较差。 汇编语言 汇编语言也称符号语言。 指令助记符是指令英文名称的缩写，容易记忆。 所谓汇编语言，就是采用字母、数字和符号来代替由一个个 0和 1构成的指令操作码、寄存器、数据和存储地址等，并在程序中用它们代替二进制编码数，这样编写出来的程序就称为符号语言程序或汇编语言程序。 大多数情况下，一条汇编指令直接对应一条机器指令，少数对应几条机器指令。 汇编语言具有一个本质上与机器语言一一对应的指令系统。汇编语言的实质和机器语言是相同的。 低级语言的特点 都与特定的计算机硬件系统紧密相关，来自于特定系统的指令系统，可移植性差； 专业知识要求高，要求对计算机硬件的结构和工作原理非常熟悉； 每条指令的功能很单一，程序员编制源程序时指令比较繁琐； 由于直接针对特定硬件编程，所以，最终的可执行程序代码精炼，而且执行效率非常高。 两者主要的区别在于：机器语言无需翻译或编译， 汇编语言必须经过汇编才能得到目标程序。 汇编 虽然汇编语言比机器语言容易阅读理解和便于检查，所以仍然需要一种特殊的程序，该程序能够将用汇编语言编写的程序“翻译”成 实现这种翻译功能的特殊程序称为 汇编语言翻译程序、汇编程序或汇编器 。程序员手工编写的程序统称为源程序，用汇编语言编写的源程序称为汇编语言源程序，汇编程序将源程序翻译得到的机器语言程序称为目标程序，翻译的过程称为 汇编 。 反汇编程序 用于将目标代码程序转换成相应的汇编语言源程序，这一过程称为反汇编。反汇编主要用于识别源程序代码，常用的调试工具程序 高级语言的产生 一个问题：如何解决程序的可移植性，即：程序员编写的源程序如何可以从一台计算机很容易地转到另一台计算机上工作。为了解决这些问题，人们引入了高级语言来编写程序。 所谓高级语言是一种由表达各种意义的“词”和“公式”，按照一定的“语法规则”来编写程序的语言，又称为程序设计语言或算法语言。 高级语言之所以“高级”，就是因为它使程序员可以完全不用与计算机的硬件打交道，可以不必了解机器的指令系统。 程序员可以把硬件上复杂的概念比如存储空间抽象成一个所谓的变量之类的概念，因而程序员就可以绕开硬件问题而集中精力解决问题本身，编程效率大大提高。 由于高级语言与具体机器无关，那么在一种机器上运行的高级语言程序可以几乎不经改动地移植到另一种机器上运行，大大提高了程序的通用性。 此外，由于高级语言与自然语言 (尤其是英语 )很相似，因此易学、易懂，也易编写。 高级语言的常见类型 目前已经有许多高级语言在流行，并且新的类型还在不断出现和升级。 用户在实际应用中进行程序设计时，可根据情况选择适合的高级语言。 (1) (2) (3) (4) (5) (6) C+语言 (7) 其他高级语言 基于视窗类操作系统的，如 +、 高级语言的优点是语句的功能强，源程序比较短，容易学习，使用方便，通用性较强，便于推广和交流。 其缺点是编译程序比汇编程序复杂，而且编译出来的目标程序往往效率不高，目标程序的长度比有经验的程序员所编的同样功能的汇编语言程序要长 半以上，运行时间也要长一些。 因此，在很多对时间要求比较高的系统，如某些实时控制系统或者大型计算机控制系统中，低级语言，主要是汇编语言，仍然得到了一定的应用。 高级语言的基本内容 高级程序设计语言依赖于各自特定的语句和语法。一条一条的语句是构成源程序的基本单位。高级语言的一条语句被编译或解释时往往会对应多条机器指令。 每一种编程语言都包含一组语句和语法。所谓语法，是指管理语言结构和语句的一组规则。不论使用何种设计语言，都必须遵循其语法规则。 以下内容主要描述了大多数高级语言都共同具备的特性，但不一定是所有高级语言都有的。 1高级语言的基本符号 高级语言都是由所谓的基本符号组成的。基本符号可以分为单字符和多字符两种情况。单字符基本符号由单个字符组成，在高级语言中通常都有下列几种单字符基本符号： (1) 字母 大写英文字母 A Z，小写英文字母 a z，共 52个符号。 (2) 数字 0 9，共 10个数字符号。 (3)特殊字符 (加 )， (减 )， *(乘 )， /(除 )， (乘方 )，(等号 )， (左括号 )， )(右括号 )， (大于 )，(小于 )， (逗号 )， (空格 )等。 在高级语言中的多字符基本符号由两个或两个以上的字符组成，例如 移 )、 (小于或等于 )、 )等等。 2高级语言的基本元素 基本元素由基本符号组成，可分为数、逻辑值、名字、标号和字符串等五大类。 (1) 数 它由 0 9共 10个基本数字和其他一些符号 (如小数点“ .”、正负号“、”及指数符号“ E”等所构成。 (2) 逻辑值 由真 (假 (个值表示。 (3) 名字 由字符组成，一般约定名字的开头是字母或者下划线，其后可为字母或数字，如 _字可用来定义常量、变量、函数、过程或子程序的，也被用来定义成某些东西，故也称为标识符。在高级语言中，一般还规定了组成名字的字符的长度，即字符个数。 (4) 标号 是在高级语言中的程序语句前所加的一个名字，主要用来指示程序可能的转移方向。 (5) 字符串 由一串字符所组成。在不同的高级语言中，字符串中的多个字符放在一对单引号或双引号中。 3基本的数据类型 任何一种高级语言都会定义一些基本的数据类型。基本的数据类型通常包括整数数据类型、实数数据类型和字符数据类型等。 在程序中，除了值无需改变的常数外，大部分数据的值是可以修改的。在程序中，变量是指代表某个具体数值，并且所代表的数值可改变的一个符号名字。 变量必须先定义，然后才能使用，这是 条基本原则。 变量实质上代表了一个特定大小的内存单元空间。 定义变量的实质就是让程序为该变量分配一个特定的内存空间。 变量的类型实质上反映了该数据占用内存空间的大小，即分配给该变量代表的数据的所占据的内存单元的字节数目。 4结构数据类型 是在基本数据类型的基础上构造出来的数据类型。数组和结构体是大多数高级语言都支持的两种最基本的结构数据类型。 (1) 数组类型 数组是若干个相同类型的数据的集合。 (2) 用户自定义的结构体类型 结构体是隶属于同一个事物的多个不同类型的数据的集合，用来表示具有若干个属性的一个事物。 除了以上两种最基本的结构数据类型外，许多高级语言还有比如枚举、集合，以及更复杂的队列、堆栈等多种数据类型。 结构数据类型在使用时也必须定义相应类型的“变量”名字。 5运算符与表达式 表达式是由基本符号、基本元素和各种数据通过各种运算符连接而成的。按表达式的运算结果可以分为算术表达式、逻辑表达式和字符串表达式等几种情况。 高级语言中的运算符大致包括以下几个方面： (1) 逻辑运算： 与、或、非、异或。 (2) 算术运算： 加、减、乘、除、取模。 (3) 数据比较： 大于、小于、等于、不等于。 (4) 数据传送； 输入、输出、赋值。 (5) 算术表达式： 该表达式的运算结果是数，它非常近似于日常的数学公式。 (6) 关系运算表达式： 该表达式的运算结果是逻辑值，常用的运算符包含 (大于 )、 (小于 )、 (等于 )、 (小于等于 )、 (大于等于 )、不等于。 (7) 字符串表达式： 该表达式的运算结果是字符串。 6语句 语句是构成高级语言源程序的基本单位，是由基本元素、运算符、表达式等组成。任何一种高级语言往往都支持赋值、条件判断、循环、输入输出等语句。程序员利用这些语句的结合，能够很方便地编制出功能强大的程序。 7库函数和用户自定义的函数 为了支持用户编写出功能强大的源程序，几乎所有的高级语言都为用户提供了丰富的库函数，这些库函数能够实现某些特定的功能，比如计算一个比较复杂的数学函数。 在源程序中，用户也可以自己定义自己的函数 (子程序或过程 )，以便以后可以反复调用这些代码集合。 8注释 任何一种程序设计语言都强调注释的重要性。源程序所包含的代码往往比较冗长，添加必要的注释不仅有助于阅读程序，更重要的是，在需要对程序功能进行扩充时，注释可以极大地帮助程序员对原始程序的理解。 经常会出现这样一种情况，程序员自己编写的程序，经过一段时间后，可能就是半年或者几个月以后，程序员自己也读不懂自己的程序了。况且，程序不仅要自己看得懂，更重要的是也要让别人能够看懂。 9程序设计风格 (1) 编码格式和编码约定在整个程序中应保持一致。 (2) 程序中应给出必要的注释，尤其在变量定义、调用接口、参数传递处，在修改程序时应注明修改人、时间、简要的修改原因。 (3) 对变量、函数标识等的命名，采用规范的命名方法，避免含义不明确的缩写，从命名最好就可以一目了然读出命名标识的含义和数据类型。 (4) 采用缩进格式，突出程序的逻辑层次结构。 (5) 每一行只写一条语句，使用括号间隔表达式或语句的组成部分，使组成部分清晰； (6) 使用结构化、面向对象的编程技术，提高程序可重用性、可扩充性。 (7) 除非完全必要，应尽量避免多任务和多重处理。 (8) 尽量避免使用复杂的算术和逻辑表达式。 (9) 提高程序健壮性，预防用户的操作错误，做到废进废出。 10高级语言程序的运行 使用高级语言编制程序的一般过程可以归纳为以下几个步骤： (1) 使用文本编辑工具，逐条编写源程序的语句。存储源程序文件时文件的后缀名与所用的高级语言有关。 (2) 编译源程序文件，生成目标文件，文件后缀名通常为 (3) 链接目标文件，生成可执行文件，文件后缀名通常为 (4) 在计算机上执行可执行程序文件，进 步调试和维护。 结构化程序设计方法 采用 自顶向下、逐步求精 的设计方法和单入口单出口的控制结构。 1. 结构化程序设计思想 . . . . . . 二级子问题 二级子问题 二级子问题 需要解决的复杂问题 三级子问题 三级子问题 三级子问题 . . . . . . . . . 最小问题 最小问题 最小问题 结构化程序设计的 原则 是： (1) 使用顺序、选择、循环 3种基本控制结构表示程序逻辑。 (2)程序语句组织成容易识别的语句模块，每个模块都是单入口、单出口。 (3)严格控制 (a) 顺序结构 (b) 选择结构 (c) (d) A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假 真 入口 A S 2模块 一个复杂的问题可以划分为多个简单问题的组合。 在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。 模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。 1面向对象的思想 向对象的程序设计方法 向对象 )的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性 (静态特征 )和行为 (动态特征 )，形成类。 2对象和类 对象 是对现实问题的高度概括、分类和抽象。每个对象都只有自己的数据和相应的处理函数，整个程序是由一系列相互作用的对象来构成，不同对象之间是通过发送消息来实现相互联系、相互作用。 方法 在对象内的操作通常叫做方法。 类 定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。 对象则是类的具体化，是类的实例。 类通过派生可以有子类，同样也可以有父类，形成层次结构。 3抽象 抽象 是对具体事物 (即对象 )进行概括，即忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而抽象出一类对象的共性并加以描述。 对一个问题的抽象一般来讲应该包括两个方面：数据抽象和代码抽象 (或称为行为抽象 )。 4封装性 封装的两个含义 ： 第一是，将抽象得到的数据成员和代码成员相结合，形成一个不可分割的整体，即对象，这种数据及行为的有机结合也就是封装。 第二个含义称为信息隐蔽，即尽可能隐蔽对象的内部细节。在隐蔽对象内部细节的同时，对象需要提供与外部世界进行交流的接口，并实现对数据访问权限的合理控制，把整个程序中不同部分的相互影响减少到最低限度。 5继承性 继承性 是父类和子类之间共享数据和方法的机制。在定义一个类的时候，可以以一个已经存在的类为基础，并把这个已经存在的类所包含的属性和方法作为自身的一部分，然后加入新的属性和方法以区别于原来的类。 原有的类称为 基类或父类 ，产生的新类称为 派生类 。 6多态性 多态性 在收到外部消息时，对象通常要予以响应。不同的对象收到同一消息可能产生完全不同的结果。 1数据、数据类型 数据 是对客观事物的符号表示。在计算机系统内，数据通常是指能够输入到计算机中并被计算机进行处理的符号的集合。 数据类型 是指具有相同取值范围和可以实施同种操作的数据的集合的总称。例如，在程序设计中，通常会有字符型、整型、数组等多种数据类型。 基本概念 数据结构 2数据元素、数据项、数据对象 能够独立并完整地描述客观世界实体的基本数据单元称为 数据元素 ，它是组成数据的基本单位。 数据项 是组成数据元素的不可分割的最小单位。最简单的数据元素就是由一个数据项构成的。 同类数据元素的集合称为 数据对象 。 3数据结构 数据结构 是指数据元素之间的相互关系的集合，包括了数据的逻辑结构、物理结构以及数据的运算。 数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系。数据之间可以根据不同的关系组成不同的数据结构。 线性结构 数据结构中，如果数据元素之间存在着前后顺序的关系，即除了第一个数据元素和最后一个元素外，其他每个元素都有惟一的一个前驱和一个后继元素，这样的数据元素之间的关系被称为线性结构。 树形结构 数据结构中，如果数据元素之间有顺序关系，且除了一个被称为根节点的元素外，每个元素都有一个前驱节点，并且可以有多个后继节点，这种逻辑结构称为树形结构。 图形结构 数据结构中，如果任何一个数据元素都可以有多个前驱节点和多个后继节点，这种逻辑结构称为图形结构。 (2) 数据的物理结构 数据的物理结构是指逻辑结构在计算机存储器中的表示。数据的物理结构不仅要存储数据本身，还要存储表示数据间的逻辑关系。 数据的物理结构主要有四种，分别是顺序结构、链表结构、索引结构及散列结构。 顺序结构 把所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。 顺序存储结构常借助于程序设计语言中的数组来实现。优点是使用方法简单，缺点是必须预先分析出所需定义数组的大小。 链表结构 对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针域来实现，由此得到的存储表示称为链式存储结构。 链式存储结构通常借助于程序设计语言中的指针来实现。 索引结构 针对每个数据结构建立一张所谓的索引表，每个数据元素占用表中的一项，每个表项包含一个能够惟一识别一个元素的关键字和用以指示该元素的地址指针。 散列结构 通过构造相应的散列函数，由散列函数的值来确定元素存放的地址。 (3) 数据运算 数据操作的集合。常见的数据操作有数据的插入、删除、查找、遍历等。 数据操作通常由计算机程序加以实现，通常也叫 算法实现 。 线性表 1定义 线性表 是由有限个相同的数据元素构成的序列，元素之间是一对一的线性关系，除了第一个元素只有直接后继、最后一个元素只有直接前驱外，其余数据元素都有一个直接前驱和一个直接后继，如图。 元素 1 u a n s u 元素 2 1 元素 3 1 元素 n 1 2运算和实现 线性表通常采用顺序和链表两种物理实现。对于经常变化的表，通常采取链表结构。线性表常用的运算主要有：插入、删除、查询和遍历。 插入 在保持原有的存储结构的前提下，根据插入要求，在适当的位置插入一个元素。插入操作要求线性表要有足够的存放新元素的空间，如果空间不足，插入操作无法进行，线性表会溢出。 删除 在线性表中，找到满足条件的数据元素，并删除。如果线性表为空，删除就会失败。 查询 在线性表中，按照查询条件，定位数据元素的过程就是查询。查询的条件一般根据数据元素中的关键字进行。实际上，数据的插入和删除都需要首先定位数据元素。对于空的线性表是无法查询的。 遍历 是指按照某种方式，逐一访问线性表中的每一个数据元素，并执行相同处理的操作。这里的处理可以是读、写、或查询等。 栈 1定义 对于由 果只允许在其固定的一端位置插入和删除一个数据元素，那么这种逻辑结构的数据结构称为 堆栈或栈 ( 允许插入或删除的这一端称为 栈项 ，另一个固定端称为 栈底 。当表中没有元素时称为 空栈 。 2运算和实现 栈的基本运算主要有：入栈、出栈和判断。 入栈 入栈也叫压栈，是在栈顶添加新元素的操作，新的元素入栈后成为新的栈顶元素。 出栈 出栈也叫退栈或弹栈，是将栈顶元素从栈中退出并传递给用户程序的操作 D C B A 入栈数据元素 E E D C B A D C B A 出栈数据元素 D C B A 判断 判断操作用来检查栈内数据是否为空，返回结果是一个逻辑值：真或假。如果栈顶和栈底重合，说明堆栈为空。 队列 1定义 对于由 果在其固定的一端只允许插入数据元素，且在另一端只允许删除数据元素，则这种逻辑结构的数据结构称为 队列 ( 把允许插入的一端叫 队尾 (把只允许删除的一端叫 队首 ( 2运算 队列的基本运算主要有：入队、出队和判断。 入队 入队是在队列中插入一个新数据元素的过程，插入在队尾进行，新的元素成为队尾，。 出队 出队是在队列中删除一个数据元素的过程，删除在队首进行并把出来的数据传递给用户程序。 A B C D E 头指针 尾指针 A B C D E F G 头指针 尾指针 F ， G 入队 A B C D E 头指针 尾指针 D E F G 头指针 尾指针 A ， B ， C 出队 判断： 判断操作用来检查队列是否为空，返回结果是一个逻辑值：真或假，如图。 头指针 尾指针 3循环队列的实现 F G A B C D E 头指针 尾指针 内存块第一个存储单元 内存块最后一个存储单元 队列移动 树 1定义 树形数据结构中，每个数据元素称为是一个节点，除了一个惟一的所谓 根节点 外，其他每个节点都有且只有一个父节点，每个元素可以有多个子节点。 树主要用在大型、动态列表的搜索，人工智能系统和编码算法等问题中。 2运算 树常见的基本运算有：插入、删除和遍历。 插入 在树中合适的位置，添加一个节点，通常插入新的节点后，仍然应该保持该树本身所具有的性质。 删除 在树中找到满足条件的节点并删除。通常删除节点后，也要保持该树本身所具有的性质。 遍历 按照某种顺序或规则，对树中的每个节点逐一进行访问的过程。 3实现 A B C D E F 图 1定义 在图形结构中，每个数据元素称为一个顶点，任意两个顶点之间都可能相关，这种相关性用一条边来表示，顶点之间的邻接关系可以是任意的。 图可以用来描述计算机网络的拓扑结构，以及图论中获得最小生成树。除此以外，图在自然科学、社会科学和人文科学等许多领域也都有着非常广泛的应用。 2运算 常见的基本运算有：添加顶点、删除顶点、添加边、删除边和遍历图。 添加顶点 在图中添加新的顶点，新添加的顶点通常是孤立的节点，还没有边连接。 删除顶点 在图中去掉一个顶点，显然，在去掉一个顶点的同时还应该删除与该顶点所连接的边。 添加边 根据指定的顶点，添加相应的边。 删除边 根据指定的顶点，删除相应的边。 遍历图 按照一定的规则，对图中的每个数据顶点逐一进行访问。 3实现 图通常用数组和链表两种结构加以实现。对于各个顶点和顶点之间的关系分别采用邻接矩阵和邻接列表来进行描述。 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E ( a ) ( b ) ( c ) 概述 1算法的定义 准确地说，“ 算法 (一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。 算法和数据结构之间存在密切联系。数据结构是算法的基础，数据结构的不同，通常的采用的算法也会不同；当问题的求解算法一旦确定，也可以选择合适的数据结构加以实现，合理的数据结构能够简化算法。 算法分析基础 (1) 有穷性 (可终止性 ) 一个算法必须在有限个操作步骤内以及合理的时间内执行完成。 (2) 确定性 算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。 (3) 有效性 (可执行性 ) 算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。 (4) 输入及输出 一个算法应该有零个或多个输入数据、有 1个或多个输出数据。 2算法的特性 3算法的描述 (1) 自然语言表示 自然语言就是人们日常使用的语言，可以是中文、英文等。 例如，求三个数中最大值的问题，可以描述为： 比较前两个数； 将中较大的数与第三个数进行比较； 步骤中较大的数即为所求。 (2) 流程图表示 流程图是用规定的一组图形符号、流程线和文字说明来表示算法的一种表示方法。 (3) 伪码 伪码用一种介于自然语言与计算机语言之间的文字和符号来描述算法。比计算机语言形式灵活，格式紧凑，没有严格的语法。 (4) 程序设计语言形式 算法也可以用某种具体的计算机程序设计语言来表示，如， C、 C+、 例如，求两个数的较大者。用伪代码描述算法如下： s:a,b 1. a is or to b) a b 常用算法介绍 1递归算法 如果一个过程直接或间接地调用它本身，则称该过程是递归的。 例如，数学阶乘运算，可以用递归算法定义函数 f (n)如下： 1!( 1 ) ! 递归的情况包括所谓的递推法和分治法。 递推 是从已知的初始条件出发，逐次推导出最后所求的值。递推是利用问题本身所具有的一种递推关系求解问题的一种方法。 分治法 也是一种广泛使用的算法设计方法。其基本思想是把大问题分解成一些较小的问题。然后由小问题的解方便地构造出大问题的解。 2迭代算法 所谓迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都从原来的解值的基础上推出一个新的解值。新的解值比原来的解值更加接近真实的解。这个过程不断重复，直到计算得到的解与真实解的误差满足实际要求。 迭代常常用于科学计算领域对某些无法直接求解的数值问题。 例如：现欲求解方程 f(x)=0的解。首先用某种数学方法导出等价的形式 x=g(x)，然后按以下步骤执行： (1)选一个方程的近似根，赋给变量 (2)将 后计算 g(并将结果存于变量 (3)若 复步骤 (2)的计算。 如果方程有解，并且按照上述方法计算出来的近似根序列数学上收敛，则按上述方法求得的 3穷举算法 亦称枚举法，该算法首先根据问题的部分条件确定问题解的大致范围，然后在此范围内对所有可能的情况逐一进行验证，直到全部情况验证完毕。 4贪婪算法 贪婪算法通常具有 贪婪选择性 和 最优子结构性 。 贪婪选择性 指的是所求解问题的整体最优解可以通过一系列局部最优的选择，即贪婪选择来达到。 最优子结构性 指的是一个问题的最优解往往包含着它的子问题的最优解。 现在我们假设顾客同样希望找回总额为 16的硬币。但是银行发行的硬币面额是分别变成了 1、5和 12单位的硬币。按照上述的贪婪法，应该选择 1枚面额 12的硬币，然后选择 4枚面额为 1的硬币，硬币总数为 5。而最优解应该是选择 3枚面额为 5的硬币，然后选择 1枚面额为 1的硬币，总数为 4。此时，贪婪法的结果就不等于最优解了。 算法的评价 对于一个算法的评价，通常要从 正确性、可理解性、健壮性、时间复杂性及空间复杂性 等多个方面加以衡量。相比而言，人们更关心的是与计算机系统资源密切相关的时间复杂性和空间复杂性。 在计算机系统内，求解问题的算法耗费的资源主要包括时间和空间，可以从分析算法的时间开销和空间开销入手，来分析算法的时间复杂性及空间复杂性。 1算法的时间复杂度 时间复杂度 (度量时间复杂性、即算法的时间效率的指标。时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。 为了简化问题，通常，用算法运行某段核心代码的 次数 来代替准确的执行时间，记为 T(n)，其中， 般是指待处理的数据量的大小。 引入符号“ O”，以此简化时间复杂度 T(n)与求解问题规模 化后的关系是一种数量级关系。 时间复杂度最好的算法是常数数量级的算法。常数数量级的算法表示为 O (c)，其中 例如，如果某个算法的时间复杂度为 T(n)=n，那么，当求解规模趋于 T(n)/ ，表示算法的时间复杂度与 为T(n)=O( 多项式函数的时间复杂度有 O (n)， O ( O ( O (等，以及数量级介于上述数量级之间的 O ( O (n* O (n2*等。 2算法的空间复杂度 算法的 空间复杂度 (用来度量算法的空间复杂性、即执行算法的程序在计算机中运行时所占用空间的大小。 简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。记为 S(n)，其中 符号“ O”同样被用来表示空间复杂度 S(n)与求解问题规模 例如，如果 S(n)= O(表示算法的空间复杂度与 为 S(n)=O( 空间复杂度的分析方法与时间复杂度的分析也是类似的，往往希望算法有常数数量级或多项式数量级的空间复杂度。 题，是非确定型多项式问题。所谓的非确定型，简单讲就是指算法无法直接计算出结果，只能通过进行一些有选择的“猜算”来得到结果。 对于这类问题给出的算法并不能直接计算出结果，但可以检验某个可能的结果是正确的还是错误的。这个可以检验“猜算”的答案正确与否的算法，如果可以在多项式时间内解出，就是非确定型多项式 (题。 例如，找一个大的质数的问题。并不存在一个公式可以用来推算并找到这个大的质数，但是，如果事先给定一个数，程序却可以在多项式时间内判断出它是否满足要求。 检验一个问题是否属于 果在多项式时间内能够证明该问题的任意“是”的实例是正确的，则该问题即为 目前关于 为典型的有装箱问题、背包问题、着色问题等等。 这些问题的研究结果有两种可能，一种是找到了求解问题的算法；另外一种就是求解问题的算法是不存在的，那么就要从数学理论上证明它为什么不存在。 编译程序概述 语言处理的过程如图所示。 编译原理 汇编器 绝对机器码 装配连接编辑 编译器 目标汇编程序 可重定位机器代码 预处理器 骨架程序 源程序 可重定位目标文件库 编译程序的功能如图所示。 编译程序 低级语言程序 高级语言程序 解释程序在处理源程序时，执行方式类似于日常生活中的“同声翻译”。 解释一句、执行一句，立即产生运行结果。解释程序不产生目标代码，不能脱离其语言环境独立执行。 解释程序对源程序的解释执行比编译程序产生的目标代码程序的执行速度要慢。 编译程序是把高级语言程序 (源程序 )作为一个整体来处理，首先将程序源代码“翻译”成目标代码 (机器语言 )，编译后与系统提供的代码库链接，形成 个完整的可执行的机器语言程序 (目标程序代码 )。 目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。相应地，由于每次执行之前必须通过编译得到可执行程序，所以，可执行程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件 (*能执行。 词法分析器语法分析器语义分析器中间代码生成优化目标代码生成源程序 目标代码 表格管理 出错处理 词法分析 其任务是从左到右一个字符、一个字符地对源程序进行扫描，读入源程序，对构成源程序的字符流进行扫描和分解，通过词法分析从而识别出一个个单词 (也称单词符号或符号 )。 例 对表达式： = 100；进行词法分析。 对其进行词法分析后得到以下结果： 单词类型 单词值 标识符 1( 算符 (赋值 ) := 标识符 2( 算符 (加 ) + 标识符 3( 算符 (乘 ) * 整数 100 分号 ； 语法分析 语法分析是编译过程的第二个阶段，任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等等。一般这种语法短语也称为语法单位。 例 按照例 表达式： = 100；进行语法分析。 语法规则： :=“:=” :=“+” :=“*” :=“(”