中南大学算法设计与分析

《中南大学算法设计与分析》由会员分享，可在线阅读，更多相关《中南大学算法设计与分析（43页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析 卢新国 参考教材 1算法设计与分析基础（ ，潘彦译（ 美 ，清华大学出版社 2计算机算法设计与分析（第 3版） ，王晓东，电子工业出版社 配套：“算法设计与实验题解”，王晓东 ，电子工业出版社 2 课程介绍 期末总评成绩： 平时成绩 *40% + 期末（闭卷）成绩 *60% 平时成绩：考勤 (10%)、小测试 (10%)、0%) 小测试安排： 学术型可以不随堂 专业型必须随堂 公室： 539 3 课程介绍 例 1： 百鸡问题 ： “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？” 中国古代约 5 张邱建算经 4 删数方案 例 2： 假设正整数

2、 n、 s， s 259 n=5 s=2 24351 - 231 5 例 3： 奥运会排球比赛 : 预赛： 国、古巴、日本、美国、波 兰、委内瑞拉、 罗斯、塞尔维亚、巴西、意大 利、哈萨克斯坦、阿尔及利亚 1/4决赛、 1/2决赛：古 、中 6 例 4： 八后问题 : 在 8*8的棋盘上，每行放置 一个皇后，要求它们不能在同一列， 同一斜线上。 高斯 认为有 76种方案。 1854年在柏林的象棋杂志上不同的作者发表了 40种不同的解，后来有人用图论的方法解出 92种结果。 由国际西洋棋棋手马克斯 贝瑟尔于 1848年提出 7 第一章 绪论 算法是计算机的核心 科技殿堂时陈列着两颗熠熠生辉的宝石

3、 ,一颗是 微积分 ,另一颗就是 算法 。微积分以及在微积分基础上建立起来的数学分析体系成就了现代科学 ,而算法则成就了现代世界 of 2000 8 为什么要学习算法 一般来说，对程序设计的研究可以分为四个层次：算法、方法学、语言和工具，其中算法研究位于最高层次。 算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。 一个人只有把知识教给别人，才能真正掌握它。实际上，一个人只有把知识教给计算机，才能真正掌握它。 9 为什么要学习算法？ 算法不仅是计算机科学的一个分支，它更是计算机科学的核心，而且，可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的。 算

4、法：计算的灵魂 程序 =数据结构 +算法 10 算法可以解决哪些问题 ? 找出人类 00000中基因，确定构成人类 0亿种化学基对的各种序列。 快速地访问和检索互联网数据 电子商务活动中各种信息的加密及签名 制造业中各种资源的有效分配 确定地图中两地之间的最短路径 各种数学、几何计算（矩阵、方程、集合） 11 12 算法基础 ( 算法基本概念 算法效率分析基础 算法设计及分析技巧 蛮力法 分治法 ( 减治法 变治法 时空权衡 动态规划 ( 贪婪技术 ( 回溯法 (13 s 假设要喝一杯茶有以下几个步骤： 请问你怎样安排？ 14 s 1一步，把冰箱门打开 第二步，把大象装进去 第三步，把冰箱门关

5、上 15 s 算法 是一系列解决问题的 清晰 指令，也就是说，能够对一定 规范 的 输入 ，在 有限 时间内获得所要求的 输出 。 “ 6 算法的几个要点 算法的每一个步骤都必须清晰、明确。 算法所处理的输入的值域必须仔细定义。 同样的一个算法可以用几种不同的形式来描述。 可能存在几种解决相同问题的算法。 针对同一个问题的算法可能会基于完全不同的解题思路，而且解题的速度也会有明显区别。 17 求两个正整数 m,m,n) 如果构造这个算法？ 18 求两个正整数 m,m,n) 欧几里得算法基于的方法是重复应用下列式子，直到 m n=0 m, n) = n, m n) m,n)的欧几里得算法 第一步

6、：如果 n=0，返回 束；否则进入第二步 第二步：用 m，将余数赋给 r。 第三步：将 m，将 n，回第一步。 算法 m,n) /使用欧几里得算法计算 m,n) /输入：两个不全为 0的非负整数 m,n /输出： m， n!=0 do rm n mn nr m 同一个算法有不同的表达方式 19 伪码描述 算法 m, n) / 计算 m 和 n 最大公约数的欧氏算法 / 输入：两个不全为 0的非负整数 mn / 输出： m 和 n 的最大公约数 n0 r m n mn n r m 问题 2：算法一定收敛吗？（ n 值最后一定为 0 ？） 观察分析（理论证明略） 每一次循环， n m n， n 值

