算法的基本工具和优化技巧.ppt

算法基本工具和优化技巧 计算机完成工作的实质是机械化的操作 而算法设计的目标是把人脑解决问题的想法规范化地描述成机械化操作 计算机语言提供给算法的机械化操作 计算 I O 流程控制 不同存储模式 变量 数组 结构体 文件等 本部分就是要讲解如何充分利用基本的机械化操作设计高质量的算法 在程序设计与算法设计之间起承上启下的作用 循环与递归 将大量重复处理大量数据的步骤抽象成循环或递归模式 设计出可以针对不同规模解决问题的算法 循环设计中要注意算法的效率 循环体的特点是 以不变应万变 所谓 不变 是指循环体内运算的表现形式是不变的 而每次具体的执行内容却是不尽相同的 在循环体内用不变的运算表现形式去描述各种相似的重复运算 例1 求1 1 1 3 1 5 1 7 1 n 1 2n 1 数学模型2 Sn Sn 1 An An 1 An 1 2 n 2 2 n 1 main inti n sign floats t 1 cin n s 1 for i 2 i n i t 1 t 2 i 2 2 i 1 s s 1 t cout Sum s 自顶向下 的设计方法 例2 编算法找出1000以内所有完数例如 28的因子为1 2 4 7 14 而28 1 2 4 7 14 因此28是 完数 编算法找出1000之内的所有完数 并按下面格式输出其因子 28 1 顶层算法 for i 2 i n i 判断i是否是完数 是完数则按格式输出 2 判断i是否是完数 for j 2 j i j 找i的因子 并累加如果累加值等于i i是完数 3 进一步细化 判断i是否 完数 算法 s 1for j 2 j i j if i j 0 s s j if s i i是 完数 算法如下 main inti k j s for i 1 i 1000 i s 1 两个赋初值语句s 1for j 2 j i j if i j 0 s s j if i s cout s endl 在算法中 递归一词用于表示直接或间接的调用自身的算法 特别的 用函数自身给出定义的函数被称之为递归函数 什么是递归 其实 我们在生活中经常运用递归的方式来思考问题 如参考下面这个例子 例1 第5个人的年龄比第4个人的年龄大2岁 第4个人的年龄比第3个人的年龄大2岁 第3个人的年龄比第2个人的年龄大2岁 第2个人的年龄比第1个人的年龄大2岁 第1个的年龄10岁 第5个人的年该该是多少呢 著名的意大利数学家斐波那契 Fibonacci 在他的著作 算盘书 中提出了一个 兔子问题 假定小兔子一个月就可以长成大兔子 而大兔子每个月都会生出一对小兔子 如果年初养了一对小兔子 问到年底时将有多少对兔子 当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖 我们需要研究表中的规律 找出一般的方法 去解决这个问题 兔子问题 很容易列出一条递推式而得到解决 假设第N个月的兔子数目是F N 我们有 这是因为每月的大兔子数目一定等于上月的兔子总数 而每个月的小兔子数目一定等于上月的大兔子数目 即前一个月的兔子的数目 递归设计要点 直接或间接地调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数 递归是一种比迭代循环更强 更好用的循环结构 只需要找出递归关系和最小问题的解 递归方法只需少量的步骤就可描述出解题过程所需要的多次重复计算 大大地减少了算法的代码量 递归的关键在于找出递归方程式和递归终止条件 递归定义 使问题向边界条件转化的规则 递归定义必须能使问题越来越简单 递归边界条件 也就是所描述问题的最简单情况 它本身不再使用递归的定义 递归算法解题通常有三个步骤 1 分析问题 寻找递归 找出大规模问题与小规模问题的关系 这样通过递归使问题的规模逐渐变小 2 设置边界 控制递归 找出停止条件 即算法可解的最小规模问题 3 设计函数 确定参数 和其它算法模块一样设计函数体中的操作及相关参数 常见的递归算法阶乘Fibonacci数列著名的汉诺塔问题二叉树的3种遍历 故事 相传在古代印度的Bramah庙中 有位僧人整天把三根柱子上的金盘倒来倒去 原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去 移动过程中恪守下述规则 每次只允许移动一只盘 且大盘不得落在小盘上面 有人会觉得这很简单 真的动手移盘就会发现 如以每秒移动一只盘子的话 按照上述规则将64只盘子从一个柱子移至另一个柱子上 所需时间约为5800亿年 Hanoi塔问题设a b c是3个塔座 开始时 在塔座a上有一叠共n个圆盘 这些圆盘自下而上 由大到小地叠在一起 各圆盘从小到大编号为1 2 n 现要求将塔座a上的这一叠圆盘移到塔座b上 并仍按同样顺序叠置 在移动圆盘时应遵守以下移动规则 规则1 每次只能移动1个圆盘 规则2 任何时刻都不允许将较大的圆盘压在较小的圆盘之上 规则3 在满足移动规则1和2的前提下 可将圆盘移至a b c中任一塔座上 在问题规模较大时 较难找到一般的方法 因此我们尝试用递归技术来解决这个问题 当n 1时 问题比较简单 此时 只要将编号为1的圆盘从塔座a直接移至塔座b上即可 当n 1时 需要利用塔座c作为辅助塔座 此时若能设法将n 1个较小的圆盘依照移动规则从塔座a移至塔座c 然后 将剩下的最大圆盘从塔座a移至塔座b 最后 再设法将n 1个较小的圆盘依照移动规则从塔座c移至塔座b 由此可见 n个圆盘的移动问题可分为2次n 1个圆盘的移动问题 这又可以递归地用上述方法来做 由此可以设计出解Hanoi塔问题的递归算法如下 Hanoi塔问题 voidhanoi intn inta intb intc if n 0 hanoi n 1 a c b move a b hanoi n 1 c b a 例 任给十进制的正整数 请从低位到高位逐位输出各位数字 循环算法设计 f1 n while n 10 cout n 10 n n 10 cout n 递归算法设计 1 同上 算法从低位到高位逐位求出各位数字并输出 求个位数字的算式为n 10 下一步则是递归地求n 10的个位数字 2 当n 10时 n为一位数停止递归 递归算法如下 f2 n if n 10 cout n else cout n 10 f n 10 例 任给十进制的正整数 请从高位到低位逐位输出各位数字 循环算法设计 本题目中要求 从高位到低位 逐位输出各位数字 但由于我们并不知道正整数的位数 算法还是 从低位到高位 逐位求出各位数字比较方便 这样就不能边计算边输出 而需要用数组保存计算的结果 最后倒着输出 循环算法如下 f3 n intj i 0 a 16 while n 10 a i n 10 i i 1 n n 10 a i n for j i j 0 j cout n 递归算法设计 与f2不同 递归算法是先递归地求n 10的个位数字 然后再求个位数字n的个位数字并输出 这样输出操作是在回溯时完成的 递归停止条件与f2相同为n 10 递归算法如下 f4 n if n 10 cout n else f n 10 cout n 10 例4排列问题设计一个递归算法生成n个元素 r1 r2 rn 的全排列 分析 n 1输出 r1n 2输出 r1r2r2r1n 3输出 r1r2r3r1r3r2r2r1r3r2r3r1r3r1r2r3r2r1分析r3 全部排列可以分为三类 1 r1类 r1后跟r2r3的全排列 2 r2类 r2后跟r1r3的全排列 3 r3类 r3后跟r1r2的全排列将 1 中r1r2互换位置 得到 2 将 1 中r1r3互换位置 得到 3 它说明可以用循环的方式重复执行交换位置 后面跟随剩余序列的所有排列 对剩余序列再使用这个方法 这就是递归调用 当后跟的元素没有时就得到递归的边界 递归小结 优点 结构清晰 可读性强 而且容易用数学归纳法来证明算法的正确性 因此它为设计算法 调试程序带来很大方便 缺点 递归算法的运行效率较低 无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 由于递归算法的实现包括递归和回溯两步 当问题需要 后进先出 的操作时 还是用递归算法更有效 如数据结构课程中二叉树的各种遍历 图的深度优先等算法都是如此 所以不能仅仅从效率上评价两个控制重复机制的好坏 事实上 无论把递归作为一种算法的策略 还是一种实现机制 对我们设计算法都有很好的帮助 例7判断s字符串是否为回文的递归函数 intishuiwen char s intn if n 0 n 1 return1 else if s s n 1 ishuiwen s 1 n 2 elsereturn0 递推是计算机数值计算中的一个重要算法 可以将复杂的运算化为若干重复的简单运算 充分发挥计算机长于重复处理的特点 现举一例 递推 猴子吃桃 有一群猴子摘来了一批桃子 猴王规定每天只准吃一半加一只 即第二天吃剩下的一半加一只 以此类推 第九天正好吃完 问猴子们摘来了多少桃子 a9 2a8 a9 1 2 作业 1 运动会开了N天 一共发出金牌M枚 第一天发金牌1枚加剩下的七分之一枚 第二天发金牌2枚加剩下的七分之一枚 第3天发金牌3枚加剩下的七分之一枚 以后每天都照此办理 到了第N天刚好还有金牌N枚 到此金牌全部发完 编程求N和M 作业 2 国王分财产 某国王临终前给儿子们分财产 他把财产分为若干份 然后给第一个儿子一份 再加上剩余财产的1 10 给第二个儿子两份 再加上剩余财产的1 10 给第i个儿子i份 再加上剩余财产的1 10 每个儿子都窃窃自喜 以为得到了父王的偏爱 孰不知国王是 一碗水端平 的 请用程序回答 老国王共有几个儿子 财产共分成了多少份 作业 3 出售金鱼 第一次卖出全部金鱼的一半加二分之一条金鱼 第二次卖出乘余金鱼的三分之一加三分之一条金鱼 第三次卖出剩余金鱼的四分之一加四分之一条金鱼 第四次卖出剩余金鱼的五分之一加五分之一条金鱼 现在还剩下11条金鱼 在出售金鱼时不能把金鱼切开或者有任何破损的 问这鱼缸里原有多少条金鱼 作业 4 某路公共汽车 总共有八站 从一号站发轩时车上已有n位乘客 到了第二站先下一半乘客 再上来了六位乘客 到了第三站也先下一半乘客 再上来了五位乘客 以后每到一站都先下车上已有的一半乘客 再上来了乘客比前一站少一个 到了终点站车上还有乘客六人 问发车时车上的乘客有多少 作业 5 小华读书 第一天读了全书的一半加二页 第二天读了剩下的一半加二页 以后天天如此 第六天读完了最后的三页 问全书有多少钱页 作业 6 日本著名数学游戏专家中村义作教授提出这样一个问题 父亲将2520个桔子分给六个儿子 分完后父亲说 老大将分给你的桔子的1 8给老二 老二拿到后连同原先的桔子分1 7给老三 老三拿到后连同原先的桔子分1 6给老四 老四拿到后连同原先的桔子分1 5给老五 老五拿到后连同原先的桔子分1 4给老六 老六拿到后连同原先的桔子分1 3给老大 结果大家手中的桔子正好一样多 问六兄弟原来手中各有多少桔子 枚举法 一次考试共考了语文 代数和外语三科 某小组共有九人 考后各科及格名单如下表 请编写算法找出三科全及格的学生的名单 学号 求X 使X2为一个各位数字互不相同的九位数 枚举法 分析 只能用枚举法尝试完成此题 由X2为一个九位数 估算X应在10000 32000之间 1 用一个10个元素的状态数组p 记录数字0 9在X2中出现的情况 数组元素都赋初值为0 表示数字0 9没有被使用过 2 对尝试的每一个数x 求x x 并取其各位数字 数字作为数组的下标 若对应元素为0 则该数字第一次出现 将对应的元素赋为1 表示该数字已出现一次 否则 若对应元素为1 则说明有重复数字 结束这次尝试 3 容易理解当状态数组p中有9个元素为1时 就找到了问题的解 但这样判定有解 需要扫描一遍数组p 为避免这个步骤 设置一个计数器k 在取x x各个位数字的过程中记录不同的数字的个数 当k 9时就找到了问题的解 main longx y1 y2 intp 10 2 i t k num 0 for x 10000 x 32000 x for i 0 i 9 i i 1 p i 0 y1 x x y2 y1 k 0 for i 1 i 9 i t y2 10 y2 y2 10 if p t 0 k k 1 p t 1 elsebreak if k 9 num num 1 cout No num x n2 y1 警察局抓了a b c d四名偷窃嫌疑犯 其中只有一人是小偷 审问中a说 我不是小偷 b说 c是小偷 c说 小偷肯定是d d说 c在冤枉人 现在已经知道四个人中三人说的是真话 一人说的是假话 问到底谁是小偷 信息数字化 算法设计 用变量x存放小偷的编号 则x的取值范围从1取到4 就假设了他们中的某人是小偷的所有情况 四个人所说的话就可以分别写成 a说的话 x1b说的话 x 3c说的话 x 4d说的话 x4或not x 4 注意 在x的枚举过程中 当这四个逻辑式的值相加等于3时 即表示 四个人中三人说的是真话 一人说的是假话 算法如下 main intx for x 1 x1 x 3 x 4 x4 3 cout chr 64 x isathief 运行结果 cisathief 三位老师对某次数学竞赛进行了预测 他们的预测如下 甲说 学生A得第一名 学生B