北京大学《计算概论》课件：第七讲-算法

第七讲算法 北京大学信息学院2013年10月 2020 4 19 北京大学 2 主要内容 了解算法的基本概念掌握描述算法的三种基本结构学会算法的流程图描述介绍几种基本算法难 有意思 数学 编程的基础 2020 4 19 北京大学 3 1算法的基本概念 计算机是一个计算工具 它本身不能主动帮助我们做任何事情 需要我们告诉它如何进行计算 程序设计就是要告诉计算机如何进行计算的 这与我们中学时代的数学解题过程是一样的 只不过描述的手段有所变化而已 2020 4 19 北京大学 4 1算法的基本概念 1984年图灵奖获得者瑞士科学家尼克劳斯 沃斯 NiklausWirth Pascal语言的发明者和结构化程序设计创始者 1976年出版了 算法 数据结构 程序设计 一书 提出了著名的公式 程序 数据结构 算法 程序 刻画现实世界 解决现实世界中的问题程序设计语言 实现的工具算法 问题的解的描述数据结构 现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述 一行行代码 语言 2020 4 19 北京大学 5 1算法的基本概念 算法的定义设计程序的目的是为了求解问题 为解决一个问题所采取的方法和步骤 就称为 算法 算法是一个由一组严格定义的动作组成的过程 给定一个出始状态 这个过程能够结束在一个确定终止状态 大多数算法都可以用程序实现 常用算法一般都被实现为算法库 供程序员调用 算法的基本思想 如何把大象关在冰箱里 分3步 第一步 打开冰箱门 第二步 把大象推进冰箱 第三步 关上冰箱门 2020 4 19 北京大学 7 1算法的基本概念 一个实例 找出一组正整数中的最大的数 2020 4 19 北京大学 8 1算法的基本概念 逐步求解 定义算法的动作S1 设Largest为第一个数S2 若第二个数比Largest大 则设Largest为第二个数S3 若第三个数比Largest大 则设Largest为第三个数S4 若第四个数比Largest大 则设Largest为第四个数S5 若第五个数比Largest大 则设Largest为第五个数 2020 4 19 北京大学 9 1算法的基本概念 算法动作精化S0 设Largest为0S1 若当前数比Largest大 则设Largest为当前数S2 若当前数比Largest大 则设Largest为当前数S3 若当前数比Largest大 则设Largest为当前数S4 若当前数比Largest大 则设Largest为当前数S5 若当前数比Largest大 则设Largest为当前数 2020 4 19 北京大学 10 1算法的基本概念 算法范化从N个正整数中找出最大数的通用算法循环结构S0 设Largest为0 当前位置p为0S1 若当前数比Largest大 则设Largest为当前数S2 若p比N小 则p增加1 并返回S1 否则返回Largest 2020 4 19 北京大学 11 1算法的基本概念 算法的基本性质通用性 即适用于某一类问题中的所有个体 而不只是用来解决一个具体的问题 有效性 即应有明确的步骤一步一步地引导计算的进行 确定性 即每个步骤都是机械的 有明确定义的动作 不需要计算者临时动脑筋 有限性 对满足算法要求的输入数据 算法应在有限多步内结束 并给出明确的计算结果 离散性 算法的输入数据及输出数据都应是离散的符号 2020 4 19 北京大学 12 1算法的基本概念 算法的基本要求正确易维护 可读 易修改 方便使用高效速度快运行时间少 时间复杂度低占用内存少 空间复杂度低算法的效率可以测试 用大量输入数据测量运行的时间和占用的内存 通过比较判别和选择效率高的算法 更重要的是可以在编程前进行分析和估计 算法分析 即理论的计算 给出事前的判断 高斯 查字典 2020 4 19 北京大学 13 1算法的基本概念 不了解施加于数据上的算法就无法决定如何构造数据 反之 算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构 简而言之 程序的构成 算法 与数据结构是两个不可分割地联系在一起的问题 2020 4 19 北京大学 14 2描述算法的三种基本结构 计算机科学家已经证明 只使用如下三种结构 就可以描述任何算法 且算法结构优良顺序结构 Sequence 分支结构 Decision 循环结构 Repetition 每一种基本结构分别只有一个入口和一个出口 2020 4 19 北京大学 15 2 1顺序结构 顺序结构 动作 语句 序列 顺序执行 每个动作只执行一次 各动作对执行结果产生的影响是独立的动作1动作2动作3 动作n 动作1 动作2 动作3 动作n 2 1顺序结构 按部就班先来后到循序渐进接连不断 起床刷牙吃早饭上课吃中饭午休上课吃晚饭晚自习洗漱睡觉 2020 4 19 北京大学 16 现实生活中的示例 2020 4 19 北京大学 17 2 2分支结构 分支结构 根据条件判断执行什么动作 序列 最多只有一个动作 序列 被执行如果条件成立则动作 或动作序列 1否则动作 或动作序列 2分支结束 条件成立 动作 序列 1 动作 序列 2 是 否 2 2分支结构 如果分数达到一本线录取到一本大学如果分数达到二本线录取到二本大学如果分数达到三本线录取到三本大学如果分数达到专科线录取到专科学校否则落榜 选择二选一条条道路通罗马如果明天天晴小明就去郊游否则就在家里看书 2020 4 19 北京大学 18 现实生活中的示例 2020 4 19 北京大学 19 2 3循环结构 循环结构 重复执行一系列动作当条件成立做动作1动作2 动作n循环结束处 条件成立 动作1 动作n 是 否 2 3循环结构 周而复始转圈轮回 第几周 如果小于20周如果是周一到周五上课否则休息放寒假 2020 4 19 北京大学 20 现实生活中的示例 一个循环结构示例 求1 1000的平方和 三种基本控制结构可相互组合和嵌套使用 形成更为复杂的控制 完成各种复杂的工作 开始 结束 2020 4 19 北京大学 22 3用流程图表示算法 算法是让人来理解的 因此需要有效的算法表示机制自然语言表示法伪代码表达法流程图表示法 2020 4 19 北京大学 23 3用流程图表示算法 流程图显示了程序的流程判断结构 通常包含如下符号 开始和结束流程线输入和输出处理 动作 条件判断 2020 4 19 北京大学 24 3用流程图表示算法 判断 x 0 y x y x Yes No 2020 4 19 北京大学 25 3用流程图表示算法 循环 k 10 动作 k k 1 Yes No 动作 k 0 吃蟹黄汤包理解算法结构问题1 吃过吗 口诀 轻轻提 慢慢移 先开窗 再喝汤 吃一只蟹黄汤包的 算法 顺序很重要 将包子从蒸笼中轻轻提起 andthen将包子慢慢移动到面前的小碟子中 andthen在包子的正上方咬开一个小口 andthen通过小口吸食包子里的汤 当心别烫着 andthen将包子送入口中 完成 问题2 你如何确保过程无误 假如我们认为在步骤4和5执行前要确保前面的结果是正确的 可以在相应的地方设个 监视哨 guard 问题3 但是我们并不只是吃一只 那怎么办呢 策略一 控制数量 假如规定吃8只 开始 设一个计数器 并将其值设定为0 吃一只汤包 计数器值加1 并判断其是否为8 否 是 结束 注意 计数器的初始值 策略二 吃饱为止 是否已饱 是 否 问题4 如果即使饱了 也希望至少品尝一只 该怎么办 有人知道饱不饱 但有人不知道 开始 要吃汤包的人不到5岁吗 是 选用策略1 选用策略2 否 结束 问题7 如果要判断的不止是两种可能 那怎么办 分类定量控制 2020 4 19 北京大学 34 3用流程图表示算法 判断闰年能被4整除且不能被100整除 能被400整除 2020 4 19 北京大学 35 3流程图表示算法 判断闰年能被4整除且不能被100整除 能被400整除 用C语言实现算法 2020 4 19 北京大学 36 4 1基本算法 日期判断 问题 给定年月日 判断该日是这年的第几天 求解按月累加天数区分大 小月区分闰年 平年 输出 total 4 1基本算法 日期判断 语言实现 2020 4 19 北京大学 38 intyear month day total i scanf d d d 2020 4 19 北京大学 39 4 1基本算法 求平方根 求一个数的平方根 x 迭代公式x1 1xn 1 xn a xn 2迭代计算 直到xn 1 xn的绝对值小于误差要求 例如小于0 00001 即保留小数点后5位 开始 初始化 x2 1 x1 x2 x2 x1 a x1 2 x2 x1的绝对值小于0 00001 N 结束 Y 输出x2 输入数a 2020 4 19 北京大学 40 4 1基本算法 求平方根 C语言实现 2020 4 19 北京大学 41 4 1基本算法 素数判定与歌德巴赫猜想 问题 判定一个数是否为素数求解除2之外 偶数都不是素数对于一个奇数P 看它是否能被某个大于1 小于P的奇数整除 如果存在 则P不是素数 否则P就是素数 初始化 isPrime ture i 3 开始 p能否被 整除 N 结束 Y i i 2 输入 p i half p能否被i整除 Y N Y N P等于 吗 half p isPrime false Y N isPrime false half p 2half sqrt p 输出isPrime 2020 4 19 北京大学 43 intisPrimeNumber intp inti half isPrime 1 if p 2 0 if p 2 returnisPrime isPrime 0 returnisPrime half p half p 2 for i 3 i half i i 2 if p i 0 isPrime 0 break returnisPrime 4 1基本算法 素数判定与歌德巴赫猜想 2020 4 19 北京大学 44 4 1基本算法 素数判定与歌德巴赫猜想 歌德巴赫猜想 任何大于6的偶数都能分成两个奇素数之和问题分析对一个偶数N 把它分解成两个奇数的和分别验证这两个数是否为素数 如果都是 则N满足歌德巴赫猜想 初始化 i 3 开始 结束 i i 2 输入 n i half i和n i是否都为素数 Y Y N half n 2 N 4 1基本算法 素数判定与歌德巴赫猜想 输出 n为素数i和n i之和 2020 4 19 北京大学 46 判断一个偶数是否满足歌德巴赫猜想 4 1基本算法 素数判定与歌德巴赫猜想 voidGoldbachConjecture intn inthalf n 2 求出半数n 2待用inti 循环变量intisPrime1 isPrime2 临时变量for i 3 i half i i 2 isPrime1 isPrimeNumber i isPrime2 isPrimeNumber n i if isPrime1 2020 4 19 北京大学 47 4 2基本算法 排序 排序 Sort 是指对一些数据的重新组织 使得数据由大到小 降序 或者由小到大 升序 存储 排序是很一种基本的要求 我们所感兴趣的是如何寻找到一个好 计算速度快或占用内存少 的办法来进行排序 选择排序冒泡排序 2020 4 19 北京大学 48 4 2排序 选择排序 选择排序 Selectionsort选身高 第一第二 从余下的选最高数据列表被分为两个子列表 已排序和未排序 找到未排序列表中值最小 或最大 的元素 并把它和未排序列表中的第一个元素进行交换 2020 4 19 北京大学 49 4 2选择排序 示例 续 2020 4 19 北京大学 50 4 2选择排序 示例 2020 4 19 北京大学 51 4 2选择排序 算法 程序 先假设A i 是最小的 2020 4 19 北京大学 52 4 2排序 冒泡排序 冒泡排序 Bubblesort数据列表被分为两个子列表 已排序和未排序 未排序列表中最小 或最大 的元素通过冒泡的形式 从后往前冒泡 从未排序列表中交换到已排序列表中 2020 4 19 北京大学 53 4 2冒泡排序 示例 比较 比较并交换 冒泡的过程 2020 4 19 北京大学 54 4 2冒泡排序 示例 续 2020 4 19 北京大学 55 4 2冒泡排序 示例 续 2020 4 19 北京大学 56 4 2冒泡排序 算法 程序 初始化 wall 0 开始 还有未排序的数 N 结束 Y 交换相邻数 还有未冒泡的数 比较相邻数 Y N Y N 4 2基本算法 排序 演示 排序舞 2020 4 19 北京大学 57 2020 4 19 北京大学 58 4 2基本算法 排序 各种排序方法简介 就地排序算法 不增加新的存储空间 1 插入排序法 InsertSort 将一个数插入到序列中的合适位置 2 选择排序法 SelectionSort 每次把最小 大 的元素交换到最前面 3 冒泡排序法 BubbleSort比较并交换相邻的元素 直到所有元素都被放到合适的位置 4 堆排序 HeapSort 一种效率非常高 但原理较复杂的排序方法 5 快速排序算法 QuickSort 一种通常情况下效率非常高 但原理较复杂的排序 2020 4 19 北京大学 59 4 3基本算法 搜索 搜索 Search 是利用给出的关键值 在一个数据集合或数据序列中找出与关键值匹配的一个或一组数据的过程 顺序查找 最简单的查找算法 从数据序列的第一个数据开始 逐个与关键值比较 直到找到一个或所有的匹配数据为止 也可能找不到 顺序查找不要求待查找的数据序列已经排好序 但当待查找数据序列中数据比较多时 顺序查找的效率将十分低 二分查找 二分查找可以提高查找效率 但要求待查找的数据序列已经排好序 以序列中间数据为界将待查找的数据序列分成两个子序列 比较匹配关键值与中间数据的大小 再确定去哪个子序列中继续查找 这样逐步缩小范围 直到找到所需数据 2020 4 19 北京大学 60 4 3基本算法 二分法搜索 二分法搜索 Binarys