录像版dajiu03mooc问题求解与算法

1、 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 2 课程简介课程简介 n课程定位课程定位 计算机公共教学核心课程计算机公共教学核心课程 大学通识教育类核心课程大学通识教育类核心课程 n教学目标教学目标 l 培养学生信息素养培养学生信息素养 l 培养学生计算思维培养学生计算思维 l 传授计算科学知识传授计算科学知识 n授课对象授课对象 l 非计算机类各专业本科生非计算机类各专业本科生 第第1章章 绪论绪论 第第2章章 计算与计算机计算与计算机 第第3章章 问题求解与算法问题求解与算法 第第4章章 数据与数据结构数据与数据结构 第第5章章 计算机程序计算机程序 第第6章章

2、 计算机网络计算机网络 第第7章章 计算科学前沿计算科学前沿 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 3 第第3章章 问题求解与算法问题求解与算法 3.1 问题与问题求解问题与问题求解 3.2 算法与算法分析算法与算法分析 3.3 算法设计及算法分类算法设计及算法分类 3.4 搜索问题与查找算法搜索问题与查找算法 3.5 排序问题及排序算法排序问题及排序算法 3.6 网络搜索问题网络搜索问题 知识要点知识要点 问题，问题， 问题求解，问题求解， 问题归约，问题归约， 与或图，与或图， 基元问题，基元问题， 问题求解系统，问题求解系统， 问题求解策略，问题求解策略

3、， 算法式，算法式， 启发式，启发式， 问题解决过程，问题解决过程， 抽象，数学模型，数学建模，哥尼抽象，数学模型，数学建模，哥尼 斯堡七桥问题斯堡七桥问题 计算机求解问题概念模型。计算机求解问题概念模型。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 4 U3.1 问题与问题求解问题与问题求解 n人类问题求解的思维过程人类问题求解的思维过程 n领域问题及形式化描述领域问题及形式化描述 l 问题的形式化表示问题的形式化表示 l 问题归约表示问题归约表示 l 问题求解策略问题求解策略 l 问题求解系统问题求解系统 n问题抽象与数学建模问题抽象与数学建模 n计算机求解问题

4、模型计算机求解问题模型 l 问题解决过程问题解决过程 l 计算计问题求解概念模型计算计问题求解概念模型 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 5 人类问题求解的思维过程人类问题求解的思维过程 n问题及其来源问题及其来源 l 问题是指需要解决还没有解决的事。问题是指需要解决还没有解决的事。 l 来源来源 u社会实践、科学研究中发现和提出问题社会实践、科学研究中发现和提出问题 u他人的任务他人的任务 n问题求解问题求解 l 问题求解是人们为寻求问题答案，对问题及其所处的环境，根据知识和经验、问题求解是人们为寻求问题答案，对问题及其所处的环境，根据知识和经验、 条件

5、、约束而进行的一系列思维活动。条件、约束而进行的一系列思维活动。 l 问题千差万别！问题求解策略不同，手段和方法各异问题千差万别！问题求解策略不同，手段和方法各异 n问题求解思维过程问题求解思维过程 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 6 问题分析问题分析 n对问题给出的条件、目标和任务进行研究，明确问对问题给出的条件、目标和任务进行研究，明确问 题的基本含义。题的基本含义。 n问题分析通常借助于数学、逻辑学等方法，例如：问题分析通常借助于数学、逻辑学等方法，例如： 问题归约、问题抽象、数学建模等，其结果是问题问题归约、问题抽象、数学建模等，其结果是问题 的

6、形式化，或建立一个抽象的问题模型，使问题的的形式化，或建立一个抽象的问题模型，使问题的 描述更加严谨。描述更加严谨。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 7 提出假设提出假设 n当问题分析清楚后，接下来是要寻找问题的答案，当问题分析清楚后，接下来是要寻找问题的答案， 而答案和求解方法都是未知的。而答案和求解方法都是未知的。 n提出假设就是在问题和答案之间寻找解决问题的方提出假设就是在问题和答案之间寻找解决问题的方 法和途径法和途径 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 8 检验假设检验假设 n对提出的假设，进行验证，来检查其

7、是否正确。对提出的假设，进行验证，来检查其是否正确。 n实践检验实践检验 l对问题给定相应的数据，检查假设的结果，看是否正确，对问题给定相应的数据，检查假设的结果，看是否正确， 从而来判断假设的真伪。从而来判断假设的真伪。 l许多物理、化学、生物实验就是这种模式。许多物理、化学、生物实验就是这种模式。 n理论验证理论验证 l假设是不可实验的假设是不可实验的 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 9 领域问题及形式化描述领域问题及形式化描述 n问题的要素问题的要素 l现实，已经具备的条件基础现实，已经具备的条件基础 l目标，对预期结果的描述或一种要求目标，对预期

8、结果的描述或一种要求 n问题形式化问题形式化 问题问题=现实，目标现实，目标 题解题解=目标现实目标现实=A1，A2，An 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 10 问题归约表示问题归约表示 n问题归约问题归约 l对于复杂的问题，直接进行问题求解往往是困难的对于复杂的问题，直接进行问题求解往往是困难的 l问题归约就是对问题进行问题归约就是对问题进行归纳归纳和和简化简化，从而把一个复杂问，从而把一个复杂问 题转换为相对简单的问题。题转换为相对简单的问题。 n三要素三要素 l目标：即问题的初始描述。目标：即问题的初始描述。 l算子集：用来将给定问题变换为若干子问

