《算法及其描述》PPT课件.ppt

计算机常用算法与程序设计案例教程 杨克昌 请用PowerPoint2003播放 课堂讲授 学时安排 36 讲授 18 上机 可根据实际教学计划进行调整 各常用算法的概念与设计要点 重点讲授应用算法设计求解基本的典型案例 并通过相关程序 引导设计变通 在基本案例引导下自学相关联案例求解 小组讨论与基本案例相关的拓展与引申案例求解 为 课程设计 作准备 上机实践 学习建议 学会归纳 总结和提炼 自觉调整学习状态 培养案例求解兴趣自觉完成布置的作业加深对算法应用的理解善于变通 拓展与改进 注重算法设计 提高解决实际案例的能力 上机环境 VC 6 0上机通过每章指定的案例求解程序与习题按要求填写实验报告 教学要求了解算法概念 算法特征及算法的描述建立算法的复杂性概念掌握结构化程序设计的基本方法 本章重点应用c语言描述算法掌握算法时间复杂度分析 算法与程序设计概述 1 1算法及其描述 算法是程序设计的基础 是计算机科学的核心 1 1 1算法定义算法是计算机解决问题的过程 是解决某一问题的运算序列 或者说算法是问题求解过程的运算描述 当面临某一问题时 需要找到用计算机解决这个问题的方法与步骤 算法就是解决这个问题的方法与步骤的描述 1 算法的三要素 算法由操作 控制结构与数据结构三者组成 1 操作 算术运算 关系运算 逻辑运算 输入 输出 赋值等操作 2 控制结构 顺序结构 选择结构 循环结构 模块调用 3 数据结构 数据之间的逻辑关系 2 算法的基本特征 一个算法由有限条可完全机械地执行的 有确定结果的指令组成 具有以下特性 1 确定性 2 可行性 3 有穷性 4 算法有零个或多个输入 5 算法有一个或多个输出 1 1 2算法描述 1 一个问题可以设计不同的算法来求解 同一个算法可以采用不同的形式来表述 2 描述算法可以有 自然语言方式 流程图方式 伪代码方式 计算机语言表示方式与表格方式等 3 当一个算法使用计算机程序设计语言描述时 就是程序 本书采用C语言与自然语言相结合来描述算法 例1 1求两个整数a b的最大公约数的欧几里德算法 1 数a除以b得余数r 若r 0 则b为所求的最大公约数 2 若r 0 以b为a r为b 继续 1 欧几里德算法具体描述如下 input a b 输入的简略表示r a b while r 0 实施辗转相除 a b b r r a b print b 输出的简略表示 例1 2由n个1组成的整数能被2011整除 求n至少为多大 1 试模拟整数竖式除法 可以证明 n是存在的 且不大于2011 因而以上竖式运算总会停止 当除运算的余数为 0 时 数一数被除数中有多少个 1 即可 设整数竖式除法每次试商的被除数为a 除数为2011 每次试商的余数为c 循环以余数c 0作为循环条件 循环外赋初值 c 1111 n 4或c 111 n 3等等 设置竖式除法模拟循环 循环中被除数a c 10 1 试商余数c a 2011 若余数c 0 结束循环 输出结果 否则 计算a c 10 1为下一轮运算的被除数 继续试商 每商一位 统计被除数中 1 的个数的变量n增1 2 竖式除法模拟描述 c 1111 n 4 变量c与n赋初值while c 0 模拟竖式除法 a c 10 1 c a 2011 n n 1 每试商一位n增1 print n 输出的简略表示 1 2算法的复杂性分析 算法的复杂性越高 所需的计算机资源越多 最重要的计算机资源是时间资源与空间资源 需要计算机时间资源的量称为时间复杂度 需要计算机空间资源的量称为空间复杂度 时间复杂度与空间复杂度集中反映算法的效率 1 2 1时间复杂度 要想充分理解算法并有效地应用算法求解实际案例 关键是对算法的分析 通常我们可以利用实验对比方法 数学方法来分析算法 实验对比分析很简单 两个算法相互比较求解时间 数学方法能在严密的逻辑推理基础上判断算法的优劣 在算法分析中 我们往往采用能近似表达性能的方法来展示某个算法的性能指标 一个算法的时间复杂度是指算法运行所需的时间 一个算法的运行时间取决于算法所需执行的语句 运算 的多少 算法的时间复杂度通常用该算法执行的总语句 运算 的数量级决定 一条语句的数量级即执行它的频数 一个算法的数量级是指它所有语句执行频数之和 在分析算法时 隐藏细节的数学表示方法为大写字母 O 记法 它可以帮助我们简化算法复杂度计算的许多细节 提取主要成分 算法的执行频数的数量级直接决定算法的时间复杂度 2个语句各执行1次 共执行2次 时间复杂度为O 1 1 x x 1 s s x 例1 3试计算下面三个程序段的时间复杂度 2 for k 1 k n k x x y y x y s x y k 1 执行1次 k n 与 k 各执行n次 3个赋值语句 每个赋值语句各执行n次 共执行5n 1次 时间复杂度为O n 例1 3试计算下面三个程序段的执行频数 3 for t 1 k 1 k n k t t 2 for j 1 j t j s s j t 1 与 k 1 各执行1次 k n 与 k 各执行n次 t t 2 执行n次 j 1 执行n次 j t j 与内循环的赋值语句 s s j 各执行频数为 总的执行频数为 时间复杂度符号O的两个定理 在估算算法的时间复杂度时 为简单计 以后只考虑内循环语句的执行频数 而不细致计算各循环设计语句及其它语句的执行次数 这样简化处理不影响算法的时间复杂度 例1 4估算以下程序段所代表算法的时间复杂度 for k 1 k n k for j 1 j k j x k j s s x 每个赋值语句执行频率为n n 1 2 该算法的时间复杂度为 O n 2 一个算法的运行时间 与问题的规模相关 也与输入的数据相关 例如对给定的n个整数a 1 a 2 a n 排序 for i 1 ia j h a i a i a j a j h 3个赋值语句的执行频数之和 最理想的情形下为零 当所有n个整数已从小到大排列时 最坏情形下为3n n 1 2 当n个整数为从大到小排列时 按平均情形来分析 其时间复杂度为O n 2 对于一个实用算法 我们通常不必深入研究它时间复杂度的上界和下界 只需要了解该算法的特性 然后在合适的时候应用它 为了求解某一问题 设计出复杂性尽可能低的算法是追求的重要目标 或者说 求解某一问题有多种算法时 选择其中复杂性最低的算法是选用算法的重要准则 对算法的改进与优化 主要表现在有效缩减算法的运行时间与所占空间 1 2 2空间复杂度 一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分 固定空间需求包括程序代码 常量与静态变量等所占的空间 可变空间需求包括局部作用域非静态变量所占用的空间 从堆空间中动态分配的空间与调用函数所需的系统栈空间等 算法的空间复杂度是指算法运行的存储空间 是实现算法所需的内存空间的大小 二维或三维数组是空间复杂度高的主要因素之一 在算法设计时 为降低空间复杂度 要注意尽可能少用高维数组 从应用的角度看 因空间所限影响算法运行的情形较为少见 因而在设计算法时 应把降低算法的时间复杂度作为首要的考虑因素 在论述某一算法时 如果其空间复杂度不高 不至于因所占有的内存空间而影响算法实现时 通常不涉及对该算法的空间复杂度的讨论 1 3算法与程序设计 计算机的一切操作都是由程序控制的 离开了程序 计算机将一事无成 从这个意义来说 计算机的本质是程序的机器 程序是计算机的灵魂 算法是程序的核心 程序是某一算法用计算机程序设计语言的具体实现 1 3 1算法与程序 程序设计反映了利用计算机解决问题的全过程 包括 建立数学模型 数据的组织方式 设计合适的算法 编写程序来实现算法 上机调试程序 使之运行后能产生求解问题的结果 一个程序应包括对数据的描述与对运算操作的描述两个方面的内容 数据结构 算法 程序 数据结构是对数据的描述 算法是对运算操作的描述 例1 7编写程序实现求两个整数a b a b 的最大公约数 a b 的欧几里德算法 includevoidmain longa b c r scanf ld ld 输出求解结果 1 3 2结构化程序设计 任何简单或复杂的算法都可以由顺序结构 选择结构和循环结构这三种基本结构组合而成 所以 顺序结构 选择结构和循环结构被称为程序设计的三种基本结构 也是结构化程序设计必须采用的结构 结构化程序设计方法是目前国内外普遍采用的一种程序设计方法 结构化程序设计方法在实践中不断发展和完善 已成为软件开发的重要方法讨论 结构化程序设计的基本要点 1 自顶向下 逐步求精 2 模块化设计 3 结构化编码 逐步求精总是和自顶向下结合使用 将问题求解逐步具体化的过程 一般把逐步求精看作自顶向下设计的具体体现 模块化是结构化程序设计的重要原则 一个程序是由一个主控模块和若干子模块组成 主控模块用来完成某些公用操作及功能选择 而子模块用来完成某项特定的功能 例1 8把欧几里德算法设计成子模块 通过主模块调用实现求n个整数的最大公约数 实现欧几里德算法的函数 c135 可加c135在VC 6 0的链接 求n个整数的最大公约数 c136 调用c135 可加c136在VC 6 0的链接 在设计好一个结构化的算法之后 还需进行结构化编码 将已设计好的算法用计算机语言来表示 编写出能在计算机上进行编译与运行的程序 结构化程序设计的过程就是将问题求解由抽象逐步具体化的过程 这种方法符