递归习题分析课件.ppt

Services 分析与求解 递归问题 Services 分析与求解 递归问题 递归的定义 一个过程或函数在其定义或说明中直接或间接调用自身的一种方法把一个大型复杂的问题层层的转换成一个与原问题相似的规模较小的问题来求解 优点 少量的程序就可以描述出解体过程所需要的重复计算大大减少了程序的代码量 缺点 运行效率较低 见递归的定义 Services 分析与求解 递归问题 递归问题的分析步骤 考虑问题规模在初始情况下的求解初始情况通常情况下是已经条件或者可以通过非递归求解的函数 考虑问题规模向较小规模的发展子问题的性质和原问题具有相同的性质 只是规模上比原问题有所缩小处理如何将子问题的解集合处理得到原问题的解常常是约束使用递规思维的瓶颈 Services 分析与求解 递归问题 递归必须要有基本条件 f n f n 1 f n 2 递归必须朝基本条件运行 f 0 0f n f n 3 1 n 1 longfunction intN if N 0 return0 if N 1 returnfunction N 3 1 longfunction intN return function N 1 function N 2 递归问题的基本原则 分析与求解 递归问题 推理方法 归纳推理 从特殊归纳出普遍特殊 所有观察到的乌鸦都是黑色的普遍 所有乌鸦都是黑色的 演绎推理 从前提的已知的事实 必然的 得出的推理前提1 所有公乌鸦都是黑色的 所有母乌鸦都是黑色的前提2 乌鸦要么是公的 要么是母的结论 所有乌鸦都是黑色 基于公理的演绎推理总是正确的归纳推理在演绎上通常是无效的归纳是开放的 但是演绎是封闭的 对所有事情都坚持可靠的演绎上的正当有理的人会饿死 大卫 休谟 分析与求解 递归问题 数学归纳方法 数学归纳法的定义证明当n等于任意一个自然数时 某命题成立 证明当n 1时 命题成立假设当n m m为任意自然数时命题成立 推导出n m 1时命题也成立注意 这里的推导必须是演绎推理方法 数学归纳法的变体从0以外的数字开始只针对偶数或者奇数递降归纳法 超限归纳法将数学归纳法的第2步改成 假设当n m m为任意自然数时命题成立 推导出n m时命题也成立 分析与求解 递归问题 更一般的归纳法 良基关系对于类X上一个二元关系R被称为是良基的 当且仅当所有X的非空子集都有一个R 极小元 就是说对于X的每一个非空子集S 都存在一个S中的元素m使得对于所有S中的s 二元组 s m 都不在R中 数学归纳法是良机归纳法的一种特殊情况0是自然数集合上后继关系的一个极小元 因此只需要证明对于n 0 命题成立 m m 1 属于后继关系 因此假设n m成立的时候 只需要证明n m 1的时候也成立 分析与求解 递归问题 利用数学归纳思想求解递规问题 最简单的数学归纳关系已知一个数组 对一个数组进行求和 解法 循环解法 依次遍历数组 求和 演绎推理思维 intSum Loop int array intarray size intsum 0 for inti 0 i array size i sum array i returnsum 递规解法 假设前n 1项已经知道 那么加上第n项的值那么就是前n项的求和 归纳推理思想 intSum Recursion int array intarray index if array index 0 returnarray 0 elsereturnarray array index Sum Recursion array array index 1 分析与求解 递归问题 1063斐波那契数列 描述 第1行是测试数据的组数n 后面跟着n行输入 每组测试数据占1行 包括一个正整数a 1 a 20 菲波那契数列是指这样的数列 数列的第一个和第二个数都为1 接下来每个数都等于前面2个数之和 给出一个正整数a 要求菲波那契数列中第a个数是多少 输出 n行 每行输出对应一个输入 输出应是一个正整数 为菲波那契数列中第a个数的大小 输入 longfunction intN if N 1 N 2 return1 return function N 1 function N 2 分析与求解 递归问题 1063斐波那契数列 解题思路 按照斐波那契数列的定义 对于每个输入调用计算的递归函数返回结果 主要问题 输入输出格式不对没有使用递归程序实现 分析与求解 递归问题 数学归纳关系适用场景 存在规模为n的问题和规模小于n的问题的映射 利用数学归纳法的思维去求解 数学归纳关系求解过程 1 确定问题规模 问题规模来自于原始问题中的各种变量 问题规模通常应该可以量化的表达 并且对于问题求解没有本质上的变化 2 寻找初始条件初始条件通常是问题规模的特殊情况或者极端化 在这种条件下这个问题应该足够简单 寻找初始条件和问题规模常常是一起考虑的 3 归纳解决简单的归纳方法主要有两种 假设我们已经得到了问题规模为n 1的解决方案 针对这个解决方案考虑如何变换到问题规模为n的方案 直接后继归纳 假设我们已经得到了所有问题规模小于n的解决方案 考虑问题规模为n的问题如何适用前面较小问题规模的来进行求解 超限归纳 分析与求解 递归问题 猴子分苹果 单维上的直接后继归纳关系 描述 输入猴子数目n和扔掉的个数k 其中k小于n n和k之间以空格间隔 有1堆苹果共m个 由n只猴子按个数平均分配 每次到达苹果堆放地的猴子只有1只 而且每个猴子都会平均分1次苹果 第1个到达的猴子将苹果平均分成n等份 但发现多k k n 个 于是 将多余的k个扔掉 然后拿走其中的1等份 第2个猴子同样将剩余的苹果又分成n等份 也发现多k个 并同样将多余的k个扔掉 然后拿走其中1等份 之后的每个猴子都这样 将剩余的苹果又分成n等份 也发现多k个 并将多余的k个扔掉 然后拿走其中1等份 假设最后的猴子分配后至少可以拿走1个苹果 请根据输入的n和k值 计算最小的m 输出 输出最小苹果数目 输入 分析与求解 递归问题 猴子分苹果 单维上的直接后继归纳关系 解题思路 寻找初始条件要想苹果总数最少 那么最后一个猴子正好拿走1个苹果 需要求出第1个猴子取苹果时候的总数 因此这个问题的 规模 与猴子取苹果的序号i有关 用a i 表示第i个猴子取苹果时候的总数 于是a n n k寻找归纳关系第i个猴子取的时候总数为a i 则第i 1个猴子取得时候总数为a i 1 a i k a i k n由于我们的基本条件是a n 我们需要由a i 1 推导出a i 才是向基本条件出发 于是根据1可以得到 a i n a i 1 k k 主要问题 输入输出格式不对没有使用递归程序实现结束条件没有搞清楚中间递推过程错误 longfunction intN if N LastMonkeyNumber returnTotalMonkeyNumber k returnTotalMonkeyNumber function N 1 k k 分析与求解 递归问题 汉诺塔 单维上的直接后继归纳关系 描述 输入数据只有一个正整数n n 16 表示开始时铁针A上的圆盘数 略 输出 要求输出步数最少的搬动方案 方案是由若干个步骤构成的 输出的每行就表示一个移动步骤 例如 A B 就表示把铁针A最上层的一个圆盘移动到B上 输入 分析与求解 递归问题 汉诺塔 单维上的直接后继归纳关系 解题思路 寻找初始条件汉诺塔中可以作为规模的变量是盘子的数目 当盘子为1的时候的情况十分的简单 我们将其作为初始条件 用move i p q 表示将i个盘子从p移动到q move 1 p q 就是p q p q A B C 寻找归纳关系先看看i 2时 move 2 A C 的动作 move 1 A B A C move 1 B C 我们假设已经 一次性 将n 1个盘子在柱子之间移动的方案已经得到 那么移动n个盘子的问题 就和i 2的时候情况非常相似了 move n 1 A B A C move n 1 B C 输入输出格式不对依样画葫芦 移动的参数不对 主要问题 思考题 尝试利用数学归纳法证明这样移动的方案的确是最优的 也就是移动次数是最少的 如果n是偶数 每次可以移动2个盘子 那么移动的方案又是如何 如果每次移动的盘子数目不超过k 从1到k之间的一个数字 那么移动的方案又是如何 如果柱子的数目不是固定的3 而是m 那么如何移动盘子 分析与求解 递归问题 寻找最长公共子序列 多维上的直接后继归纳关系 已经两个数组a和b 子序列S如果既出现在a中 也出现在b中 那么S称为a和b的公共子序列 给定两个数组求解他们的最长的公共子序列的长度 如1 3是序列1 2 3和1 3 5的最长公共子序列 分析寻找初始条件初始条件只能从已经知道的条件中获取 题目中出现的 规模 有两个 a的长度和b的长度 那么最简单的 如果a的长度为1并且b的长度为1 那么可以知道最长公共子序列为1或者0 问题的规模是数组的长度 那么就要考虑数组的长度比M和N小的情况 一个最直接的想法是考虑a的前i i M 个数字和b的前j j N 个数字组成的序列 我们用L i j 表示我们得到的a的前i项和b的前j项的公共子序列的长度 那么L 0 0 IsSame a 0 b 0 寻找归纳关系设a的长度为M b的长度为N 考虑以下问题 如何缩小问题的规模 问题的规模是a的长度i和b的长度j 那么对于L i j 的问题 我们可以考虑L i 1 j 和L i j 1 以及L i 1 j 1 其中L i 1 j L i 1 j 1 1 L i j 1 L i 1 j 1 1 如何通过子问题得到原始问题的解 我们假设已经得到L i 1 j L i j 1 和L i 1 j 1 a 如果a i 和b j 相等 那么L i j L i 1 j 1 1 b 如果不相等 那么a i 和b j 不可能同时出现在公共子序列中 所以要么a i 出现 此时L i j L i j 1 否则b j 出现 此时L i j L i 1 j 到底a i 出现还是b j 出现 取决于两者的较大值 因此L i j max L i 1 j L i j 1 分析与求解 递归问题 前继求和 单维上的超限归纳关系 f n f n 1 f n 2 f 0 描述 输入为一行 其中运算符和运算数之间都用空格分隔 运算数是浮点数 把M个同样的苹果放在N个同样的盘子里 允许有的盘子空着不放 问共有多少种不同的分法 用K表示 输出 输出为一行 表达式的值 输入 放苹果问题 多维上的超限归纳关系 分析与求解 递归问题 放苹果问题 多维上的超限归纳关系 解题思路 寻找初始条件这个问题中的问题规模取决于两个方面 一个是盘子的数目 一个是苹果的总数 我们将M个苹果放在1个盘子和1个苹果放在N个盘子的方案都很容易 我们用f i j 表示将i个苹果放在j个盘子的方案数 为了避免重复的方案 我们假定盘子上的苹果数目是递增的 递减也是可以的 这里采用递增的假定 用a i 表示放在第i个盘子上的数目 则a 0 a 1 a N a 0 a 1 a N M利用这些关系我们去尝试减少问题的规模 分析与求解 递归问题 放苹果问题 多维上的超限归纳关系 解题思路 寻找归纳关系我们依旧试图减少问题的规模1 首先考虑减少苹果的总数M 如果我们已经在N个盘子上放了M 1个苹果 那么我们如何放最后一个苹果 按照假定 如果我们把这个苹果放在第i个盘子上 那么必须要满足a i 1 a i 1 且a i 1 a i 1 想要确定这样的盘子 那么我们需要保存所有在N个盘子上放置M 1个苹果的方案 voidPlaceApple intAppleNumber if AppleNumber 1 如果只放一个苹果 那么一定是把这个苹果放最后一个盘子上for inti 0 i Solutions i j 1 产生一个可行方案 保存起来 分析与求解 递归问题 放苹果问题 多维上的超限归纳关系 解题思路 intPlaceApple intAppleNumber intPlateNumber intlimit if AppleNumber PlateNumber limit PlateNumber 0 return0 if AppleNumber PlateNumber limit PlateNumber 1 return1 intsum for inti limit i AppleNumber PlateNumber i sum PlaceApple AppleNumber i PlateNumber 1 i returnsum 分析与求解 递归问题 放苹果问题 多维上的超限归纳关系 解题思路 intPlaceApple intAppleNumber intPlateNumber if AppleNumber 0 PlateNumber 0 return0 if AppleNumber 1 AppleNumber 0 PlateNumber 1 return1 intsum for inti limit i AppleNumber PlateNumber i sum PlaceApple AppleNumber PlateNumber i PlateNumber 1 returnsum 分析与求解 递归问题 放苹果问题 多维上的超限归纳关系 解题思路 intPlaceApple intAppleNumber intPlateNumber if AppleNumber 0 PlateNumber 0 return0 if AppleNumber 1 AppleNumber 0 PlateNumber 1 return1 returnPlaceApple AppleNumber PlateNumber 1 PlaceApple AppleNumber PlateNumber PlateNumber 分析与求解 递归问题 数学归纳关系使用小结 1 问题规模通常很容易识别 问题规模通常是问题中的某个 数量 如盘子的个数 数组的长度等 2 初始条件是对于问题规模的特殊情况的处理初始条件下这个问题一般十分的简单3 归纳解决的关键是寻找子问题到原始问题之间的转换对于问题规模首先尝试演绎归纳 即假定问题规模n 1已经解决 考虑第n个子问题如果存在多维的问题规模 那么原始问题可能和这多个问题规模上子问题相关如果直接从n 1很难推导出问题规模n的问题 那么尝试超限归纳 考虑从所有问题规模小于n的子问题推导问题规模n的原始问题演绎归纳实际上是超限归纳的一种特殊情况 数学归纳关系局限 一些情况下 我们无法找到可以量化的问题规模或者无法简单的找到初始条件 分析与求解 递归问题 树形递归问题 定义在树上的良基归纳法递归问题可以和一颗树一一对应尽管问题规模无法直接的 数量化 但是问题直观上总是向问题规模更小的情况发展 如果增加了一定的约束条件之后 问题变成简单的相似的问题 我们就将这个子问题作为原始问题的子节点 在树形递归问题中 初始情况可能有多种情况根据具体的情况判断什么是递归问题的结束条件或者初始条件 一般都是加上一定的约束条件使得问题较为简单树中一个节点和子节点之间的关系也就是递归问题中的关系 任何一个节点都代表了递归问题的一个子问题 解决子节点的方法都和解决整个树的方法是一致的数学归纳关系是树形递归问题的特例单维的数学归纳关系是退化的树 线n维的数学归纳关系是n叉树 分析与求解 递归问题 逆波兰表达式 树形递归问题 描述 输入为一行 其中运算符和运算数之间都用空格分隔 运算数是浮点数 逆波兰表达式是一种把运算符前置的算术表达式 例如普通的表达式2 3的逆波兰表示法为 23 逆波兰表达式的优点是运算符之间不必有优先级关系 也不必用括号改变运算次序 例如 2 3 4的逆波兰表示法为 234 本题求解逆波兰表达式的值 其中运算符包括 四个 输出 输出为一行 表达式的值 输入 分析与求解 递归问题 逆波兰表达式 树形递归问题 分析 对于表达式 34 12 等同于 34 12 我们必须首先计算 34和 12之后才可以得到整个表达式的值 每个运算符后面一定跟随着两个子表达式 子表达式可能是数字也可能还是运算 我们总是可以将一个逆波兰表达式转换成一个树 在这个树中 任何一个子树也都是逆波兰表达式 树的叶节点一定都是数字节点 基于这个树 我们计算这个逆波兰表达式的值 对于叶节点 那它只可能是数字 表达式的值就是这个数字 如果不是叶节点 那么它的值由它的两个子树的值决定 用EXP node 表示一个逆波兰表达式的值 那么有EXP node EXP node LeftChild OPEXP node RightChild OP是这个节点的运算符如果存在了这样一棵树 那么我们的计算就很容易了 因此问题的关键在于如何建立这么一棵树 建树的过程和计算值的过程是一致的 当我们读取了一个运算符 那么一定存在两个子树 我们首先建立左子树 返回左子树的值 之后建立右子树 返回右子树的值 34 12 12 分析与求解 递归问题 逆波兰表达式 树形递归问题 解题思路 如果输入为一个数 那么表达式的值就为这个数的值如果输入只有一个运算符 比如输入了 那么后面的输入一定会产生两组值 这两组值可能是直接的数字 比如3和4 那么结果就是3 4 也可能还是表达式比如输入了 34和 12 这个时候的值就是 3 4 1 2 而表达式 34和 12处理和当前表达式的处理是相同的 本质上是利用递归调用对输入构成一个栈的数据结构 主要问题 输入输出格式不对不知道如何判断输入的是运算符还是数字不知道如何递归计算表达式的值 思维局限在如何对一个已经输入的字符串进行处理 floatfunction cin str switch str 0 case returnfunction function case returnfunction function case returnfunction function case returnfunction function default returnatof str 分析与求解 递归问题 二叉树 树形递归问题 描述 输入只有一行 包括两个正整数x和y 这两个正整数都不大于1000 由正整数1 2 3 组成了一棵无限大的二叉树 对于两个结点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 输出 输出只有一个正整数xi 输入 分析与求解 递归问题 二叉树 树形递归问题 分析 相比于逆波兰表达式 二叉树问题已经有了树的模型 现在需要考虑的是问题的初始条件和子问题的关系 如果这两个数字相同 这两个数字的公共祖先就是自己本身 这就是问题的基本条件 如果这两个数字不相同 我们 翻族谱 去发现公共祖先 因此 如果两个节点并不一致 那么我们继续向上寻找使得这两个节点变成相同的节点 问题是我们如何向上寻找 如果这两个节点高度不一致 那么我们只有提升那个 矮 节点才有可能使得两个节点达到一致 如果这两个节点一致 但是并不是一样的节点 那么就一起提升 分析与求解 递归问题 利用归纳结构解决递归问题 寻找初始条件考虑问题在某些特定情况下的变化寻找归纳关系不管何种归纳方法 都存在着从原始问题向子问题的发展 对于归纳方法的分类只是提供了一种去寻找归纳关系的套路 照着这些套路去思考总会能得到一些启发 如果存在数组或者多个变量的问题 那么尝试减少一个变量的子问题如果存在树或者其他结构 那么尝试着看他们的父节点或者子节点所代表的子问题在得到了子问题的解之后 需要考虑如何组合来得到父节点的解 这个过程有时候比较麻烦 是递归解决问题的关键 利用递归的常见算法 回溯法 n n 1分治法 n n 2 分析与求解 递归问题 回溯递归问题 BoolBackTracking intn foreachCANDIDATEcaboutn 对第n步的所有可能解进行枚举 尝试每个可能cMAKEsolution n cifn LAST ELEMENT 如果已经对所有步骤上的解 那么判断是否符合题目中的约束if solutionISACOMPLETESOLUTION OUTPUTsolutionreturntrueelsereturnfalseelseif BackTracking n 1 如果c可以到达一个可行解 那么说明c是一个正确尝试returntrue returnfalse 如果所有的尝试都不能到达可行解 那么说明这个问题不可解 分析与求解 递归问题 回溯递归问题 回溯问题可以转换成为树形递归问题 分析与求解 递归问题 红与黑 回溯递规问题 描述 包括多个数据集合 每个数据集合的第一行是两个整数W和H 分别表示x方向和y方向瓷砖的数量 W和H都不超过20 在接下来的H行中 每行包括W个字符 每个字符表示一块瓷砖的颜色 规则如下 黑色的瓷砖 白色的瓷砖 黑色的瓷砖 并且你站在这块瓷砖上 该字符在每个数据集合中唯一出现一次当在一行中读入的是两个零时 表示输入结束 有一间长方形的房子 地上铺了红色 黑色两种颜色的正方形瓷砖 你站在其中一块黑色的瓷砖上 只能向相邻的四块瓷砖中的黑色瓷砖移动 请写一个程序 计算你总共能够到达多少块黑色的瓷砖 输出 输出为一行 表达式的值 输入 分析与求解 递归问题 红与黑 回溯递规问题 分析 如果站在一个黑色的砖上 但是四周都不是黑色的 或者四周都走过了 那么就无法再前进 这个就是问题的基本条件 如果站在其中一块黑砖上 我们尝试的向四周走动 每走一步就增加一步 为了避免重复计数 走过的黑砖被标记不可以再行走 在这个问题中 本质上也是回溯解法 不断的向四周进行尝试的走动 但是这个问题中不发生尝试错误的 修正 voidWalkAround intx inty if Bricks i j RED Visited i j true return TotalVistedNumber 走到了一个新的黑砖上 标记这个黑砖已经被访问 并且增加计数Visited i j true 向四周走动WalkAround x 1 y WalkAround x 1 y WalkAround x y 1 WalkAround x y 1 分析与求解 递归问题 红与黑 回溯递规问题 分析与求解 递归问题 分解因数 回溯递规问题 描述 第1行是测试数据的组数n 后面跟着n行输入 每组测试数据占1行 包括一个正整数a 1 a 32768 给出一个正整数a 要求分解成若干个正整数的乘积 即a a1 a2 a3 an 并且1 a1 a2 a3 an 问这样的分解的种数有多少 注意到a a也是一种分解 输出 n行 每行输出对应一个输入 输出应是一个正整数 指明满足要求的分解的种数 输入 分析与求解 递归问题 分解因数 回溯递规问题 分析 如果这个数a是一个素数 那么肯定不能够再进行分解了 分解的情况只有一种