算法设计-课件.ppt

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

2、设计就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手段有所变化而已。2023-2-4北京大学51 算法的基本概念n1984年图灵奖获得者年图灵奖获得者瑞士科学家尼克劳斯尼克劳斯沃斯沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）1976年出版了算法算法+数据结构数据结构=程序设计程序设计一书，提出了著名的公式：“程序程序 数据结构数据结构 算法算法”。n程序：刻画现实世界，解决现实世界中的问题n程序设计语言：实现的工具n算法：问题的解的描述n数据结构：现实世界的数据模型n程序就是在数据的某些特定的表示方式和结构数据的某些特

3、定的表示方式和结构的基础上对抽象算法抽象算法的具体表述。2023-2-4北京大学61 算法的基本概念n算法的定义n设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为“算法”n算法是一个由一组严格定义的指令组成的过程一个由一组严格定义的指令组成的过程，给定一个出始状态，这个过程能够结束在一个确定终止状态。n大多数算法都可以用程序实现。n常用算法一般都被实现为算法库，供程序员调用。2023-2-4北京大学71 算法的基本概念一个实例：找出一组一个实例：找出一组正整数正整数中的最大的数中的最大的数2023-2-4北京大学81 算法的基本概念n逐步求解，定义算法的动作逐步求解，定义

4、算法的动作nS1:设Largest为第一个数nS2:若第二个数比Largest大，则设Largest为第二个数nS3:若第三个数比Largest大，则设Largest为第三个数nS4:若第四个数比Largest大，则设Largest为第四个数nS5:若第五个数比Largest大，则设Largest为第五个数2023-2-4北京大学91 算法的基本概念n算法动作精化算法动作精化nS0:设Largest为0nS1:若当前数当前数比Largest大，则设Largest为当前数当前数nS2:若当前数比Largest大，则设Largest为当前数nS3:若当前数比Largest大，则设Largest为当

5、前数nS4:若当前数比Largest大，则设Largest为当前数nS5:若当前数比Largest大，则设Largest为当前数2023-2-4北京大学101 算法的基本概念n算法范化算法范化从N个正整数中找出最大数的通用算法nS0:设Largest为0，当前位置p为0nS1:若当前数比Largest大，则设Largest为当前数nS2:若p比N小，则p增加1，返回S1，否则返回Largest2023-2-4北京大学111 算法的基本概念算法的基本性质算法的基本性质n通用性通用性：即适用于某一类问题中的所有个体，而不只是用来解决一个具体的问题。n有效性有效性：即应有明确的步骤一步一步地引导计算

6、的进行。n确定性确定性：即每个步骤都是机械的、有明确定义的动作，不需要计算者临时动脑筋。n有限性有限性：对满足算法要求的输入数据，算法应在有限多步内结束，并给出明确的计算结果。n离散性离散性：算法的输入数据及输出数据都应是离散的符号。2023-2-4北京大学121 算法的基本概念n算法的基本要求n正确n易维护（可读，易修改）n方便使用n高效n速度快 运行时间少，时间复杂度低n占用内存少 空间复杂度低n算法的效率可以测试，用大量输入数据测量运行的时间和占用的内存，通过比较判别和选择效率高的算法。n更重要的是编程前的分析和估计，即理论的计算，给出事前的判断。2023-2-4北京大学131 算法的基

7、本概念n不了解施加于数据上的算法就无法决定如何构造数据；反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。简而言之，程序的构成（算法）程序的构成（算法）与数据结构是两个不可分割地联系在一与数据结构是两个不可分割地联系在一起的问题。起的问题。2023-2-4北京大学142 描述算法的三种基本结构n已经证明，只使用如下三种结构，就可以描述任何算法，且算法结构优良n顺序结构（Sequence）n分支结构（Decision）n循环结构（Repetition）n每一种基本结构分别只有一个入口和一个出口2023-2-4北京大学152.1 顺序结构n顺序结构：动作（语句）动作（语句）序列，顺

8、序执行n动作1n动作2n动作3nn动作n动作动作1动作动作2动作动作3动作动作12023-2-4北京大学162.2 分支结构n分支结构：根据条件条件判断执行什么动作（语句）n如果 条件成立 则n动作1n否则n动作2n分支结束条件成立？条件成立？动作动作1动作动作2是是否否2023-2-4北京大学172.3 循环结构n循环结构：重复执行重复执行一系列动作n当 条件成立 做n动作1n动作2nn动作nn循环结束处条件成立？条件成立？动作动作1动作动作n是是否否2023-2-4北京大学183 流程图表示算法n算法是让人来理解的，因此需要有效的算法表示机制n自然语言表示法n伪代码表达法n流程图表示法流程

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

10、1low=mid+1YYYNNN2023-2-4北京大学424.4 基本算法 迭代与递归n迭代迭代(iterative)与递归与递归(recursive)2023-2-4北京大学431974年图灵奖获得者美国科学家唐纳德克努特(Donad E.Knuth，排版软件的先驱(TEX)）经典巨著计算机程序设计的艺术(The Art of Computer Programming)The Art of Computer Programmingp 卷1为基础运算法则基础运算法则，该书以基本的编程概念和技术为开始，然后讲述信息结构计算机内信息的表示法，数据元素间的结构关系以及处理它们的有效方法。主要应用于

11、模拟、数字方法、符号计算、软件和系统设计。p 卷2对半数值算法对半数值算法领域做了全面介绍，分随机数和算术两章。本卷总结了主要算法范例及这些算法的基本理论，广泛剖析了计算机程序设计与数值分析间的相互联系。p 卷3为分拣和搜索分拣和搜索，它对计算机分拣和搜索的一流技术的最全面的研究，它扩展了卷1中数据结构的处理方法，将数据库以及内存和外部存储都包含在内。2023-2-4北京大学44小结n算法的概念n描述算法的三种基本结构n顺序结构、分支结构、循环结构n算法的流程图表示与算法的程序实现n闰年判断n基本算法介绍n迭代计算：求平方根n排序：选择排序、冒泡排序n二分查找n迭代与递归2023-2-4北京大学45n编程网格。n算法设计练习输入算法。上机练习（第2次上机）