《计算概论》课件:第七讲算法.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《计算概论》课件:第七讲算法.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算概论 计算 概论 课件 第七 算法
- 资源描述:
-
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流程图表示法
展开阅读全文