算法设计基础(1)

算法设计与分析授课教师：刘志中[e-mail]:120511193TEL:[phone]第一章算法设计基础1234算法的基本概念为什么学习和研究算法重要的问题类型小结１算法及其特性算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法的特性4确定性2输出3有穷性1输入5可行性１算法及其特性1输入这些输入通常取自于某个特定的对象的集合零个或多个输入１算法及其特性2输出通常输入与输出之间有着某种特定的关系有一个或多个输出１算法及其特性3有穷性必须总是在执行又穷步之后结束，且每一步都在有穷时间内完成１算法及其特性4确定性算法中每一条指令必须有确切的含义，不存在二义性；在任何情况下，对于相同的输入只能得到相同的输出；１算法及其特性5可行性可以通过程序实现操作；Problem—问题规定了输入与输出之间的关系，可以用通用语言来描述；InstanceofaProblem—问题实例某一个问题实例包含了求解该问题所需输入；输入:由n个数组成的一个序列a1,a2,,an输出:对输入系列的一个排列(重排）a1’,a2’,,an’，使得a1’a2’an’排序问题的一个实例Input:31,41,59,26,41,58——Output:26,31,41,41,58,59算法概念理解:问题及问题实例算法的其他特性4抽象分级2健壮性3可理解性1正确性5高效性算法的其他特性1正确性对于任意合法的输入，算法都会得到正确的结果；算法的其他特性2健壮性算法对非法输入的抵抗能力；对错误的输入，算法应能识别并作出处理；而不产生错误的动作或陷入瘫痪；危害：美国电话电报公司算法的其他特性3可理解性容易理解与实现；易于被人理解，易于转换成程序；算法的其他特性4抽象分级对某些具体的细节进行抽象；不过细地描述细节；算法步骤太多，会增加算法的理解难度；算法的其他特性5高效性时间效率与空间效率；时间效率---求解速度；空间效率---额外的存储空间；理想目标：较短的执行时间、较少的辅助空间；算法的描述方法4程序设计语言2程序流程图3伪代码1自然语言算法的描述方法1自然语言优点：容易书写、容易理解缺点:(1)歧义性，二义性，不满足确定性；(2)自然语言不够简练，导致算法描述过长；(3)抽象级别高，不易转换成计算机程序算法的描述方法2程序流程图优点：直观易懂、能够随意表示控制流程；缺点:(1)严密性不如程序设计语言；(2)灵活性不如自然语言；算法的描述方法3伪代码伪代码是介于自然语言和程序设计语言之间的方法；它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化描述算法不必要的细节，是比较合适的算法描述语言，被称为“算法语言”或“第一语言”。算法设计的一般过程1理解问题求解目标、已知信息、显示条件、隐含条件输入什么、输出什么、结果的呈现全面准确地理解、分析问题，能够事半功倍算法设计的一般过程2选择算法设计技术算法设计策略；本课程所讲解的方法可以用于解决不同领域的不同问题；蛮力法、分治法、减治法、动态规划、回溯等基于这些基本的算法与技术，设计出高效、智能的好算法！算法设计的一般过程3设计并描述算法清楚地描述算法的步骤；描述方法：自然语言、流程图、伪代码本课程：C++与自然语言---伪代码算法设计的一般过程4手工运行算法计算机比较傻；比较机械，吩咐干啥就干啥发现不了算法中的逻辑错误；解决方法：手工运行算法；带入一个具体的事例，按照算法流程走一遍；实例的选择：尽可能地覆盖多个方面；考虑问题的特殊性；算法设计的一般过程5分析算法的效率时间效率与空间效率；更关注的是时间效率；算法性能比较：时间短、效果好！算法设计的一般过程6实现算法计算机不能直接执行伪代码；算法是需要不断完善和改进的；算法设计的一般过程待求解的问题分析问题选择算法设计技术设计并描述算法分析算法的效率手工运行算法根据算法编写代码不满意满意算法设计实例1.2例1.2求两个自然数的最大公约数求解思路：用短除法找出两个自然数的所有公因子，将这些公因子相乘，结果就是这两个数的最大公约数。算法设计实例1.2算法1.CommFactor1输入：两个自然数m和n输出：m和n的最大公约数1.factor=1;2.循环变量i从2~min(m,n),执行以下操作；2.1如果i是m和n的公因子，则执行下述操作；2.1.1factor=factor*i;2.1.2m=m/i;n=n/i;2.2如果i不是m和n的公因子，则i=i+1；3.输出factor；算法设计实例1.2算法1.编程实现intCommFactor1(intm,intn){inti,factor=1;for(inti=2;i=m&&i=n;i++){while(m%i==0&&n%n==0){factor=factor*i;m=m/i;n=n/i;}}returnfactor;}2为什么要学习和研究算法2算法训练能够提高计算思维能力计算机不够智能，不能主动地分析问题解决问题；需要人的智慧分析问题，形式化地描述问题；采用抽象思维和逻辑思维设计问题解决方案；采用抽象思维和逻辑思维设计问题解决方案；2算法训练能够提高计算思维能力美国计算机协会与美国电气与电子工程师协会（ACM/IEEE-CS）认为计算机专业的基本能力包括：计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力；计算机求解问题的过程中，最重要的环节就是将人的想法抽象为算法；算法训练像一种思维体操，能够锻炼我们的思维，使思维变得清晰、更有逻辑；2算法研究是推动计算机技术发展的关键检索技术压缩与解压缩信息安全与数据加密思考如下问题案例一——查找问题231333231788131723233313233323178132333231781323233317813172323338案例二——排序问题voidinsertSort(intr[],intn){for(i=2;i=n;i++){r[0]=r[i];j=i-1;for(j=i-1;r[0]r[j];j--){r[j+1]=r[j];j=j-1;}r[j+1]=r[0];}}案例二——排序问题案例三——图问题案例四——组合问题最小乘车费用假设12345678910费用122131404958697990101而任意一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。案例五——几何问题怎么修围墙满足利用最大化？用计算机求解任何问题离不开程序设计，而程序设计的核心是算法设计。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。算法是计算机的灵魂算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。算法是计算机的灵魂算法之魂——速度算法研究的核心问题是时间（速度）问题。