《计算概论》课件：第七讲算法

1、第七讲 算法北京大学信息学院2013年10月2022/9/23北京大学2主要内容了解算法的基本概念掌握描述算法的三种基本结构学会算法的流程图描述介绍几种基本算法难、有意思、数学、编程的基础2022/9/23北京大学31 算法的基本概念计算机是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何进行计算。程序设计就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手段有所变化而已。2022/9/23北京大学41 算法的基本概念1984年图灵奖获得者瑞士科学家尼克劳斯沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）19

2、76年出版了算法+数据结构 = 程序设计一书，提出了著名的公式：“程序 数据结构 算法” 。程序：刻画现实世界，解决现实世界中的问题程序设计语言：实现的工具算法：问题的解的描述数据结构：现实世界的数据模型程序就是在数据的某些特定的表示方式和结构的基础上对抽象算法的具体表述。一行行代码、语言2022/9/23北京大学51 算法的基本概念算法的定义设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为“算法”算法是一个由一组严格定义的动作组成的过程，给定一个出始状态，这个过程能够结束在一个确定终止状态。大多数算法都可以用程序实现。常用算法一般都被实现为算法库，供程序员调用。算法的基

3、本思想如何把大象关在冰箱里?分3步：第一步：打开冰箱门;第二步：把大象推进冰箱;第三步：关上冰箱门;2022/9/23北京大学71 算法的基本概念一个实例：找出一组正整数中的最大的数2022/9/23北京大学81 算法的基本概念逐步求解，定义算法的动作S1: 设Largest为第一个数S2: 若第二个数比Largest大，则设Largest为第二个数S3: 若第三个数比Largest大，则设Largest为第三个数S4: 若第四个数比Largest大，则设Largest为第四个数S5: 若第五个数比Largest大，则设Largest为第五个数2022/9/23北京大学91 算法的基本概念算法

4、动作精化S0: 设Largest为0S1: 若当前数比Largest大，则设Largest为当前数S2: 若当前数比Largest大，则设Largest为当前数S3: 若当前数比Largest大，则设Largest为当前数S4: 若当前数比Largest大，则设Largest为当前数S5: 若当前数比Largest大，则设Largest为当前数2022/9/23北京大学101 算法的基本概念算法范化从N个正整数中找出最大数的通用算法循环结构S0: 设Largest为0，当前位置p为0S1: 若当前数比Largest大，则设Largest为当前数S2: 若p比N小，则p增加1，并返回S1；否则返

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

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

7、一种基本结构分别只有一个入口和一个出口2022/9/23北京大学152.1 顺序结构顺序结构：动作（语句）序列，顺序执行，每个动作只执行一次，各动作对执行结果产生的影响是独立的动作1动作2动作3动作n动作1动作2动作3动作n2.1 顺序结构按部就班先来后到循序渐进接连不断起床刷牙吃早饭上课吃中饭午休上课吃晚饭晚自习洗漱睡觉2022/9/23北京大学16现实生活中的示例2022/9/23北京大学172.2 分支结构分支结构：根据条件判断执行什么动作（序列），最多只有一个动作（序列）被执行如果 条件成立 则动作（或动作序列）1否则动作（或动作序列） 2分支结束条件成立？动作（序列）1动作（序列）2

8、是否2.2 分支结构如果分数达到一本线录取到一本大学如果分数达到二本线录取到二本大学如果分数达到三本线录取到三本大学如果分数达到专科线录取到专科学校否则落榜选择二选一条条道路通罗马如果明天天晴小明就去郊游否则就在家里看书2022/9/23北京大学18现实生活中的示例2022/9/23北京大学192.3 循环结构循环结构：重复执行一系列动作当 条件成立 做动作1动作2动作n循环结束处条件成立？动作1动作n是否2.3 循环结构周而复始转圈轮回（第几周）如果小于20周 如果是周一到周五上课否则休息放寒假2022/9/23北京大学20现实生活中的示例一个循环结构示例：求11000的平方和S0j1SS

9、+ j*jjj+1j1000打印SYesNo三种基本控制结构可相互组合和嵌套使用，形成更为复杂的控制，完成各种复杂的工作。开始结束2022/9/23北京大学223 用流程图表示算法算法是让人来理解的，因此需要有效的算法表示机制自然语言表示法伪代码表达法流程图表示法2022/9/23北京大学233 用流程图表示算法流程图显示了程序的流程判断结构。通常包含如下符号：开始和结束流程线输入和输出处理（动作）条件判断开始/结束处理（动作）流程线输入/输出条件判断2022/9/23北京大学243 用流程图表示算法判断x0y = xy = -xYesNo2022/9/23北京大学253 用流程图表示算法循环

