1精简-计算机算法概述(第一章).pptx

算法分析设计;教材： 算法设计与分析 王晓东编 清华大学出版社 算法设计与分析 吕国英主编 清华大学出版社 参考书： 计算机算法基础 余祥宣等编 华中科大出版社 计算机算法导引——设计与分析 卢开澄编 清华大学出版社 学时：3+1学时/周;与数据结构的区别： 考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。 考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。; 广播操图解是广播操的算法; 菜谱是做菜的算法； 歌谱是一首歌曲的算法； 空调说明书是空调使用的算法等;例1：给出求1+2+3+4+5的一个算法。;第一步 取n=5;;例2：三个牧师和三个野人过河，只有一条能装下两人的船，在河的任一边或者船上，若野人人数大于牧师人数，那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河算法呢？;算法;20 世纪最伟大的科学技术发明---计算机；;现代科学研究的三大支柱;21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在”;本课程为计算机科学与技术学科本科生的专业课。 ; 一般计算机对现实问题无能为力，需要人类对问题抽象化、形式化后才能去机械的执行。;绪 论;1. 什么是算法？ 算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列。 ;2. 算法的五个重要特性 确定性、输入、输出、有穷性/有限性;2）输入 每个算法有0个或多个输入。;3. 程序与算法的区别 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。 ;4.问题求解;;计算gcd(m,n)的短除法 算法设计：计算机没有“宏观”能力来“看出”公约数，但通过“枚举尝试”（逐个尝试）就可以“试出”m,n有哪些是公约数，并将这些公约数“累乘”，就能得到最大公约数。;计算gcd(m,n)的连续整数检测算法;欧几里德算法;算法 = 控制结构 + 原操作 表示算法的语言主要有： 自然语言 流程图 盒图 PAD图 伪代码 计算机程序设计语言;1．自然语言 自然语言是人们日常所用的语言。 自然语言描述算法的缺点： ①自然语言的歧义性易导致算法执行的不确定性。 ②自然语言语句一般太长导致描述的算法太长。 ③当算法中循环和分支较多时就很难清晰表示。 ④不便翻译成程序设计语言理解的语言。; 2．流程图 ;3．盒图（NS流程图） （1）盒图具有以下优点： ① 层次感强、嵌套明确。 ② 支持自顶向下、逐步求精。 ③ 容易转换成高级语言源算法。; PAD图的主要优点： ①设计出来的算法必是结构化的。 ②PAD图描绘的算法结构清晰。 ③用PAD图表现的算法逻辑，易读、易懂、易记。 ④容易用软件工具自动将PAD图转换成高级语言源算法。 ⑤既可用于表示算法逻辑，也可用于描绘数据结构。 ⑥支持自顶向下、逐步求精。 缺点：由于是图形符号书写、编辑、录入不方便。;例：;; 5．伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便，格式紧凑，易于理解，便于用计算机程序设计语言实现。 如：类JAVA/类C/类C＋＋;6．程序设计语言的缺点： ① 算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的，当算法的逻辑流程较为复杂时这个问题就变得更加严重。 ② 特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决。 ③ 要花费大量的时间去熟悉和掌握某种特定的程序设计语言。 ④ 要求描述计算步骤的细节而忽视算法的本质。 ⑤ 需要考虑语法细节，而扰乱算法设计的思路。 ⑥ 考虑到程序设计语言不断更新，不适于描述算法。 算法设计一般不用程序设计语言直接描述。;自然语言 示例：求解斐波那契数 ; 求解斐波那契数;求斐波那契数列的前n个数;求斐波那契数列的前n个数;流程图 示例：求解斐波那契数 ;伪代码 示例：求解斐波那契数 ;算法分析;1. 重要的假设和约定 1）计算机模型的假设