7、变小，但不会变成负数即 n r 0 . 整数 n 越来越小，最终变成 0（算法收敛） 问题 1： 如果 m 和 n 没有 公约数，本算法是否支持这种情况？ 答：支持 例 ： (63, 22)(22, 19) (19, 3)(3,1) (1,0) 1 20 m,n)的连续整数检测算法 第一步：将 m,n的值赋给 t。 第二步： t，如果余数为 0，则进入第三步；否则，进入第四步。 第三步： t，如果余数为 0 ，则返回 则，进入第四步。 第四步：把 。返回第二步。 m,n)的中学计算算法 第一步：找到 第二步：找到 第三步：从第一步和第二步中求得的质因数分解式找出所有的公因数 第四步：将第三步中

8、找的质因数相乘，其结果作为给定数字的最大公因数。 同一个问题有不同的解决方法 21 算法问题求解基础 算法是问题的程序化解决方案 。 理解问题 了解设备性能 选择计算方法 精确或近似解法 高效的数据结构 算法的设计技术 设计算法 正确性证明 分析算法 编程实现 算法 22 算法问题求解基础 理解问题 设计算法前做的第一件事情 仔细阅读问题的描述 提出疑问 手工处理一些实例 考虑特殊情况 确定输入 抽象出问题，用数学表达式描述 23 算法问题求解基础 了解计算设备的性能 ? 确定计算方法 并行算法 选择精确解和近似解 ? 某些重要的问题无法求得精确解 某些问题利用精确解速度慢，无法接受 1）解非

9、线性方程（超越方程，高次方程）算法 对分区间法， 顿切线法等等。 2）数值积分算法 找不到原函数：如被积函数是表格函数（离散点）。 3）数值微分算法 差分近似微分，如前差分、后差分、中心差分、 5点差分等。 4）插值算法、拟合算法 无法得到理论上精确的函数关系。 24 算法问题求解基础 确定适当的数据结构 算法 + 数据结构 = 程序 算法设计技术 使用算法解题的一般性方法，用于解决计算领域的多种问题。 详细表述算法的方法 自然语言 伪代码 流程图 25 算法问题求解基础 证明算法的正确性 证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。 一般方法：数学归纳法 证明算

10、法的正确性与不正确哪一个更容易？ 分析算法 算法有两种效率：时间效率和空间效率 算法的另外两个特性：简单性和一般性 26 算法问题求解基础 为算法写代码 用计算机程序实现算法 在把算法转变为程序的过程中，可能会发生错误或者效率非常低 作为一种规律，一个好的算法是反复努力和重新修正的结果 算法是一个 最优性 问题：对于给定的问题需要花费多少力气（资源）？ 是不是每个问题都能够用算法的方法来解决？ 发明或者发现算法是一个非常有创造性和非常值得付出的过程！ 27 重要的问题类型 排序 ( 查找 ( 串处理 ( 图问题 ( 组合问题 ( 几何问题 ( 数值问题 岛 岛 河 岸 桥 七桥问题 28 基本

11、数据结构 线性数据结构 数组，串，单（双）链表，栈，队列 图 有向图，无向图，加权图 树 自由树，有根树 有序树 集合与字典 29 数据结构简要回顾：线性结构 数据结构简要回顾 算法操作的是数据，数据结构是数据的存储和组织方式 逻辑结构： 线性结构、树形结构、图形结构、集合结构。（数据结构） 存储结构： 顺序存储、链式存储、索引存储、散列存储。（物理结构） 线性结构 顺序存储（一维数组实现） 特点：相同类型的数据构成，在内存中连续存放。 访问：可用数组下标访问数组元素。无论元素在数组的什么位置上， 其访问时间都相等。 应用： C+ 的整型数组、浮点数组、字符串数组、结构数组、指针 数组、函数指针数组、结构数组、对象数组， ，等等。 存储结构图例： 数据 0 数据 1 数据 2 数据 储单元 30 数据结构简要回顾：链式存储 链式存储（链表） 特点： 若干节点构成，每个节点包含数据和指针。 指针可有多个，指向 其他节点地址（ 示无后继节点）。单链表除最后节点外， 每个节点包含一个指向后继节点的指针。如图： 节点所占的内存单元不连续，不能给节点编号来直接访问。 访问：要访问某个节点， 需从头节点开始，直到访问到该元素为止。 访问链表某节点所需时间