算法设计基础ppt课件.ppt

《算法设计基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法设计基础ppt课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析 授课教师：刘志中授课教师：刘志中 QQ:120511193 TEL:15838939240第一章第一章 算法设计基础算法设计基础1234算法的基本概念算法的基本概念为什么学习和研究算法为什么学习和研究算法重要的问题类型重要的问题类型小小 结结 算法及其特性算法及其特性算法是对特定问题求解步骤的一种描算法是对特定问题求解步骤的一种描述，是指令的有限序列。述，是指令的有限序列。算法的特性算法的特性4确定性确定性2输出输出3有穷性有穷性1输入输入5可行性可行性 算法及其特性算法及其特性1输入输入 这些输入通常取自于某个特定的对象的集合这些输入通常取自于某个特定的对象的集

2、合 零个或多个输入零个或多个输入 算法及其特性算法及其特性2输出输出 通常输入与输出之间有着某种特定的关系通常输入与输出之间有着某种特定的关系 有一个或多个输出有一个或多个输出 算法及其特性算法及其特性3有穷性有穷性 必须总是在执行又穷步之后结束，且每一步必须总是在执行又穷步之后结束，且每一步都在有穷时间内完成都在有穷时间内完成 算法及其特性算法及其特性4确定性确定性 算法中每一条指令必须有确切的含义，不存算法中每一条指令必须有确切的含义，不存在二义性；在二义性；在任何情况下，对于相同的输入只能得到相同在任何情况下，对于相同的输入只能得到相同的输出；的输出； 算法及其特性算法及其特性5可行性可