9、题的操作。算子集：用来将给定问题变换为若干子问题的操作。 l基元问题集：已有解或其解十分明显可以直接描述的问题。基元问题集：已有解或其解十分明显可以直接描述的问题。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 11 与或图与或图 n“或或”节点，原来问题被变换为若干节点，原来问题被变换为若干 子问题，而只需要解决其中之一便子问题，而只需要解决其中之一便 可解决原问题，代表这些子问题的可解决原问题，代表这些子问题的 节点称为相对于原问题的节点称为相对于原问题的“或或”节节 点。点。 n“与与”节点，如果原问题被变换为节点，如果原问题被变换为 缺一不可（均需解决）的若干

10、子问缺一不可（均需解决）的若干子问 题，那么代表这些子问题的节点称题，那么代表这些子问题的节点称 为相对于原问题节点的为相对于原问题节点的“与与”节点，节点， 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 12 问题求解策略问题求解策略-1算法式算法式 n算法式是指按照逻辑来求解问题的策略。如果问题算法式是指按照逻辑来求解问题的策略。如果问题 有解，算法式一定可以得到问题的答案或解。有解，算法式一定可以得到问题的答案或解。 n例如例如 l解一个解一个6个字母的字谜，只要将这个字母的字谜，只要将这6个字母进行全排列，个字母进行全排列， 一定可以找到这个字。为了找到这个字

11、，最坏情况下需一定可以找到这个字。为了找到这个字，最坏情况下需 要尝试要尝试720中不同的排列。中不同的排列。 n常用的算法式策略有：枚举、递归等方法常用的算法式策略有：枚举、递归等方法 n缺点：费时缺点：费时 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 13 问题求解策略问题求解策略-2启发式启发式 n根据以往解决问题的经验形成一些经验规则。启发式不能保根据以往解决问题的经验形成一些经验规则。启发式不能保 证一定得到答案。证一定得到答案。 n例如例如 l 计算机突然不能上网。可能是网线没接好，也可能是网络协议问题，计算机突然不能上网。可能是网线没接好，也可能是网络

12、协议问题， 或者是病毒造成的。或者是病毒造成的。 n常用的启发式策略常用的启发式策略 l 手段目的分析，是指不断地将当前状态和目标状态进行比较，然后手段目的分析，是指不断地将当前状态和目标状态进行比较，然后 采取措施尽可能地缩小这两个状态之间的差异。采取措施尽可能地缩小这两个状态之间的差异。 l 顺向工作，也称顺向推理，是指从问题的已知条件出发，通过逐步顺向工作，也称顺向推理，是指从问题的已知条件出发，通过逐步 扩展已有的信息直到问题解决的一种策略。扩展已有的信息直到问题解决的一种策略。 l 逆向工作，又称逆向推理，是指从问题的目标状态出发，将问题解逆向工作，又称逆向推理，是指从问题的目标状态

13、出发，将问题解 决的目标分解成若干子目标，直至使子目标按逆推途径与给定的条决的目标分解成若干子目标，直至使子目标按逆推途径与给定的条 件建立直接联系或等同起来。件建立直接联系或等同起来。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 14 问题求解系统问题求解系统 n求解问题就是要求解一个问题的结果，或找出一种求解问题就是要求解一个问题的结果，或找出一种 从现实到目标的行动序列，并予以执行。从现实到目标的行动序列，并予以执行。 n问题求解状态图问题求解状态图 l状态状态 l活动活动 n问题的解问题的解 活动序列活动序列A2-A4-A6 大学计算机计算思维的视角（第3版

14、），郝兴伟编著. 北京：高等教育出版社 15 例例3-1汉诺塔问题（汉诺塔问题（Tower of Hanoi Problem） n在印度，有一个古老传说。在世界中心贝拿勒斯的圣庙里，安放着一块黄铜板，在印度，有一个古老传说。在世界中心贝拿勒斯的圣庙里，安放着一块黄铜板， 板上插着三根宝石针。梵天（印度教的主神勃拉玛）在创造世界的时候，在其板上插着三根宝石针。梵天（印度教的主神勃拉玛）在创造世界的时候，在其 中一根针上从下往上放下了由大到小的中一根针上从下往上放下了由大到小的64个金片。这就是所谓梵塔，又称汉诺个金片。这就是所谓梵塔，又称汉诺 塔。塔。 n不论白天黑夜，都有一个值班的僧侣按照梵天

15、不渝的法则，把这些金片在三根不论白天黑夜，都有一个值班的僧侣按照梵天不渝的法则，把这些金片在三根 针上移来移去：一次只能移一片，并且要求不管在哪根针上，小片永远在大片针上移来移去：一次只能移一片，并且要求不管在哪根针上，小片永远在大片 的上面。当所有的的上面。当所有的64片都从梵天创造世界时所放的那根针上移到另外一根针上片都从梵天创造世界时所放的那根针上移到另外一根针上 时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 16 汉诺塔问题求解策略汉诺塔问

