“大学计算机基础”课程 5

1、Chapter 5算法基础CS, ZJU9/14/2022Overview算法的概念算法的分类和特性算法的三种结构算法的表示算法的发现常用算法算法的方法数据表达和数据结构2022/9/142计算机科学基础5.1 算法的概念广义地说，为解决问题而采用的方法和步骤就是算法。在计算机中，算法是程序设计的基础，算法的质量直接影响程序运行的效率。根据图灵理论，只要能够被分解为有限步骤的问题就可以被计算机执行。在计算机领域，算法描述主要就是为了能够将算法的步骤变成计算机能够用它的语言所实现的表示方式。算法的正式定义：算法是求解问题步骤的有序集合，它能够产生结果并在有限时间内结束。2022/9/143计算机

2、科学基础5.2 算法的分类和特点算法一般可分成两大类：数值运算算法非数值运算算法特性确定性：算法中的每一个步骤都应该是确定的，不应使不同的编程者对算法中的描述产生不同的理解 有穷性：算法中的步骤应该是有限的，否则计算机就会永远无休止地执行程序有效性：算法中的每一个步骤都应该被有效地执行，并应能得到一个明确的结果可有零个或多个输入有一个或多个输出2022/9/144计算机科学基础5.3 算法的三种结构根据结构化程序设计，所有的程序都由三种结构构成：顺序结构 最简单的一种结构，它使计算机按照命令出现的先后顺序依次执行循环结构使计算机按照设定的条件重复执行一组命令分支结构 在程序执行过程中 ，根据设

3、定的条件来决定程序的执行方向2022/9/145计算机科学基础2022/9/146计算机科学基础顺序结构A B分支结构2022/9/147计算机科学基础（a）While结构 （b） Until结构5.4 算法的表示算法的表示是为了把算法以某种形式加以表达，因此一个算法的表示可以有不同的方法，常用的：自然语言传统的流程图结构流程图伪代码PAD图2022/9/148计算机科学基础2022/9/149计算机科学基础 例：流程图求N！的算法2022/9/1410计算机科学基础求N！的算法例:自然语言2022/9/1411计算机科学基础求N！的算法例：伪代码2022/9/1412计算机科学基础求N！的算

4、法例：伪代码5.5 算法的发现发现算法具有很大的挑战性“中国邮递员问题”：不但要选择路径，而且要确保这个选择的路径是最短的。解决问题的4个步骤：理解问题设计一个解决问题的方案执行这个方案检验这个方案 2022/9/1413计算机科学基础5.6 算法的举例理解常用的算法进而体会算法的发现、设计，是大多数学习计算机的人所采用的学习方法。基本算法求和累积求最大值和最小值求数的位数2022/9/1414计算机科学基础迭代一种建立在循环基础上的算法。举例：“判断一个整数是否为素数”的迭代算法算法思路：素数是指只能被1和它本身整除的数。判断它的方法为：将n（设n是要被判断的整数）作为被除数，用2（n-1）

5、之间的各个整数轮流去除，如果都不能整除，则n是素数。 2022/9/1415计算机科学基础递归递归是算法的自我调用例：求N的阶乘。2022/9/1416计算机科学基础排序迭代的延续应用。是将一组原始数据按照递增或递减的规律进行重新排列的算法。排序不仅用在数值方面，也用在文本处理中。排序规则是递增或递减，其输出是原数据的一种重新排列。常用的方法有：（如果是从小到大排序的话）选择法排序把表中最小的数找到并放入第一个位置，然后比较余下的数，找到次小的数放到第二个位置，直到对所有数据全部扫描过。冒泡法排序。从列表的最后开始比较相邻的两个数，将较小的向前移动，再和前一个相邻的数据比较，同样把较小的数向前

6、移动，直到列表的开始。接着继续这个过程，找到的次小的数排到列表的第二个位置，依次类推，直到结束。2022/9/1417计算机科学基础查找问题把一个特定的数据从列表中找到并提供它所在的位置（即索引）。对于列表数据有两种基本的方法：顺序查找从列表的第一个数据（或叫做元素）开始，但给定的数据和表中的数据匹配时，查找过程结束，给出这个数据所在表中的位置。折半查找也叫二分法，从列表的一半开始，比较列表处于一半（中间）位置的数据，判断是在前半部分还是后半部分（根据列表的排序确定的）。2022/9/1418计算机科学基础5.7 算法的方法学贪心法 分治法 动态规划 回溯法 2022/9/1419计算机科学基

7、础贪心法 贪心算法（Greedy Algorithm）的基本思想是从小的方案推广到大的解决方法。它分阶段工作，在每一个阶段选择最好的方案，而不考虑其后的结果如何。贪心法主要用于求解最优问题，但它已经发展成为一种通用的算法设计技术：核心是：可行性每一步选择必须满足问题的约束；局部最优它是当前可选择的方案中最优的；不可取消性选择一旦做出，在算法的其后步骤中不能被取消。贪心法不能确定得到的最后解是最优的，也不能用于求解最大或最小问题。在算法的效率上，贪心法快速，程序实现需要的内存开销也较小。但遗憾的是，它们往往是不正确的。然而一旦被证明是正确的，其执行效率和速度有很大的优势。2022/9/1420计

8、算机科学基础分治法 基本思想就是，将一个较大规模的问题分解为若干个较小规模的子问题，找出子问题的解，然后把各个子问题的解合并成整个问题的解。分治法的分（Divide）是指划分较大问题为若干个较小问题，递归求解子问题；分治法的治（Conquer）是指从小问题的解构建大问题的解。例： 金块问题2022/9/1421计算机科学基础动态规划 动态规划（Dynamic Programming）被描述为：如果一个较大问题可以被分解为若干个子问题，且子问题具有重叠，可以将每个子问题的解存放到一个表中，这样就可以通过查表解决问题。例：背包问题2022/9/1422计算机科学基础回溯法 回溯法也叫穷尽搜索法（B

9、rute-Force Search），尝试分步地去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的、正确的解答的时候，将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。通常使用递归实现。例：n皇后问题。2022/9/1423计算机科学基础5.8数据表达和数据结构算法最终都需要通过适当的数据表达，以便能够被计算机所处理。数据表达是对数据的符号化表示。数据结构的定义包括三方面内容：逻辑结构、存储结构和对数据的操作。按照它的结构形式可以分为链、表、堆、队、树等。2022/9/1424计算机科学基础数据元素是数据的基本单位，数据元素之间存在某种关联。有三类基本的数据之间的结构，如线性结构：结构中的数据元素存在一对一的关系；树型结构：结构中的数据元素存在一对多的关系；网状结构：结构中的数据元素存在多对多的关系；2022/9/1425计算机科学基础数据的逻辑关系反映的是数据间的关系，是静态的。静态的对象和动态的作用于对象上的操作就构成了数据类型。如何用程序设计语言实现相应的抽象数据类型是数据结构的一个重要问题：对象如何用程序设计语言来表示，即对象逻辑结构的物理实现；对象的操作如何实现，即编写相应的函数；例：队