算法设计与分析-第1章

算法设计与分析,王红梅胡明编著,普通高校计算机专业特色教材精选,本书主要内容,第1章算法设计基础第2章算法分析基础第3章蛮力法第4章分治法第5章减治法第6章动态规划法,本书主要内容（续）,第7章贪心法第8章回溯法第9章分支限界法第10章问题的复杂性第11章近似算法第12章概率算法,第1章算法设计基础,算法理论的两大论题：1.算法设计2.算法分析,1.1算法的基本概念,1.1.1算法及其重要特性,1.1.2算法的描述方法,1.1.3算法设计的一般过程,1.1.1算法及其重要特性,算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。,算法的五大特性：,输入：一个算法有零个或多个输入。输出：一个算法有一个或多个输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。,算法的其它特性：,正确性：任何合法的输入，算法都会得出正确的结果。健壮性：算法对非法输入的抵抗能力，即对错误的输入，算法应能识别并作出处理，而不是产生错误的动作或者瘫痪。可理解性：算法容易理解和实现。抽象分级；高效性。,1.1.2算法的描述方法,自然语言优点：容易理解缺点：冗长、二义性使用方法：粗略描述算法思想注意事项：避免写成自然段,欧几里德算法,m,n,r,例：欧几里德算法辗转相除法求两个自然数m和n的最大公约数,输入m和n；求m除以n的余数r；若r等于0，则n为最大公约数，算法结束；否则执行第步；将n的值放在m中，将r的值放在n中；重新执行第步。,欧几里德算法,流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次,欧几里德算法,程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数,#includeintCommonFactor(intm,intn)intr=m%n;while(r!=0)m=n;n=r;r=m%n;returnn;voidmain()coutCommonFactor(63,54)endl;,欧几里德算法,伪代码算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：72,1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;,欧几里德算法,1.1.3算法设计的一般过程,1理解问题2选择算法设计技术3.设计并描述算法4.手工运行算法5分析算法的效率6实现算法,问题的求解过程：分析问题设计算法编写程序整理结果程序设计研究的四个层次：算法方法学语言工具,1.2为什么要学习算法,理由1：算法程序的灵魂,理由2：提高分析问题的能力,算法的形式化思维的逻辑性、条理性,用计算机求解任何问题离不开程序设计，而程序设计的核心是算法设计。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。算法可以看作是解决问题的一类特殊方法它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。,算法是计算机的灵魂,1.3重要的问题类型,1.3.1查找问题1.3.2排序问题1.3.3图问题1.3.4组合问题1.3.5几何问题,查找问题,排序问题,图问题,组合问题,最小乘车费用假设12345678910费用122131404958697990101