16、题求解策略 n汉诺塔问题（汉诺塔问题（Tower of Hanoi Problem） n启发式求解策略启发式求解策略 l 先把上面的先把上面的N-1个盘子从第个盘子从第1根柱子上搬移到第根柱子上搬移到第2根柱子上，根柱子上， l 然后把第然后把第1根柱子上最下面的盘子搬移到第根柱子上最下面的盘子搬移到第3根柱子上根柱子上 l 然后把第然后把第2根柱子上的根柱子上的N-1个盘子搬到第个盘子搬到第3根柱子上根柱子上 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 17 汉诺塔问题解汉诺塔问题解 n汉诺塔问题（汉诺塔问题（Tower of Hanoi Problem） 大学计

17、算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 18 提出问题提出问题 n发现问题，提出问题发现问题，提出问题 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 19 问题分析方法之问题分析方法之-抽象抽象 n抽象的概念抽象的概念 l 抽象（抽象（Abstraction），就是从众多的事物中抽取出共同的、本质性），就是从众多的事物中抽取出共同的、本质性 的特征，而舍弃其非本质的特征。的特征，而舍弃其非本质的特征。 l 抽象是一种重要的思维方法。抽象是一种重要的思维方法。 l 共同特征是指那些能把一类事物与他类事物区分开来的特征，这些共同特征是指那些能把一

18、类事物与他类事物区分开来的特征，这些 具有区分作用的特征又称具有区分作用的特征又称本质特征本质特征。 l 例如，对苹果、香蕉、葡萄等比较，它们共同的特性就是水果，从例如，对苹果、香蕉、葡萄等比较，它们共同的特性就是水果，从 而抽象出水果这一而抽象出水果这一概念概念。 n抽象的层次性抽象的层次性 l 例如，对于在校大学生这一群体，从低到高，我们可以抽象为：大例如，对于在校大学生这一群体，从低到高，我们可以抽象为：大 学生（具有高等学校学历）、学生（学习状态）、年轻人（按照年学生（具有高等学校学历）、学生（学习状态）、年轻人（按照年 龄属性）、人（社会属性）、动物（生物学特征）、生物（生物学龄属性

19、）、人（社会属性）、动物（生物学特征）、生物（生物学 特征）、物质（按哲学观点）等。特征）、物质（按哲学观点）等。 l 从不同的层次去认识和观察事物，是人们分析问题和思维的一部分。从不同的层次去认识和观察事物，是人们分析问题和思维的一部分。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 20 事物抽象的方法事物抽象的方法 n分离，就是暂不考虑研究对象与其它对象的联系，把要研究分离，就是暂不考虑研究对象与其它对象的联系，把要研究 的对象单独的抽取出来进行考察，研究其属性。的对象单独的抽取出来进行考察，研究其属性。 n提纯，就在研究对象的错综复杂的属性和联系中，去掉那些提

20、纯，就在研究对象的错综复杂的属性和联系中，去掉那些 与研究目标关系不大的内容，更好的揭示其本质特征。与研究目标关系不大的内容，更好的揭示其本质特征。 n简略，提纯本身就是一种简化，简略是抽象的最后环节，它简略，提纯本身就是一种简化，简略是抽象的最后环节，它 是对研究对象抽象结果的一种表达。目的都是要表达研究对是对研究对象抽象结果的一种表达。目的都是要表达研究对 象的本质性特性，从而产生一类新的概念。象的本质性特性，从而产生一类新的概念。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 21 数学模型数学模型 n数学模型，对实际问题的数学抽象，用数学符号、数学模型，对实际

21、问题的数学抽象，用数学符号、 数学式子、程序、框图等对实际问题本质属性的抽数学式子、程序、框图等对实际问题本质属性的抽 象而又简洁的刻划，用以描述客观事物的特征、内象而又简洁的刻划，用以描述客观事物的特征、内 在联系及发展和运动规律。在联系及发展和运动规律。 n通过数学模型，可以解释某些客观现象，预测未来通过数学模型，可以解释某些客观现象，预测未来 发展规律，或能为控制某一现象的发展提供某种意发展规律，或能为控制某一现象的发展提供某种意 义下的优化策略。义下的优化策略。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 22 数学建模数学建模 n数学模型是现实问题的抽象，

22、数学模型用数学语言数学模型是现实问题的抽象，数学模型用数学语言 描述了现实问题的特征及其内部联系或与外界的联描述了现实问题的特征及其内部联系或与外界的联 系。系。 n应用知识从实际问题中进行抽象、提炼出数学模型应用知识从实际问题中进行抽象、提炼出数学模型 的过程称为数学建模（的过程称为数学建模（Mathematical Modeling） 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 23 哥尼斯堡七桥问题哥尼斯堡七桥问题 n18世纪初，在普鲁士的哥尼斯堡世纪初，在普鲁士的哥尼斯堡 （德国时期旧称哥尼斯堡（德国时期旧称哥尼斯堡 Koenigsberg，现为俄罗斯的加里

