算法设计课件

1、2022/7/28北京大学1上堂课的主要内容程序设计语言（也被称为“编程语言”，Programming Language）是人们描述（编制）程序所使用的规范和方法（语言）。机器语言汇编语言高级语言第六讲 算法设计北京大学 信息科学技术学院2022年7月28日2022/7/28北京大学3主要内容了解算法的基本概念掌握描述算法的三种基本结构学会算法的流程图描述介绍几种基本算法2022/7/28北京大学41 算法的基本概念计算机只是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何进行计算。程序设计就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手

2、段有所变化而已。2022/7/28北京大学51 算法的基本概念1984年图灵奖获得者瑞士科学家尼克劳斯沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）1976年出版了算法+数据结构 = 程序设计一书，提出了著名的公式：“程序 数据结构 算法” 。程序：刻画现实世界，解决现实世界中的问题程序设计语言：实现的工具算法：问题的解的描述数据结构：现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。2022/7/28北京大学61 算法的基本概念算法的定义设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为“算法”算法

3、是一个由一组严格定义的指令组成的过程，给定一个出始状态，这个过程能够结束在一个确定终止状态。大多数算法都可以用程序实现。常用算法一般都被实现为算法库，供程序员调用。2022/7/28北京大学71 算法的基本概念一个实例：找出一组正整数中的最大的数2022/7/28北京大学81 算法的基本概念逐步求解，定义算法的动作S1: 设Largest为第一个数S2: 若第二个数比Largest大，则设Largest为第二个数S3: 若第三个数比Largest大，则设Largest为第三个数S4: 若第四个数比Largest大，则设Largest为第四个数S5: 若第五个数比Largest大，则设Large

4、st为第五个数2022/7/28北京大学91 算法的基本概念算法动作精化S0: 设Largest为0S1: 若当前数比Largest大，则设Largest为当前数S2: 若当前数比Largest大，则设Largest为当前数S3: 若当前数比Largest大，则设Largest为当前数S4: 若当前数比Largest大，则设Largest为当前数S5: 若当前数比Largest大，则设Largest为当前数2022/7/28北京大学101 算法的基本概念算法范化从N个正整数中找出最大数的通用算法S0: 设Largest为0，当前位置p为0S1: 若当前数比Largest大，则设Largest为

5、当前数S2: 若p比N小，则p增加1，返回S1，否则返回Largest2022/7/28北京大学111 算法的基本概念算法的基本性质通用性：即适用于某一类问题中的所有个体，而不只是用来解决一个具体的问题。有效性：即应有明确的步骤一步一步地引导计算的进行。确定性：即每个步骤都是机械的、有明确定义的动作，不需要计算者临时动脑筋。有限性：对满足算法要求的输入数据，算法应在有限多步内结束，并给出明确的计算结果。离散性：算法的输入数据及输出数据都应是离散的符号。2022/7/28北京大学121 算法的基本概念算法的基本要求正确易维护（可读，易修改）方便使用高效速度快 运行时间少，时间复杂度低占用内存少

6、空间复杂度低算法的效率可以测试，用大量输入数据测量运行的时间和占用的内存，通过比较判别和选择效率高的算法。更重要的是编程前的分析和估计，即理论的计算，给出事前的判断。2022/7/28北京大学131 算法的基本概念不了解施加于数据上的算法就无法决定如何构造数据；反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言之，程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。2022/7/28北京大学142 描述算法的三种基本结构已经证明，只使用如下三种结构，就可以描述任何算法，且算法结构优良顺序结构（Sequence）分支结构（Decision）循环结构（Repetit

7、ion）每一种基本结构分别只有一个入口和一个出口2022/7/28北京大学152.1 顺序结构顺序结构：动作（语句）序列，顺序执行动作1动作2动作3动作n动作1动作2动作3动作12022/7/28北京大学162.2 分支结构分支结构：根据条件判断执行什么动作（语句）如果 条件成立 则动作1否则动作2分支结束条件成立？动作1动作2是否2022/7/28北京大学172.3 循环结构循环结构：重复执行一系列动作当 条件成立 做动作1动作2动作n循环结束处条件成立？动作1动作n是否2022/7/28北京大学183 流程图表示算法算法是让人来理解的，因此需要有效的算法表示机制自然语言表示法伪代码表达法流

8、程图表示法2022/7/28北京大学193 流程图表示算法流程图显示了程序的流程判断结构。通常包含如下符号：开始和结束流程线输入和输出处理（动作）条件判断开始/结束处理（动作）流程线输入/输出条件判断2022/7/28北京大学203 流程图表示算法判断x0y = xy = -xYesNo2022/7/28北京大学213 流程图表示算法循环k41455345=452022/7/28北京大学414.3 二分法搜索算法、程序开始返回-1子序列为空？low=0, high=n-1mid=(low+high)/2返回midx =Amid？xAmid？high=mid-1low=mid+1YYYNNN20

9、22/7/28北京大学424.4 基本算法 迭代与递归迭代(iterative)与递归(recursive)2022/7/28北京大学431974年图灵奖获得者美国科学家唐纳德克努特(Donad E.Knuth，排版软件的先驱(TEX) ）经典巨著计算机程序设计的艺术(The Art of Computer Programming)The Art of Computer Programming 卷1为基础运算法则，该书以基本的编程概念和技术为开始，然后讲述信息结构计算机内信息的表示法，数据元素间的结构关系以及处理它们的有效方法。主要应用于模拟、数字方法、符号计算、软件和系统设计。 卷2对半数值算法领域做了全面介绍，分随机数和算术两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。 卷3为分拣和搜索，它对计算机分拣和搜索的一流技术的最全面的研究，它扩展了卷1中数据结构的处理方法，将数据库以及内存和外部存储都包