4.4分治与递归策略（Python进阶-数据结构与算法）课件

分治策略与递归 数据结构与算法（Python版） ❖ 解决问题的典型策略： 分而治之 将问题分为若干更小规模的部分 通过解决每一个小规模部分问题，并将结果汇总 得到原问题的解 数据结构与算法（Python版） 0 分治策略 ❖ 递归三定律： 基本结束条件，解决最小规模问题 缩小规模，向基本结束条件演进 调用自身来解决已缩小规模的相同问题 ❖ 体现了分治策略 问题解决依赖于若干缩小了规模的问题 汇总得到原问题的解 ❖ 应用相当广泛 排序、查找、遍历、求值等等 数据结构与算法（Python版） 递归算法与分治策略 0 ❖ 计算机科学中许多算法都是为了找到某些 问题的最优解 例如，两个点之间的最短路径； 能最好匹配一系列点的直线； 或者满足一定条件的最小集合 数据结构与算法（Python版） 0 优化问题 ❖ 一个经典案例是兑换最少个数的硬币问题 假设你为一家自动售货机厂家编程序，自动售货 机要每次找给顾客最少数量硬币； 假设某次顾客投进$1纸币，买了ȼ37的东西，要 找ȼ63，那么最少数量就是： 2个quarter(ȼ25） 、1个dime(ȼ10）和3个penny(ȼ1）， 一共6个 数据结构与算法（Python版） 找零兑换问题 0 ❖ 人们会采用各种策略来解决这些问题 ， 例 如最直观的“贪心策略” ❖ 一般我们这么做： 从最大面值的硬币开始，用尽量多的数量 有余额的，再到下一最大面值的硬币，还用尽量 多的数量， 一直到penny(ȼ1）为止 数据结构与算法（Python版） 贪心策略解决找零兑换问题 0 ❖ 贪心策略 因为我们每次都试图解决问题的尽量大的一部分 对应到兑换硬币问题，就是每次以最多数量的最 大面值硬币来迅速减少找零面值 ❖ “贪心策略 ”解决找零兑换问题 ， 在美元 或其他货币的硬币体系下表现尚好 贪心策略Greedy Method 数据结构与算法（Python版） 0 ❖ 但如果你的老板决定把自动售货机出口到 Elbonia ， 事情就会有点复杂 （系列漫画Dilbert里杜撰的国家） 因为这个古怪的国家除了上面3种面值之外，还 有一种【ȼ21】的硬币！ 数据结构与算法（Python版） 贪心策略失效 0 ❖ 按照 “贪心策略 ” ， 在Elbonia ， ȼ63还 是原来的6个硬币 ȼ63 = ȼ25*2 + ȼ10*1 + ȼ1*3 ❖ 但实际上最优解是3个面值ȼ21的硬币！ ȼ63 = ȼ21*3 ❖ “贪心策略”失效了 数据结构与算法（Python版） 贪心策略失效 0 数据结构与算法（Python版） Inflation in Elbonia 0 PROBLEM SOLVED ❖ 在本章我们研究了几种递归算法 ， 表明了 递归是解决某些具有自相似性的复杂问题 的有效技术 ❖ 递归算法“三定律” 递归算法必须具备基本结束条件 递归算法必须要减小规模，改变状态，向基本结 束条件演进 递归算法必须要调用自身 数据结构与算法（Python版） 0 本章小结 ❖ 某些情况下 ， 递归可以代替迭代循环 ❖ 递归算法通常能够跟问题的表达自然契合 ❖ 递归不总是最合适的算法 ， 有时候递归算 法会引发巨量的重复计算 ❖ “ 记忆化/函数值缓存 ”可以通过附加存 储空间记录中间计算结果来有效减少重复 计算 ❖ 如果一个问题最优解包括规模更小相同问 题的最优解 ， 就可以用动态规划来解决 数据结构与算法（Python版） 0 本章小结 ❖ 我们来找一种肯定能找到最优解的方法 贪心策略是否有效依赖于具体的硬币体系 ❖ 首先是确定基本结束条件 ， 兑换硬币这个 问题最简单直接的情况就是 ， 需要兑换的 找零 ， 其面值正好等于某种硬币 如找零25分，答案就是1个硬币！ 数据结构与算法（Python版） 找零兑换问题：递归解法 0 ❖ 其次是减小问题的规模 ，我们要对每种硬币尝试 1次 ，例如美元硬币体系： 找零减去1分(penny)后， 求兑换硬币最少数量（递归调用 自身）； 找零减去5分(nikel)后， 求兑换硬币最少数量 找零减去10分(dime)后， 求兑换硬币最少数量 找零减去25分(quarter)后，求兑换硬币最少数量 上述4项中选择最小的一个。 数据结构与算法（Python版） 找零兑换问题：递归解法 0 最小规模，直接返回 调用自身 减小规模： 每次减去一种硬币面值 挑选最小数量 数据结构与算法（Python版） 找零兑换问题：递归解法代码 0 ❖ 递归解法虽然能解决问题 ， 但其最大的问 题是： 极！ 其！ 低！ 效！ 对63分的兑换硬币问题，需要进行67,716,925 次递归调用！ 在我这台笔记本电脑上花费了40秒时间得到解： 6个硬币 数据结构与算法（Python版） 找零兑换