23、，现为俄罗斯的加里 宁格勒，宁格勒，1946年由德国划入前苏年由德国划入前苏 联）的一个公园里，普雷格尔河联）的一个公园里，普雷格尔河 从中穿过，河中有两个小岛，有从中穿过，河中有两个小岛，有 七座桥把两个岛与河岸联系起来七座桥把两个岛与河岸联系起来 n有人提出一个问题：一个步行者有人提出一个问题：一个步行者 怎样才能不重复、不遗漏地一次怎样才能不重复、不遗漏地一次 走完七座桥。走完七座桥。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 24 七桥问题的数学抽象七桥问题的数学抽象 n1736年，年，29岁的欧拉岁的欧拉 向圣彼得堡科学院递交了关于哥尼斯堡七桥问题的向圣

24、彼得堡科学院递交了关于哥尼斯堡七桥问题的 论文论文“与位置几何相关的一个问题的解与位置几何相关的一个问题的解”。在论文中，欧拉将七桥问。在论文中，欧拉将七桥问 题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 并由此得到了如图一样的几何图形并由此得到了如图一样的几何图形 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 25 图论图论 n欧拉把问题归结为如图的欧拉把问题归结为如图的“一笔画一笔画” 问题，证明上述走法是不可能的，即问题，证明上述走法是不可能的，即 从任意一点出发不重复的走遍每一

25、座从任意一点出发不重复的走遍每一座 桥，最后再回到原点是不可能的。桥，最后再回到原点是不可能的。 n在解答问题的同时，欧拉开创了数学在解答问题的同时，欧拉开创了数学 的一个新的分支的一个新的分支图论（图论（Graph Theory）。图论的创立，为人们问题）。图论的创立，为人们问题 求解提供了一种新的数学理论和工具。求解提供了一种新的数学理论和工具。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 26 模型的分类模型的分类-1按特性分（按特性分（1） n静态模型和动态模型静态模型和动态模型 l静态模型是指要描述的系统各量之间的关系是不随时间静态模型是指要描述的系统各量

26、之间的关系是不随时间 的变化而变化的，即与时间变量无关，一般都用代数方的变化而变化的，即与时间变量无关，一般都用代数方 程来表达。程来表达。 l动态模型是指描述系统各量之间随时间变化而变化的规动态模型是指描述系统各量之间随时间变化而变化的规 律的数学表达式，一般用微分方程或差分方程来表示。律的数学表达式，一般用微分方程或差分方程来表示。 n连续时间模型和离散时间模型连续时间模型和离散时间模型 l时间变量是在一定区间内变化的模型称为连续时间模型，时间变量是在一定区间内变化的模型称为连续时间模型， 用微分方程描述用微分方程描述 l将时间变量离散化，所获得的模型称为离散时间模型，将时间变量离散化，所

27、获得的模型称为离散时间模型， 用差分方程描述用差分方程描述 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 27 模型的分类模型的分类-1按特性分（按特性分（2） n参数模型与非参数化模型参数模型与非参数化模型 l 参数模型是指可以采用有限个参数进行描述的数学模型，并给定模参数模型是指可以采用有限个参数进行描述的数学模型，并给定模 型参数的值域。型参数的值域。 l 非参数模型是指系统的数学模型中非显式地包含可估参数。非参数模型是指系统的数学模型中非显式地包含可估参数。 n集中参数模型和分布参数模型集中参数模型和分布参数模型 l 集中参数模型是指描述系统的特征、动态不随空

28、间坐标变化的模型，集中参数模型是指描述系统的特征、动态不随空间坐标变化的模型， 通常把系统看作一个整体，只研究输入与输出之间的拟合关系，而通常把系统看作一个整体，只研究输入与输出之间的拟合关系，而 对系统内部的过程和机理不予考虑，即把所有要素都看作属于空间对系统内部的过程和机理不予考虑，即把所有要素都看作属于空间 一个点。一个点。 l分布参数模型则是描述系统特征、动态随空间坐标变化分布参数模型则是描述系统特征、动态随空间坐标变化 的模型。的模型。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 28 模型的分类模型的分类-1按特性分按特性分(3) n随机性模型和确定性模

29、型随机性模型和确定性模型 l 确定性模型中变量间的关系是确定的确定性模型中变量间的关系是确定的 l 随机性模型中变量之间的关系是以统计值或概率分布的形式给出的随机性模型中变量之间的关系是以统计值或概率分布的形式给出的 n线性模型和非线性模型线性模型和非线性模型 l 线性模型中各量之间的关系是线性的，可以应用叠加原理，即几个线性模型中各量之间的关系是线性的，可以应用叠加原理，即几个 不同的输入量同时作用于系统的响应，等于几个输入量单独作用的不同的输入量同时作用于系统的响应，等于几个输入量单独作用的 响应之和。响应之和。 l 非线性模型中各量之间的关系不是线性的，不满足叠加原理。非线性模型中各量之

30、间的关系不是线性的，不满足叠加原理。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 29 模型的分类模型的分类-2按数学方法按数学方法 n几何模型几何模型 n图论模型图论模型 n微分方程模型微分方程模型 n线形规划线形规划 n非线性规划模型非线性规划模型 n概率论模型概率论模型 n等等 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 30 模型的分类模型的分类-3按应用领域按应用领域 n经济学数学模型经济学数学模型 n管理学数学模型管理学数学模型 n社会学数学模型社会学数学模型 n地质学数学模型地质学数学模型 n气象学数学模型气象学数学模型 n

