算法设计基础ppt课件.ppt

《算法设计基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法设计基础ppt课件.ppt（42页珍藏版）》请在三一办公上搜索。

1、,算法设计与分析,授课教师：刘志中 QQ:120511193 TEL:15838939240,第一章 算法设计基础,1,2,3,4,算法的基本概念,为什么学习和研究算法,重要的问题类型,小 结, 算法及其特性,算法是对特定问题求解步骤的一种描述，是指令的有限序列。,算法的特性, 算法及其特性,这些输入通常取自于某个特定的对象的集合,零个或多个输入, 算法及其特性,通常输入与输出之间有着某种特定的关系,有一个或多个输出, 算法及其特性,必须总是在执行又穷步之后结束，且每一步都在有穷时间内完成, 算法及其特性,算法中每一条指令必须有确切的含义，不存在二义性；,在任何情况下，对于相同的输入只能得到相

2、同的输出；, 算法及其特性,可以通过程序实现操作；,Problem 问题规定了输入与输出之间的关系，可以用通用语言来描述；Instance of a Problem 问题实例某一个问题实例包含了求解该问题所需输入；,输入: 由n个数组成的一个序列输出: 对输入系列的 一个排列(重排） ，使得,排序问题的一个实例,Input: Output: ,算法概念理解: 问题及问题实例,算法的其他特性,算法的其他特性,对于任意合法的输入，算法都会得到正确的结果；,算法的其他特性,算法对非法输入的抵抗能力；,对错误的输入，算法应能识别并作出处理；而不产生错误的动作或陷入瘫痪；,危害：美国电话电报公司,算法的

3、其他特性,容易理解与实现；,易于被人理解，易于转换成程序；,算法的其他特性,对某些具体的细节进行抽象；不过细地描述细节；,算法步骤太多，会增加算法的理解难度；,算法的其他特性,时间效率与空间效率；,时间效率-求解速度；空间效率-额外的存储空间；,理想目标：较短的执行时间、较少的辅助空间；,算法的描述方法,算法的描述方法,优点：容易书写、容易理解,缺点: (1)歧义性，二义性，不满足确定性； (2) 自然语言不够简练，导致算法描述过长； (3) 抽象级别高，不易转换成计算机程序,算法的描述方法,优点：直观易懂、能够随意表示控制流程；,缺点: (1)严密性不如程序设计语言； (2) 灵活性不如自然

4、语言；,算法的描述方法,伪代码是介于自然语言和程序设计语言之间的方法；它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。,伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化描述算法不必要的细节，是比较合适的算法描述语言，被称为“算法语言”或“第一语言”。,算法设计的一般过程,求解目标、已知信息、,显示条件、隐含条件,输入什么、输出什么、结果的呈现,全面准确地理解、分析问题，能够事半功倍,算法设计的一般过程,算法设计策略；,本课程所讲解的方法可以用于解决不同领域的不同问题；,蛮力法、分治法、减治法、动态规划、回溯等,基于这些基本的算法与技术，设计出高效、智能的

5、好算法！,算法设计的一般过程,清楚地描述算法的步骤；,描述方法：自然语言、流程图、伪代码,本课程：C+ 与 自然语言 -伪代码,算法设计的一般过程,计算机比较傻；比较机械，吩咐干啥就干啥,发现不了算法中的逻辑错误；,解决方法：手工运行算法；带入一个具体的事例，按照算法流程走一遍；,实例的选择：尽可能地覆盖多个方面；考虑问题的特殊性；,算法设计的一般过程,时间效率与空间效率；,更关注的是时间效率；,算法性能比较：时间短、效果好！,算法设计的一般过程,计算机不能直接执行伪代码；,算法是需要不断完善和改进的；,算法设计的一般过程,算法设计实例 1.2,例1.2求两个自然数的最大公约数,求解思路：用短

6、除法找出两个自然数的所有公因子，将这些公因子相乘，结果就是这两个数的最大公约数。,算法设计实例 1.2,算法1. CommFactor1,输入：两个自然数m和n输出：m和n的最大公约数factor=1;循环变量 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=

7、1; for(int i=2;i=m,2 为什么要学习和研究算法,2 算法训练能够提高计算思维能力,计算机不够智能，不能主动地分析问题解决问题；,需要人的智慧分析问题，形式化地描述问题；采用抽象思维和逻辑思维设计问题解决方案；,采用抽象思维和逻辑思维设计问题解决方案；,2 算法训练能够提高计算思维能力,美国计算机协会与美国电气与电子工程师协会（ACM/IEEE-CS）认为计算机专业的基本能力包括：计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力；,计算机求解问题的过程中，最重要的环节就是将人的想法抽象为算法；,算法训练像一种思维体操，能够锻炼我们的思维，使思维变得清晰、更有逻辑；

8、,2 算法研究是推动计算机技术发展的关键,检索技术,压缩与解压缩,信息安全与数据加密,思考如下问题,案例一查找问题,案例二排序问题,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=r0; ,案例二排序问题,案例三图问题,案例四组合问题,最小乘车费用假 设 1 2 3 4 5 6 7 8 9 10费 用 12 21 31 40 49 58 69 79 90 101 而任意一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。,案例五几何问题,怎么修围墙满足利用最大化？,用计算机求解任何问题离不开程序设计，而程序设计的核心是算法设计。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。,算法是计算机的灵魂,算法可以看作是解决问题的一类特殊方法它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。,算法是计算机的灵魂,算法之魂速度,算法研究的核心问题是时间（速度）问题。,