3、行性可以通过程序实现操作；可以通过程序实现操作；Problem Problem 问题问题规定了输入与输出之间的关系，可以用通用语规定了输入与输出之间的关系，可以用通用语言来描述；言来描述；Instance of a Problem Instance of a Problem 问题实例问题实例某一个问题实例包含了求解该问题所需输入；某一个问题实例包含了求解该问题所需输入；输入输入: : 由由n n个数组成的一个序列个数组成的一个序列 输出输出: : 对输入系列的对输入系列的 一个排列一个排列( (重排）重排） ，使得，使得 排序问题的一个实例排序问题的一个实例Input: Input: Outp

4、ut: Output: 算法概念理解算法概念理解: 问题及问题实例问题及问题实例算法的其他特性算法的其他特性4抽象分级抽象分级2健壮性健壮性3可理解性可理解性1正确性正确性5高效性高效性算法的其他特性算法的其他特性1正确性正确性对于任意合法的输入，算法都会得到正确的对于任意合法的输入，算法都会得到正确的结果；结果；算法的其他特性算法的其他特性2健壮性健壮性算法对非法输入的抵抗能力；算法对非法输入的抵抗能力；对错误的输入，算法应能识别并作出处理；对错误的输入，算法应能识别并作出处理；而不产生错误的动作或陷入瘫痪；而不产生错误的动作或陷入瘫痪；危害：美国电话电报公司危害：美国电话电报公司算法的其他

5、特性算法的其他特性3 可理解性可理解性容易理解与实现；容易理解与实现；易于被人理解，易于转换成程序；易于被人理解，易于转换成程序；算法的其他特性算法的其他特性4抽象分级抽象分级对某些具体的细节进行抽象；不过细地描述对某些具体的细节进行抽象；不过细地描述细节；细节；算法步骤太多，会增加算法的理解难度；算法步骤太多，会增加算法的理解难度；算法的其他特性算法的其他特性5高效性高效性时间效率与空间效率；时间效率与空间效率；时间效率时间效率-求解速度；求解速度；空间效率空间效率-额外的存储空间；额外的存储空间；理想目标：较短的执行时间、较少的辅助空间；理想目标：较短的执行时间、较少的辅助空间； 算法的描

6、述方法算法的描述方法4程序设计语言程序设计语言2程序流程图程序流程图3伪代码伪代码1自然语言自然语言 算法的描述方法算法的描述方法1自然语言自然语言 优点：容易书写、容易理解优点：容易书写、容易理解 缺点缺点: (1)歧义性，二义性，不满足确定性；歧义性，二义性，不满足确定性； (2) 自然语言不够简练，导致算法描述过长；自然语言不够简练，导致算法描述过长； (3) 抽象级别高，不易转换成计算机程序抽象级别高，不易转换成计算机程序 算法的描述方法算法的描述方法2程序流程图程序流程图 优点：直观易懂、能够随意表示控制流程；优点：直观易懂、能够随意表示控制流程； 缺点缺点: (1)严密性不如程序设

7、计语言；严密性不如程序设计语言； (2) 灵活性不如自然语言；灵活性不如自然语言； 算法的描述方法算法的描述方法3伪代码伪代码 伪代码是介于自然语言和程序设计语言之间伪代码是介于自然语言和程序设计语言之间的方法；它采用某一程序设计语言的基本语法，的方法；它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。操作指令可以结合自然语言来设计。 伪代码不是一种实际的编程语言，但在表达伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化描述算法能力上类似于编程语言，同时极小化描述算法不必要的细节，是比较合适的算法描述语言，不必要的细节，是比较合适的算法描述语言，被称为被称

8、为“算法语言算法语言”或或“第一语言第一语言”。 算法设计的一般过程算法设计的一般过程1理解问题理解问题 求解目标、已知信息、求解目标、已知信息、 显示条件、隐含条件显示条件、隐含条件 输入什么、输出什么、结果的呈现输入什么、输出什么、结果的呈现 全面准确地理解、分析问题，能够事半功倍全面准确地理解、分析问题，能够事半功倍 算法设计的一般过程算法设计的一般过程2选择算法设计技术选择算法设计技术 算法设计策略；算法设计策略； 本课程所讲解的方法可以用于解决不同领域本课程所讲解的方法可以用于解决不同领域的不同问题；的不同问题； 蛮力法、分治法、减治法、动态规划、回溯等蛮力法、分治法、减治法、动态规

9、划、回溯等 基于这些基本的算法与技术，设计出高效、基于这些基本的算法与技术，设计出高效、智能的好算法！智能的好算法！ 算法设计的一般过程算法设计的一般过程3设计并描述算法设计并描述算法 清楚地描述算法的步骤；清楚地描述算法的步骤； 描述方法：自然语言、流程图、伪代码描述方法：自然语言、流程图、伪代码 本课程：本课程：C+ 与与 自然语言自然语言 -伪代码伪代码 算法设计的一般过程算法设计的一般过程4手工运行算法手工运行算法 计算机比较傻；比较机械，吩咐干啥就干啥计算机比较傻；比较机械，吩咐干啥就干啥 发现不了算法中的逻辑错误；发现不了算法中的逻辑错误； 解决方法：手工运行算法；带入一个具体的事

10、解决方法：手工运行算法；带入一个具体的事例，按照算法流程走一遍；例，按照算法流程走一遍； 实例的选择：尽可能地覆盖多个方面；考虑问实例的选择：尽可能地覆盖多个方面；考虑问题的特殊性；题的特殊性； 算法设计的一般过程算法设计的一般过程5分析算法的效率分析算法的效率 时间效率与空间效率；时间效率与空间效率； 更关注的是时间效率；更关注的是时间效率； 算法性能比较：时间短、效果好！算法性能比较：时间短、效果好！ 算法设计的一般过程算法设计的一般过程6实现算法实现算法 计算机不能直接执行伪代码；计算机不能直接执行伪代码； 算法是需要不断完善和改进的；算法是需要不断完善和改进的； 算法设计的一般过程算法

11、设计的一般过程待求解的问题待求解的问题分析问题分析问题选择算法设计技术选择算法设计技术设计并描述算法设计并描述算法分析算法的效率分析算法的效率手工运行算法手工运行算法根据算法编写代码根据算法编写代码不满意不满意满意满意 算法设计实例算法设计实例 1.2例例1.2求两个自然数的最大公约数求两个自然数的最大公约数求解思路：用短除法找出两个自然数的所有公求解思路：用短除法找出两个自然数的所有公因子，将这些公因子相乘，结果就是这两个数因子，将这些公因子相乘，结果就是这两个数的最大公约数。的最大公约数。 算法设计实例算法设计实例 1.2算法算法1. CommFactor1输入：两个自然数输入：两个自然数

12、m和和n输出：输出：m和和n的最大公约数的最大公约数1. factor=1;2. 循环变量循环变量 i 从从2min(m,n), 执行以下操作；执行以下操作； 2.1 如果如果i是是m 和和 n的公因子，则执行下述操作；的公因子，则执行下述操作； 2.1.1 factor=factor*i; 2.1.2 m=m/i; n=n/i; 2.2如果如果i不是不是m和和n的公因子，则的公因子，则i=i+1；3. 输出输出factor； 算法设计实例算法设计实例 1.2算法算法1. 编程实现编程实现int CommFactor1(int m, int n) int i , factor=1; for(i

13、nt i=2;i=m&i=n;i+) while (m%i=0 &n%n=0) factor=factor*i; m=m/i; n=n/i; return factor;2 为什么要学习和研究算法为什么要学习和研究算法2 算法训练能够提高计算思维能力算法训练能够提高计算思维能力计算机不够智能，不能主动地分析问题解决问题；计算机不够智能，不能主动地分析问题解决问题；需要人的智慧分析问题，形式化地描述问题；采需要人的智慧分析问题，形式化地描述问题；采用抽象思维和逻辑思维设计问题解决方案；用抽象思维和逻辑思维设计问题解决方案；采用抽象思维和逻辑思维设计问题解决方案；采用抽象思维和逻辑思维设计问题解决

14、方案；2 算法训练能够提高计算思维能力算法训练能够提高计算思维能力美国计算机协会与美国电气与电子工程师协会美国计算机协会与美国电气与电子工程师协会（ACM/IEEE-CS）认为计算机专业的基本能力）认为计算机专业的基本能力包括：计算思维能力、算法设计与分析能力、程包括：计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力；序设计与实现能力、系统能力；计算机求解问题的过程中，最重要的环节就是将计算机求解问题的过程中，最重要的环节就是将人的想法抽象为算法；人的想法抽象为算法；算法训练像一种思维体操，能够锻炼我们的思维，算法训练像一种思维体操，能够锻炼我们的思维，使思维变得清晰、更有逻辑；

15、使思维变得清晰、更有逻辑；2 算法研究是推动计算机技术发展的关键算法研究是推动计算机技术发展的关键检索技术检索技术压缩与解压缩压缩与解压缩信息安全与数据加密信息安全与数据加密思考如下问题思考如下问题案例一案例一查找问题查找问题231333231788131723233313233323178132333231781323233317813172323338案例二案例二排序问题排序问题void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; for (j=i-1;r0rj;j-) rj+1=rj; j=j-1; rj+1=r

16、0; 案例二案例二排序问题排序问题案例三案例三图问题图问题案例四案例四组合问题组合问题最小乘车费用最小乘车费用假假 设设 1 2 3 4 5 6 7 8 9 10费费 用用 12 21 31 40 49 58 69 79 90 101 而任意一辆汽车从不行驶超过而任意一辆汽车从不行驶超过10公里。某人想行驶公里。某人想行驶n公里，假设他可公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。案例五案例五几何问题几何问题怎么修围墙满足利用最大化？怎么修围墙满足利用最大化？用计算机求解任何问题离不开程序设计，用计算机求解任何问

17、题离不开程序设计，而程序设计的核心是算法设计。算法对而程序设计的核心是算法设计。算法对程序设计的指导可以延续几年甚至几十程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的年，它不依赖于方法学、语言和工具的发展与变化。发展与变化。算法是计算机的灵魂算法是计算机的灵魂算法可以看作是解决问题的一类特殊方算法可以看作是解决问题的一类特殊方法法它不是问题的答案，而是经过精它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。确定义的、用来获得答案的求解过程。算法是计算机的灵魂算法是计算机的灵魂算法之魂算法之魂速度速度算法研究的核心问题是算法研究的核心问题是时间（速度）问题。时间（速度）问题。