31、天文学数学模型天文学数学模型 n工程学数学模型工程学数学模型 n生物学数学模型生物学数学模型 n医学数学模型等医学数学模型等 此阿，还有许多特殊的问题模型，如：交通运输问题模型、经济决策模型等。此阿，还有许多特殊的问题模型，如：交通运输问题模型、经济决策模型等。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 31 数学建模的基本步骤数学建模的基本步骤 n模型准备模型准备 n模型假设模型假设 n模型建立模型建立 n模型求解模型求解 n模型分析模型分析 n模型检验模型检验 n模型应用模型应用 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 32 计

32、算机问题求解计算机问题求解 n数学模型可以对问题进行严谨的形式化描述数学模型可以对问题进行严谨的形式化描述 n计算机系统可以实现问题求解的自动化计算机系统可以实现问题求解的自动化 l计算机的海量存储、高速度，高精度、自动运行和不计算机的海量存储、高速度，高精度、自动运行和不 知疲倦知疲倦 l设备智能化设备智能化 l计算机在各种各样的问题求解中正在发挥越来越重要计算机在各种各样的问题求解中正在发挥越来越重要 的作用的作用 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 33 计算机问题求解概念模型计算机问题求解概念模型 n计算机问题求解概念模型计算机问题求解概念模型 大学

33、计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 34 举例举例1：阿基米德分牛问题：阿基米德分牛问题 n太阳神有一牛群，由白、黑、花、棕四种颜色的公、母牛组成。在太阳神有一牛群，由白、黑、花、棕四种颜色的公、母牛组成。在 公牛中，白牛数多于棕牛数，多出之数相当于黑牛数的公牛中，白牛数多于棕牛数，多出之数相当于黑牛数的1/2+1/3；黑；黑 牛数多于棕牛数，多出之数相当于花牛数的牛数多于棕牛数，多出之数相当于花牛数的1/4+1/5；花牛数多于棕；花牛数多于棕 牛数，多出之数相当于白牛数的牛数，多出之数相当于白牛数的1/6+1/7。在母牛中，白牛数是全体。在母牛中，白牛数是全体

34、 黑牛数的黑牛数的1/3+1/4；黑牛数是全体花牛数；黑牛数是全体花牛数1/4+1/5；花牛数是全体棕牛；花牛数是全体棕牛 数的数的1/5+1/6；棕牛数是全体白牛数的；棕牛数是全体白牛数的1/6+1/7。 n问这牛群是怎样组成的？问这牛群是怎样组成的？ 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 35 问题分析问题分析 n这是一个看起很复杂的问题，问题包含了许多约束条件，求解的量也很这是一个看起很复杂的问题，问题包含了许多约束条件，求解的量也很 多。多。 n为了更好的理解问题的含义，引入数学变量，设：白、黑、花、棕四种为了更好的理解问题的含义，引入数学变量，设：白

35、、黑、花、棕四种 颜色的公牛、母牛数量分别为颜色的公牛、母牛数量分别为x1,x2,x3,x4和和y1,y2,y3,y4，这样可以将要，这样可以将要 求的问题解表示成一个表格求的问题解表示成一个表格 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 36 数学建模数学建模 n在公牛中在公牛中 l白牛数多于棕牛数，多出之数相当于黑牛白牛数多于棕牛数，多出之数相当于黑牛 数的数的1/2+1/3； l黑牛数多于棕牛数，多出之数相当于花牛黑牛数多于棕牛数，多出之数相当于花牛 数的数的1/4+1/5； l花牛数多于棕牛数，多出之数相当于白牛花牛数多于棕牛数，多出之数相当于白牛 数的数

36、的1/6+1/7。 n在母牛中在母牛中 l白牛数是全体黑牛数的白牛数是全体黑牛数的1/3+1/4； l黑牛数是全体花牛数黑牛数是全体花牛数1/4+1/5； l花牛数是全体棕牛数的花牛数是全体棕牛数的1/5+1/6； l棕牛数是全体白牛数的棕牛数是全体白牛数的1/6+1/7。 n根据问题的约束条件，可以建立下列约束根据问题的约束条件，可以建立下列约束 关系关系 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 37 第第3章章 问题求解与算法问题求解与算法 3.1 问题与问题求解问题与问题求解 3.2 算法与算法分析算法与算法分析 3.3 算法设计及算法分类算法设计及算法分

37、类 3.4 搜索问题与查找算法搜索问题与查找算法 3.5 排序问题及排序算法排序问题及排序算法 3.6 网络搜索问题网络搜索问题 知识要点知识要点 算法，算法， 算法描述，算法描述， 流程图，流程图， N-S流程图，流程图， 伪代码，伪代码， 算法分析，算法分析， 算法复杂性，算法复杂性， P问题，问题， NP问题，问题， NP完全问题，完全问题， NP难度问题，难度问题， 时间复杂性。时间复杂性。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 38 U3.2 算法与算法分析算法与算法分析 n算法及其描述算法及其描述 l 算法的特征算法的特征 l 算法描述算法描述 l

