ACM递归与动态规划(一).ppt

第十二讲 递归与动态规划 一 acm算法与程序设计 2 38 递归的基本思想 先来看看n的阶乘 常见的有两种做法 第一种做法 利用循环 直接求出 intn m 1 for inti 2 i n i m i printf d的阶乘是 d n n m 这一种做法 需要了解n 的算法 它的优点是运算速度快 3 38 递归的基本思想 第二种做法 利用公式n n n 1 使用递归函数求出 intfactorial intn if n 0 return 1 if n 1 n 0 return1 elsereturnn factorial n 1 该方法通过递推关系把原来问题缩小成一个更小规模的同类问题 并延续这一缩小规模的过程 直到在某一规模上 问题的解是已知的 这种解决问题的思想我们称为递归的思想 递归方法的总体思想是将待求解问题的解看作输入变量x的函数f x 通过寻找函数g 使得f x g f x 1 并且已知f 0 的值 就可以通过f 0 和g求出f x 的值 这种思想也可以推广到多个输入变量x y z等 x 1也可以推广到x x1 只要递归朝着出口的方向走就可以了 4 38 二叉树 1 链接地址 图1满二叉树 5 38 问题描述 如上图所示 由正整数1 2 3 组成了一棵无限大的二叉树 从某一个结点到根结点 编号是1的结点 都有一条唯一的路径 比如从10到根结点的路径是 10 5 2 1 从4到根结点的路径是 4 2 1 从根结点1到根结点的路径上只包含一个结点1 因此路径就是 1 对于两个结点x和y 假设他们到根结点的路径分别是 x1 x2 1 和 y1 y2 1 这里显然有x x1 y y1 那么必然存在两个正整数i和j 使得从xi和yj开始 有xi yj xi 1 yj 1 xi 2 yj 2 现在的问题就是 给定x和y 要求xi 也就是yj 6 38 问题描述 输入格式输入只有一行 包括两个正整数x和y 这两个正整数都不大于1000 输出要求输出只有一个正整数xi 输入样例104输出样例2 7 38 这个题目要求树上任意两个节点的最近公共子节点 分析这棵树的结构不难看出 不论奇数偶数 每个数对2做整数除法 就走到它的上层结点 我们可以每次让较大的一个数 也就是在树上位于较低层次的节点 向上走一个结点 直到两个结点相遇 如果两个节点位于同一层 并且它们不相等 可以让其中任何一个先往上走 然后另一个再往上走 直到它们相遇 设common x y 表示整数x和y的最近公共子节点 那么 根据比较x和y的值 我们得到三种情况 1 x与y相等 则common x y 等于x并且等于y 2 x大于y 则common x y 等于common x 2 y 3 x大于y 则common x y 等于common xy 2 3 解题思路 8 38 4 参考程序 includeintcommon intx inty if x y returnx if x y returncommon x 2 y returncommon x y 2 intmain void intm n scanf d d 9 38 逆波兰表达式 1 链接地址 10 38 问题描述 输入数据输入为一行 其中运算符和运算数之间都用空格分隔 运算数是浮点数输出要求输出为一行 表达式的值 输入样例 11 012 0 24 035 0输出样例1357 000000 11 38 这个问题看上去有些复杂 如果只是简单地模拟计算步骤不太容易想清楚 但是如果用递归的思想就非常容易想清楚 让我们根据逆波兰表达式的定义进行递归求解 在递归函数中 针对当前的输入 有五种情况 1 输入是常数 则表达式的值就是这个常数 2 输入是 则表达式的值是再继续读入两个表达式并计算出它们的值 然后将它们的值相加 3 输入是 4 输入是 5 输入是 后几种情况与2 相同 只是计算从 变成 3 解题思路 12 38 4 参考程序 include includedoubleexp void chara 10 scanf s a switch a 0 case returnexp exp case returnexp exp case returnexp exp case returnexp exp default returnatof a 13 38 4 参考程序 intmain void doubleans ans exp printf f ans return0 14 38 放苹果 1 链接地址 15 38 问题描述 输入数据第一行是测试数据的数目t 0 t 20 以下每行均包含两个整数m和n 以空格分开 1 m n 10 输出要求对输入的每组数据m和n 用一行输出相应的k 输入样例173输出样例8 16 38 所有不同的摆放方法可以分为两类 至少有一个盘子为空和所有盘子都不空 对于至少空着一个盘子的情况 则n个盘子摆放m个苹果的摆放方法数目与n 1个盘子摆放m个苹果的摆放方法数目相同 对于所有盘子都不空的情况 则n个盘子摆放m个苹果的摆放方法数目等于n个盘子摆放m n个苹果的摆放方法数目 我们可以据此来用递归的方法求解这个问题 设f m n 为m个苹果 n个盘子的放法数目 则先对n作讨论 如果n m 必定有n m个盘子永远空着 去掉它们对摆放苹果方法数目不产生影响 即if n m f m n f m m 当n m时 不同的放法可以分成两类 即有至少一个盘子空着或者所有盘子都有苹果 前一种情况相当于f m n f m n 1 后一种情况可以从每个盘子中拿掉一个苹果 不影响不同放法的数目 即f m n f m n n 总的放苹果的放法数目等于两者的和 即f m n f m n 1 f m n n 整个递归过程描述如下 3 解题思路 17 38 3 解题思路 intf intm intn if n 1 m 0 return1 if n m returnf m m returnf m n 1 f m n n 由上在知 当n 时 所有苹果都必须放在一个盘子里 所以返回 当没有苹果可放时 定义为 种放法 递归的两条路 第一条n会逐渐减少 终会到达出口n 1 第二条m会逐渐减少 因为n m时 我们会returnf m m 所以终会到达出口m 0 注 苹果 相同或不同 放入盘子 相同或不同 的问题 在 组合数学 中有更多的论述 可参考卢开澄的 组合数学 第2版 第2章中的stirling数 18 38 4 参考程序 includeintcount intx inty if y 1 x 0 return1 if x y returncount x x returncount x y 1 count x y y 19 38 4 参考程序 intmain void intt m n scanf d 20 38 红与黑 1 链接地址 21 38 问题描述 输入数据包括多个数据集合 每个数据集合的第一行是两个整数w和h 分别表示x方向和y方向瓷砖的数量 w和h都不超过20 在接下来的h行中 每行包括w个字符 每个字符表示一块瓷砖的颜色 规则如下 1 黑色的瓷砖 2 白色的瓷砖 3 黑色的瓷砖 并且你站在这块瓷砖上 该字符在每个数据集合中唯一出现一次 当在一行中读入的是两个零时 表示输入结束 22 38 问题描述 输出要求对每个数据集合 分别输出一行 显示你从初始位置出发能到达的瓷砖数 记数时包括初始位置的瓷砖 23 38 这个题目可以描述成给定一点 计算它所在的连通区域的面积 需要考虑的问题包括矩阵的大小 以及从某一点出发向上下左右行走时 可能遇到的三种情况 出了矩阵边界 遇到 遇到 设f x y 为从点 x y 出发能够走过的黑瓷砖总数 则f x y 1 f x 1 y f x 1 y f x y 1 f x y 1 这里需要注意 凡是走过的瓷砖不能够被重复走过 可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖 3 解题思路 24 38 4 参考程序 includeintw h charz 21 21 intf intx inty if x w y h 如果走出矩阵范围return0 if z x y return0 else z x y 将走过的瓷砖做标记return1 f x 1 y f x 1 y f x y 1 f x y 1 25 38 4 参考程序 intmain void inti j num while scanf d d 26 38 小结 在上面放苹果的例题中可以看出 在寻找从f x 向出口方向的递归方法时 我们是对可能的情况做了一步枚举 即将所有可能情况划分为至少有一个盘子空着和所有盘子至少有一个苹果两种情况 这种通过一步枚举进行递归的方法是很常用的 例如在例题 红与黑 中 我们枚举了在一个方格点上的四种可能的走法 例题 红与黑 与前几个例题不