10、k10动作k=k+1YesNo动作k=0吃蟹黄汤包理解算法结构问题1：吃过吗？口诀：轻轻提, 慢慢移, 先开窗, 再喝汤。吃一只蟹黄汤包的“算法”顺序很重要：将包子从蒸笼中轻轻提起，and then将包子慢慢移动到面前的小碟子中，and then 在包子的正上方咬开一个小口，and then通过小口吸食包子里的汤(当心别烫着)，and then将包子送入口中。完成！问题2：你如何确保过程无误？假如我们认为在步骤4和5执行前要确保前面的结果是正确的，可以在相应的地方设个“监视哨” “guard”。问题3：但是我们并不只是吃一只，那怎么办呢？策略一：控制数量假如规定吃8只：开始设一个计数器，并将其

11、值设定为0。吃一只汤包计数器值加1，并判断其是否为8否是结束注意：计数器的初始值策略二：吃饱为止是否已饱？是否 问题4：如果即使饱了，也希望至少品尝一只，该怎么办？有人知道饱不饱，但有人不知道！开始要吃汤包的人不到5岁吗？是选用策略1选用策略2否结束问题7：如果要判断的不止是两种可能，那怎么办？分类定量控制开始要吃汤包的人不到5岁吗？否参数设为2是结束要吃汤包的人不到60岁吗？参数设为8是参数设为4否选用策略1(带参数)2022/9/23北京大学343 用流程图表示算法判断闰年能被4整除且不能被100整除；能被400整除2022/9/23北京大学353 流程图表示算法判断闰年能被4整除且不能被

12、100整除；能被400整除用C语言实现算法2022/9/23北京大学364.1基本算法 日期判断问题：给定年月日，判断该日是这年的第几天。求解按月累加天数区分大、小月区分闰年、平年初始化：total=0, i=1开始total = total + 31i month？N结束Yi = i+1输入：year, month, dayi是大月？i是小月？total = total + 30YNYNyear是闰年？total = total + 29total = total + 28total = total + day输出：total4.1基本算法 日期判断（语言实现）2022/9/23北京大学38

13、int year, month, day, total, i;scanf(“%d%d%d”, &year, &month, &day);total = 0;for( i=1; imonth; i+) if ( i =1 | i=3 | i=5 | i=7 | i=8 | i=10 | i=12) total = total +31; if ( i =4 | i=6 | i=9 | i=11) total = total +30; if ( i =2) if( (year%4=0&year%100!=0) | year%400=0 ) total = total +29; else total

14、= total +28; total = total + day;2022/9/23北京大学394.1基本算法 - 求平方根求一个数的平方根： x = 迭代公式 x1 = 1 xn+1 = (xn + a/xn)/2 迭代计算，直到 xn+1 xn 的绝对值小于误差要求，例如小于0.00001，即保留小数点后5位。开始初始化：x2=1x1 = x2x2 = (x1 + a/x1)/2x2-x1的绝对值小于0.00001？N结束Y输出x2输入数a2022/9/23北京大学404.1基本算法 - 求平方根(C语言实现)2022/9/23北京大学414.1基本算法 素数判定 与歌德巴赫猜想问题：判定

15、一个数是否为素数求解除2之外，偶数都不是素数对于一个奇数P，看它是否能被某个大于1，小于P的奇数整除，如果存在，则P不是素数，否则P就是素数初始化：isPrime = ture, i = 3开始p能否被整除？N结束Yi = i+2输入：pi half ？p能否被i整除？YNYNP等于吗？half = pisPrime = falseYNisPrime = falsehalf = p/2half = sqrt(p)输出isPrime2022/9/23北京大学43int isPrimeNumber(int p)int i, half, isPrime1;if ( p % 2 = 0 ) if (

16、p = 2 ) return isPrime; isPrime = 0;return isPrime;half = p; / half = p / 2;for( i = 3; i = half; i = i+2 ) if( p % i = 0 ) isPrime = 0;break;return isPrime;4.1基本算法 素数判定 与歌德巴赫猜想2022/9/23北京大学444.1基本算法 素数判定 与歌德巴赫猜想歌德巴赫猜想：任何大于6的偶数都能分成两个奇素数之和问题分析对一个偶数N，把它分解成两个奇数的和分别验证这两个数是否为素数，如果都是，则N满足歌德巴赫猜想初始化：i = 3开始

17、结束i = i+2输入：ni = half ？i和n-i是否都为素数 ？YYNhalf = n/2N4.1基本算法 素数判定 与歌德巴赫猜想输出：n为素数i和 n-i 之和2022/9/23北京大学46判断一个偶数是否满足歌德巴赫猜想4.1基本算法 素数判定 与歌德巴赫猜想void GoldbachConjecture(int n)int half = n/2; / 求出半数n/2待用int i; / 循环变量int isPrime1, isPrime2; / 临时变量for( i = 3; i 41455345=452022/9/23北京大学614.3 二分法搜索算法、程序开始返回-1子序列为空？low=0, high=n-1mid=(low+high)/2返回midx =Amid？x1n=1n14.4 基本算法 迭代与递归2022/9/23北京大学63一个关于递归的故事 一个没有去过北京的人问：天安门是什么样子？去过北京的人答道：天安门有个城楼，城楼上有个国徽，国徽里有个天安门，天安门有个城楼，城楼上有个国