38、 算法的正确性算法的正确性 n算法复杂性分析算法复杂性分析 l 时间复杂性分析时间复杂性分析 l P问题与问题与NP问题问题 l 空间复杂性空间复杂性 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 39 算法及其特征算法及其特征 n算法的概念算法的概念 l 算法（算法（Algorithm）一词最早出现在数学中，原意是关于数字的运算）一词最早出现在数学中，原意是关于数字的运算 法则。法则。 l 算法指问题求解的方法及求解过程的描述，是一个精心设计的计算算法指问题求解的方法及求解过程的描述，是一个精心设计的计算 序列，用以解决一类特定的问题序列，用以解决一类特定的问题 。

39、 n算法的特征算法的特征 l 确定性：算法中的每一条指令必须有确定的含义，不能产生二义性。确定性：算法中的每一条指令必须有确定的含义，不能产生二义性。 l 可行性：算法描述的步骤在计算机上是可行的。可行性：算法描述的步骤在计算机上是可行的。 l 有穷性：一个算法必须在执行有穷步后结束，每一步必须在有穷的有穷性：一个算法必须在执行有穷步后结束，每一步必须在有穷的 时间内完成。时间内完成。 l 输入：一个算法可以有零个或多个输入。输入：一个算法可以有零个或多个输入。 l 输出：算法执行过程中或结束后要有输出结果，或者产生相应的动输出：算法执行过程中或结束后要有输出结果，或者产生相应的动 作指令。作

40、指令。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 40 算法描述算法描述-1自然语言描述自然语言描述 n用自然语言将问题的求解步骤清晰的表述出来即用自然语言将问题的求解步骤清晰的表述出来即 可。在步骤描述上，要求语言简练，层次清晰。可。在步骤描述上，要求语言简练，层次清晰。 n为表述方便，每一步可以加上标号，例如为表述方便，每一步可以加上标号，例如Step1， Step2等等 n对于复杂的步骤，可以进行进一步展开，如对于复杂的步骤，可以进行进一步展开，如 Step1.1,Step1.2等等 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 4

41、1 自然语言描述举例自然语言描述举例 n举例举例 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 42 自然语言描述的特点自然语言描述的特点 n采用自然语言描述算法可以较好的描述问题的采用自然语言描述算法可以较好的描述问题的大大 的求解思路的求解思路，对于比较精细的求解步骤自然语言，对于比较精细的求解步骤自然语言 在描述上比较困难。在描述上比较困难。 l例如，对于判断、分支、重复，特别是这些逻辑的嵌例如，对于判断、分支、重复，特别是这些逻辑的嵌 套，自然语言描述时显得不够清晰直观。套，自然语言描述时显得不够清晰直观。 n更具体的更具体的细节细节可以使用流程图和伪代码来描

42、述。可以使用流程图和伪代码来描述。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 43 算法描述算法描述-2流程图描述流程图描述 n流程图（流程图（Flow Diagram） l 由图框和流程线组成的图形，由图框和流程线组成的图形，图框图框表示各种类型的操作，图框中的表示各种类型的操作，图框中的 文字和符号表示操作的内容，文字和符号表示操作的内容，流程线流程线表示操作的先后次序。表示操作的先后次序。 l 流程图可以很好的表达顺序、分支和重复逻辑，可以较好的描述数流程图可以很好的表达顺序、分支和重复逻辑，可以较好的描述数 据处理、算法描述及系统功能描述等据处理、算法描述

43、及系统功能描述等 n流程图常用图形符号流程图常用图形符号 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 44 流程图举例流程图举例 n优点优点 l简单直观，可很好的表达顺序、分简单直观，可很好的表达顺序、分 支和重复逻辑结构，可以很自然的支和重复逻辑结构，可以很自然的 将算法流程图转化成计算机程序。将算法流程图转化成计算机程序。 n不足不足 l对于复杂的算法，流程图手工绘制对于复杂的算法，流程图手工绘制 和修改都比较麻烦和修改都比较麻烦 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 45 N-S流程图流程图 n1973年，美国学者年，美国学者

44、I.Nassi和和B.Shneiderman提出了提出了 一种新的流程图形式，这种流程图完全去掉了流程一种新的流程图形式，这种流程图完全去掉了流程 线，算法的每一步都用一个矩形框来描述，在框内线，算法的每一步都用一个矩形框来描述，在框内 还可以包含其他框的流程图形式。即由一些基本的还可以包含其他框的流程图形式。即由一些基本的 框组成一个大的框，这种流程图又称为框组成一个大的框，这种流程图又称为N-S结构流结构流 程图，又称程图，又称“盒图盒图” nNS图有三种基本结构，分别表示：顺序、选择和循图有三种基本结构，分别表示：顺序、选择和循 环环 大学计算机计算思维的视角（第3版），郝兴伟编著. 北

45、京：高等教育出版社 46 N-S流程结构流程结构 nNS图有三种基本结构，分别表示：顺序、选择和循环图有三种基本结构，分别表示：顺序、选择和循环 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 47 举例举例 n输入输入10个数，求最个数，求最 大值，并输出大值，并输出 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 48 N-S流程图特点流程图特点 nNS图把整个程序写在一个大框图内，这个大框图由图把整个程序写在一个大框图内，这个大框图由 若干个小的基本框图构成。虽然去掉了流程线，但若干个小的基本框图构成。虽然去掉了流程线，但 可读性较差。可读

