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

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

2、s Wirth，Pascal语言的发明者和结构化程序设计创始者）1976年出版了算法算法+数据结构数据结构=程序设计程序设计一书，提出了著名的公式：“程序程序 数据结构数据结构 算法算法”。n程序：刻画现实世界，解决现实世界中的问题n程序设计语言：实现的工具n算法：问题的解的描述n数据结构：现实世界的数据模型n程序就是在数据的某些特定的表示方式和结构数据的某些特定的表示方式和结构的基础上对抽象算法抽象算法的具体表述。一行行代码、语言2022-10-7北京大学51 算法的基本概念n算法的定义算法的定义n设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为“算法”n算法是一个由一

3、组严格定义的动作组成的过程一个由一组严格定义的动作组成的过程，给定一个出始状态，这个过程能够结束在一个确定终止状态。n大多数算法都可以用程序实现。n常用算法一般都被实现为算法库，供程序员调用。n算法的基本思想算法的基本思想如何把大象关在冰箱里如何把大象关在冰箱里?n分3步：n第一步：打开冰箱门;n第二步：把大象推进冰箱;n第三步：关上冰箱门;2022-10-7北京大学71 算法的基本概念一个实例：找出一组一个实例：找出一组正整数正整数中的最大的数中的最大的数2022-10-7北京大学81 算法的基本概念n逐步求解，定义算法的动作逐步求解，定义算法的动作nS1:设Largest为第一个数nS2:

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

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

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

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

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

9、分支结束条件成立？条件成立？动作（序列）动作（序列）1动作（序列）动作（序列）2是是否否2.2 分支结构n如果分数达到一本线n录取到一本大学n如果分数达到二本线n录取到二本大学n如果分数达到三本线n录取到三本大学n如果分数达到专科线n录取到专科学校n否则n落榜n选择选择n二选一二选一n条条道路通罗马条条道路通罗马n如果明天天晴n小明就去郊游n否则n就在家里看书2022-10-7北京大学18现实生活中的示例现实生活中的示例2022-10-7北京大学192.3 循环结构n循环结构循环结构：重复执行重复执行一系列动作n当 条件成立 做n动作1n动作2nn动作nn循环结束处条件成立？条件成立？动作动作

10、1动作动作n是是否否2.3 循环结构n周而复始n转圈n轮回n（第几周）如果小于20周 n如果是周一到周五n上课n否则n休息n放寒假2022-10-7北京大学20现实生活中的示例现实生活中的示例一个循环结构示例：求11000的平方和S0j1SS+j*jjj+1j1000打印打印SYesNo三种基本控制结构可相互三种基本控制结构可相互组合和嵌套使用，形成更组合和嵌套使用，形成更为复杂的控制，完成各种为复杂的控制，完成各种复杂的工作复杂的工作。开始开始结束结束2022-10-7北京大学223 用流程图表示算法n算法是让人来理解的，因此需要有效的算法表示机制n自然语言表示法n伪代码表达法n流程图表示法

11、流程图表示法2022-10-7北京大学233 用流程图表示算法n流程图显示了程序的流程判断结构。通常包含如下符号：n开始开始和结束结束n流程线流程线n输入输入和输出输出n处理（动作）处理（动作）n条件判断条件判断开始/结束处理（动作）流程线输入/输出条件判断2022-10-7北京大学243 用流程图表示算法n判断x0y=xy=-xYesNo2022-10-7北京大学253 用流程图表示算法n循环k10动作动作k=k+1YesNo动作动作k=0口诀：轻轻提口诀：轻轻提,慢慢移慢慢移,先开窗先开窗,再喝汤。再喝汤。吃一只蟹黄汤包的“算法”n顺序很重要：1.将包子从蒸笼中轻轻提起，and then2

12、.将包子慢慢移动到面前的小碟子中，and then 3.在包子的正上方咬开一个小口，and then4.通过小口吸食包子里的汤(当心别烫着)，and then5.将包子送入口中。完成！假如我们认为在步骤假如我们认为在步骤4 4和和5 5执行前要确保前面的结果是正确执行前要确保前面的结果是正确的，可以在相应的地方设个的，可以在相应的地方设个“监视哨监视哨”“guardguard”。策略一：控制数量假如规定吃8只：开始开始设一个计数器，设一个计数器，并将其值设定为并将其值设定为0。吃一只汤包吃一只汤包计数器值加计数器值加1，并，并判断其是否为判断其是否为8否否是是结结束束注意：注意：计数器的初始值

