《算法设计与分析》第01章.ppt

算法设计与分析 DeSignandAnalysisofAlgorithmsInC 十一五 国家级规划教材 陈慧南编著 电子工业出版社 课程简介 课程名称 算法设计与分析DesignandAnalysisofAlgorithms先修课程 程序设计语言C C 数据结构 离散数学 一点 参考书 教材算法设计与分析 C 语言描述陈慧南其他参考书 TheArtofComputerProgramming Volume1 3 D E Knuth byAddision WeslyPublishingCompany inc第1版AlgorithmsDesignTechniquesandAnalysis 沙特 M H Alsuwaiyel著 电子工业出版社 第1版算法设计与分析 王晓东 电子工业出版社 第1版 课程内容安排 第一部分 算法分析基础算法基础概念算法分析概念与基本方法第三部分 算法设计策略图的遍历方法 分治法 贪心法 动态规划法 回溯法 分枝限界法第三部分 求解困难问题与现代算法NP问题概念现代算法 考核方法 10 考勤与课堂表现40 练习作业50 实验报告 含5 的个人学习体会 第1部分算法和算法分析 第1章算法问题求解基础 1 1算法概述1 2问题求解方法1 3算法设计与分析1 4递归和归纳 1 1算法概述 1 1 1什么是算法 算法 algorithm 一个算法是对特定问题求解步骤的一种描述 它是指令的有限序列 此外 算法具有下列5个特征 Knuth 1968 section1 1 DonaldKnuth TheArtofComputerProgramming Addison Wesley Reading Mass 输入 input 算法有零个或多个输入量 输出 output 算法至少产生一个输出量 确定性 definiteness 算法的每一条指令都有确切的定义 没有二义性 能行性 effectiveness 算法的每一条指令必须足够基本 它们可以通过已经实现的基本运算执行有限次来实现 有穷性 finiteness 算法必须总能在执行有限步之后终止 问题 计算两个整数m和n 0 m n 的最大公约数 记为gcd m n 欧几里德算法 辗转相除法 gcd m n gcd nmodm m 直到nmodm 0为止 程序1 1 欧几里德递归算法intRGcd intm intn if m 0 returnn returnRGcd n m m intGcd intm intn if m n Swap m n 使第2个参数大returnRGcd m n 程序1 1 欧几里德递归算法intRGcd intm intn if m 0 returnn returnRGcd n m m intGcd intm intn if m n Swap m n returnRGcd m n 程序1 2 欧几里德迭代算法intGcd intm intn if m 0 returnn if n 0 returnm if m n Swap m n while m 0 intc n m n m m c returnn 程序1 3 Gcd的连续整数检测算法intGcd intm intn if m 0 returnn if n 0 returnm intt m n n m while m t n t t returnt 1 1 2为什么学习算法 算法 高级软件人才 因为你必须知道来自不同计算领域的重要算法 你也必须学会设计新的算法 确认其正确性并分析其效率 随着计算机应用的日益普及 各个应用领域的研究和技术人员都在使用计算机求解他们各自专业领域的问题 他们需要设计算法 编写程序 开发应用软件 所以学习算法对于越来越多的人来说变得十分必要 1 2问题求解方法 1 2 1问题和问题求解 总存在问题问题求解过程 problemsolvingprocess 是人们通过使用问题领域知识来理解和定义问题 并凭借自身的经验和知识去选择和使用适当的问题求解策略 技术和工具 将一个问题描述转换成问题解的过程 计算机求解问题的关键之一是寻找一种问题求解策略 problemsolvingstrategy 得到求解问题的算法 从而得到问题的解 算法问题的求解过程 程序的开发过程就是使用计算机求解问题的过程 软件工程 softwareengineering 将软件开发和维护过程分成若干阶段 称为系统生命周期 systemlifecycle 或软件生命周期 软件生命周期划分为 分析 analysis 设计 design 编码 codingorprogramming 测试 testing 维护 maintenance 等5个阶段 前4个阶段属于开发期 最后一个阶段处于运行期 分析 设计 算法问题求解过程 理解问题选择求解方法 确定数据结构设计算法正确性证明算法分析 评估 改进 1 3算法设计与分析 一个精确算法 exactalgorithm 总能保证求得问题的解 一个启发式算法 heuristicalgorithm 通过使用某种规则 简化或智能猜测来减少问题求解时间 1 3 1算法分类 对于最优化问题 一个算法如果致力于寻找近似解而不是最优解 被称为近似算法 approximationalgorithm 如果在算法中需做出某些随机选择 则称为随机算法 randomizedalgorithm 1 3 2如何设计算法 使用计算机的问题求解策略主要指算法设计策略 algorithmdesignstrategy 1 3 3如何表示算法 算法描述方法自然语言流程图伪代码程序设计语言本书使用C C 语言描述算法 1 3 4如何确认算法 确认一个算法是否正确的活动称为算法确认 algorithmvalidation 使用数学方法证明算法的正确性 称为算法证明 algorithmproof 程序测试 programtesting 是指对程序模块或程序总体 输入事先准备好的样本数据 称为测试用例 testcase 检查该程序的输出 来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动 1 3 5如何分析算法 算法分析 algorithmanalysis 活动是指对算法的执行时间和所需空间的估算 当然在算法写成程序后 便可使用样本数据 实际测量一个程序所消耗的时间和空间 这称为程序的性能测量 performancemeasurement 1 4递归和归纳 1 4 1递归 递归定义递归 recursive 定义是一种直接或间接引用自身的定义方法 一个合法的递归定义包括两部分 基础情况 basecase 和递归部分 例1 1斐波那契数列 例1 1斐波那契数列 递归算法当一个算法采用递归方式定义时便成为递归算法 一个递归算法是指直接或间接调用自身的算法 程序1 4 求FnlongFib longn if n 1 returnn elsereturnFib n 2 Fib n 1 可以用所谓的递归树 recursivetree 来描述程序1 4的函数Fib执行时的调用关系 图1 2计算Fib 4 的递归树 递归数据结构使用递归方式定义的数据结构称为递归数据结构 recursivedatastructure 如链表结构 1 4 2递归算法示例 例1 2逆序输出正整数的各位数 程序1 5 voidPrintDigit unsignedintn cout 10 PrintDigit n 10 以逆序输出前k 1位数 例1 3汉诺塔问题 towerofHanoi 假定有三个塔座 X Y Z 在塔座X上有n个直径大小各不相同 按圆盘大小从小到大编号为1 2 n的圆盘 现要求将X塔座上n个圆盘移到塔座Y上 并仍按同样顺序叠排 圆盘移动时必须遵循下列规则 1 每次只能移动一个圆盘 2 圆盘可以加到塔座X Y Z中任意一个上 3 任何时刻都不能将一个较大的圆盘放在较小的圆盘之上 程序1 6 汉诺塔问题enumtower A X B Y C Z voidMove intn towerx towery 将第n个圆盘从塔座x移到塔座y的顶部cout Thedisk n ismovedfrom char x totopoftower char y endl voidHanoi intn towerx towery towerz 将x上部的n个圆盘移到y上 顺序不变 if n Hanoi n 1 x z y Move n x y Hanoi n 1 z y x 递归算法小结 一种将 大问题 分解为 小问题 求解的思路大 小问题之间有相似性最终小问题能够直接求解 结束递归 问两个题 1 如何证明递归算法的正确性2 如何判断一个递归算法能否转换为迭代实现 1 4 3归纳证明 定理1 1对于n 0 程序1 5是正确的 证明 归纳法证明 当n是1位数时 程序显然是正确的 假定函数PrintDigit对所有位数小于k k 1 的正整数都能正确运行 当n的位数为k位时 此时有n 10 算法必定先执行语句cout 10 PrintDigit n 10 由于 n 10 是n的前k