46、性较差。 n为结构化编程设计，不便于表达面向对象的编程思为结构化编程设计，不便于表达面向对象的编程思 想（受时代局限）想（受时代局限） 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 49 算法描述算法描述-3伪代码描述伪代码描述 n伪代码（伪代码（Pseudocode） l是一种介于自然语言和计算机程序设计语言（是一种介于自然语言和计算机程序设计语言（Pascal、C 语言等）之间的文字和符号来描述算法的工具，并以编语言等）之间的文字和符号来描述算法的工具，并以编 程语言的书写形式来描述算法。程语言的书写形式来描述算法。 l伪代码没有严格的语法规则，只是遵循简单的书写

47、约定伪代码没有严格的语法规则，只是遵循简单的书写约定 n伪代码不是用户和分析师的工具，而是设计师和程伪代码不是用户和分析师的工具，而是设计师和程 序员的工具序员的工具 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 50 伪代码一般的书写形式伪代码一般的书写形式 n每一条指令占一行，指令后不跟任何符号（每一条指令占一行，指令后不跟任何符号（Pascal和和C中语句要以分号中语句要以分号 结尾）；结尾）； n书写上的书写上的“缩进缩进”表示程序中的分支程序结构，用缩进取代传统表示程序中的分支程序结构，用缩进取代传统Pascal 中的中的begin和和end语句和语句和C中

48、的中的“”和和“”来表示程序的块结构可以大大提来表示程序的块结构可以大大提 高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句 相对与其父级模块的语句缩进；相对与其父级模块的语句缩进； n变量名和保留字不区分大小写变量名和保留字不区分大小写 n赋值语句用符号赋值语句用符号表示，表示，xexp表示将表示将exp的值赋给的值赋给x n使用与程序设计语言类似的关键字表达选择、循环结构使用与程序设计语言类似的关键字表达选择、循环结构 l If,if eles,switch l while,do while,for n数组元素的存

49、取有数组名后跟数组元素的存取有数组名后跟“下标下标”表示，结构变量或对象采用变量表示，结构变量或对象采用变量 名后加点和域名方式访问名后加点和域名方式访问 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 51 举例举例-输入三个数，输出其最大值输入三个数，输出其最大值 n问题求解算法的伪代码描述问题求解算法的伪代码描述 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 52 算法描述方法的比较算法描述方法的比较 n自然语言自然语言 l适合描述大的求解思路适合描述大的求解思路 l细节描述上比较麻烦细节描述上比较麻烦 n流程图流程图 l精确描述，适合描

50、述实现细节精确描述，适合描述实现细节 l流程图绘制和修改麻烦流程图绘制和修改麻烦 n伪代码伪代码 l折中了自然语言和流程图的优点，在大的求解思路和具折中了自然语言和流程图的优点，在大的求解思路和具 体细节上都可以使用体细节上都可以使用 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 53 算法分析算法分析 n 传统意义下，就是对算法进行正确性、时间复杂性传统意义下，就是对算法进行正确性、时间复杂性 和空间复杂性的分析，从而来评价算法的优劣，或和空间复杂性的分析，从而来评价算法的优劣，或 估计算法实现后的运行效果。估计算法实现后的运行效果。 n其他评价指标其他评价指标 l

51、在网络化环境下，一个图形图像压缩算法，压缩比就是在网络化环境下，一个图形图像压缩算法，压缩比就是 一种重要的算法性能指标一种重要的算法性能指标 n算法分析通常是对同一类问题的不同求解算法之间算法分析通常是对同一类问题的不同求解算法之间 的性能比较的性能比较 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 54 算法正确性分析算法正确性分析 n计算三角形面积算法计算三角形面积算法 n算法的正确性层次算法的正确性层次 l对于一组数据能够得出正确的结果。对于一组数据能够得出正确的结果。 l对于精心挑选的、苛刻的测试用例算法可以得到正确的对于精心挑选的、苛刻的测试用例算法可以得

52、到正确的 结果。结果。 l对于一切合法的输入数据，算法得到的结果都是正确的。对于一切合法的输入数据，算法得到的结果都是正确的。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 55 时间复杂性时间复杂性 n算法的时间复杂性（算法的时间复杂性（Time Complexity）是指根据该）是指根据该 算法编写的程序在运行过程中，从开始到结束所需算法编写的程序在运行过程中，从开始到结束所需 要的时间。要的时间。 n从算法中选取一种对于所研究的问题来说是基本运从算法中选取一种对于所研究的问题来说是基本运 算的操作作为算的操作作为元操作元操作，以该元操作重复执行的次数，以该元操作