13、计数器的初始值策略二：吃饱为止是否已饱？是否已饱？是是否否 有人知道饱不饱，但有人不知道！开始开始要吃汤包的要吃汤包的人不到人不到5岁吗？岁吗？是是选用策略选用策略1选用策略选用策略2否否结束结束分类定量控制开始开始要吃汤包的要吃汤包的人不到人不到5岁吗？岁吗？否否参数设为参数设为2是是结束结束要吃汤包的人要吃汤包的人不到不到60岁吗？岁吗？参数设为参数设为8是是参数设为参数设为4否否选用策略选用策略1(带参数带参数)2022-10-7北京大学343 用流程图表示算法n判断闰年n能被4整除且不能被100整除；n能被400整除2022-10-7北京大学353 流程图表示算法n判断闰年n能被能被4

14、 4整除且不能被整除且不能被100100整除；整除；n能被能被400400整除整除用用C语言实现算法语言实现算法2022-10-7北京大学364.1基本算法 日期判断n问题：问题：给定年月日，判断该日是这年的第几天。n求解求解n按月累加天数n区分大、小月n区分闰年、平年初始化：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基本算法 日期判断（

15、语言实现）2022-10-7北京大学38int 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=total+28;total =total+day;2022-10-7北京大学39

16、4.1基本算法-求平方根n求一个数的平方根：求一个数的平方根：x=n迭代公式 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结束Ya输出x2输入数a2022-10-7北京大学404.1基本算法-求平方根(C语言实现)2022-10-7北京大学414.1基本算法 素数判定 与歌德巴赫猜想n问题：问题：判定一个数是否为素数n求解求解n除2之外，

17、偶数都不是素数n对于一个奇数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-10-7北京大学43int isPrimeNumber(int p)int i,half,isPrime1;if(p%2=0)if(p=2)return isPrime;isPrime=0;return isPrim

18、e;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-10-7北京大学444.1基本算法 素数判定 与歌德巴赫猜想n歌德巴赫猜想：歌德巴赫猜想：任何大于6的偶数都能分成两个奇素数之和n问题分析问题分析n对一个偶数N，把它分解成两个奇数的和n分别验证这两个数是否为素数，如果都是，则N满足歌德巴赫猜想初始化：i=3开始结束i=i+2输入：ni=half？i和n-i是否都为素数？YYNhalf=n/2N4.1基本算法 素数判定 与歌德巴赫猜想输出

19、：n为素数i和 n-i 之和2022-10-7北京大学46n判断一个偶数是否满足歌德巴赫猜想4.1基本算法 素数判定 与歌德巴赫猜想void GoldbachConjecture(int n)int half=n/2;/求出半数求出半数n/2待用待用int i;/循环变量循环变量int isPrime1,isPrime2;/临时变量临时变量for(i=3;i 41455345=452022-10-7北京大学614.3 二分法搜索算法、程序开始返回-1子序列为空？low=0,high=n-1mid=(low+high)/2返回midx=Amid？x1n=1n14.4 基本算法 迭代与递归2022

20、-10-7北京大学63一个关于递归的故事一个关于递归的故事 一个没有去过北京的人问：天安门是什么样子？去过北京的人答道：天安门有个城楼，城楼上有个国徽，国徽里有个天安门，天安门有个城楼，城楼上有个国徽，国徽里有个天安门，2022-10-7北京大学64小结n算法的概念n描述算法的三种基本结构n顺序结构、分支结构、循环结构n算法的流程图表示与算法的程序实现n闰年判断n基本算法介绍n迭代计算：求平方根n排序：选择排序、冒泡排序n二分查找n迭代与递归2022-10-7北京大学65书面作业书面作业n用程序流程图描述以下算法：1.输入正整数n，输出n!2.输入大于0的整数n，输出裴波那契数列 的第n个数值裴波那契数列的定义为：裴波那契数列的定义为：F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2)n交作业的方式为将答案写在交作业的方式为将答案写在word文件中，作为邮件的附件发给本文件中，作为邮件的附件发给本班辅导老师。班辅导老师。n3周内交周内交(12.4号前交号前交)