53、重复执行的次数 作为算法的时间度量。例如，排序类算法，用数据作为算法的时间度量。例如，排序类算法，用数据 的比较和移动作为元操作。的比较和移动作为元操作。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 56 时间复杂性分析时间复杂性分析 n定义：设定义：设f(n)和和g(n)是从自然数集到非负实数集的两个函数，如果存在一是从自然数集到非负实数集的两个函数，如果存在一 个自然数个自然数n0和一个常数和一个常数c0，使得，使得nn0，f(n)cg(n)，则记为，则记为f(n)=O(g(n)， 称称g(n)是是f(n)的的上界上界；如果是；如果是nn0，f(n)n0时，可以

54、时，可以 用等号（或大于号、小于号）将用等号（或大于号、小于号）将an与其前面的某些项与其前面的某些项ai（0i=2，nN*） n问题分析问题分析 l从斐波那契数列的定义可知，斐波那契数列的第从斐波那契数列的定义可知，斐波那契数列的第1项为项为1， 第第2项也为项也为2，递推关系是当前项等于前，递推关系是当前项等于前2项之和。因此，项之和。因此， 通过顺推可以得到通过顺推可以得到 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 87 求斐波拉契数列的顺推算法求斐波拉契数列的顺推算法 n算法算法3-5 求斐波拉契数列的顺推算法求斐波拉契数列的顺推算法 n/ 求斐波那契数列

55、第求斐波那契数列第10项的值并输出项的值并输出 nf0=1 nf1=2 nn=2 nwhile (n10) n n fn=fn-1+fn-2 n n=n+1 n nwrite(f9) 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 88 例例3-7:卡车穿越沙漠问题卡车穿越沙漠问题 n一辆重型卡车要穿过一辆重型卡车要穿过800公里的沙漠，已知卡车每公里耗油公里的沙漠，已知卡车每公里耗油1 升，卡车总载油能力为升，卡车总载油能力为400升，显然卡车装满一次油是无法升，显然卡车装满一次油是无法 穿越沙漠的，因此卡车司机需要在沿途建立几个储油点，使穿越沙漠的，因此卡车司机需要

56、在沿途建立几个储油点，使 卡车能够顺利穿越沙漠。卡车能够顺利穿越沙漠。 n要让卡车以消耗最少的汽油穿越沙漠，试问司机沿途最少需要让卡车以消耗最少的汽油穿越沙漠，试问司机沿途最少需 要建立几个储油点？每个储油点需要存储多少汽油？要建立几个储油点？每个储油点需要存储多少汽油？ 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 89 问题分析问题分析 n设沿途设置设沿途设置n个储油点，用倒推法来解决这个问题，个储油点，用倒推法来解决这个问题， 从终点向起点倒推，可以逐一求出每个储油点的位从终点向起点倒推，可以逐一求出每个储油点的位 置及储存量。置及储存量。 大学计算机计算思维的

57、视角（第3版），郝兴伟编著. 北京：高等教育出版社 90 分析分析 n（1）为了消耗最少的汽油，最后一个储油点应该离终点）为了消耗最少的汽油，最后一个储油点应该离终点400 公里，且此处储油公里，且此处储油400升，即储油点升，即储油点m=1处离终点处离终点dist1=400 公里，储油量公里，储油量oil1=400升。升。 n（2）为了在）为了在m=1处储存处储存400升汽油，卡车最少从储油点升汽油，卡车最少从储油点m=2 处开两趟载满油的车到储油点处开两趟载满油的车到储油点m=1处，则储油点处，则储油点m=2处储油处储油 量量oil2=400*2=800升，其中，升，其中，400升用于储存

58、在升用于储存在m=1处，处， 400升用于从升用于从m=2到到m=1处的油料运输。要将处的油料运输。要将400生油从储油生油从储油 点点m=2处运送到到储油点处运送到到储油点m=1处，则从处，则从m=2到到m=1处至少需处至少需 开两趟，需要开三次路程，因此有开两趟，需要开三次路程，因此有dist2=dist1+400/3公里。公里。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 91 分析（续分析（续1） n（3）为了在储油点）为了在储油点m=2处储存处储存800升汽油，卡车最升汽油，卡车最 少从储油点少从储油点m=3处开三趟载满油的车到储油点处开三趟载满油的车到储

59、油点m=2 处，则储油点处，则储油点m=3处储油处储油oil3=400*3=1200升，其升，其 中，中，800升用于储存在升用于储存在m=2处，处，400升用于从升用于从m=3到到 m=2处的油料运输。储油点处的油料运输。储油点m=3处到储油点处到储油点m=2处处 至少开三趟需要开五次路程，因此，至少开三趟需要开五次路程，因此， dist3=dist2+400/5公里。公里。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 92 分析（续分析（续2） n（4）依次类推，为了在）依次类推，为了在m=k处储存处储存oilk=k*400升升 汽油，则储油点汽油，则储油点m=

60、k+1处储油处储油oilk+1=(k+1)*400， 其中其中400升用于往返运送的消耗。要在升用于往返运送的消耗。要在m=k处储存处储存 k*400升油，从升油，从m=k+1处至处至m=k处至少需要处至少需要k+1趟，趟， 最后一次无需返回最后一次无需返回m=k+1处，因此两地往返最小需处，因此两地往返最小需 2(k+1)-1=2k+1次路程，则储油点离终点次路程，则储油点离终点 distk+1=distk+400/(2*k+1)。 大学计算机计算思维的视角（第3版），郝兴伟编著. 北京：高等教育出版社 93 分析（续分析（续3） n（5）最后一个储油点为）最后一个储油点为m=n，它至起点的