递归习题分析ppt课件.ppt
《递归习题分析ppt课件.ppt》由会员分享,可在线阅读,更多相关《递归习题分析ppt课件.ppt(42页珍藏版)》请在三一办公上搜索。
1、,Services,分析与求解,递归问题,Services,分析与求解,递归问题,递归的定义,一个过程或函数在其定义或说明中直接或间接调用自身的一种方法把一个大型复杂的问题层层的转换成一个与原问题相似的规模较小的问题来求解,优点,少量的程序就可以描述出解体过程所需要的重复计算大大减少了程序的代码量,缺点,运行效率较低,见递归的定义,Services,分析与求解,递归问题,递归问题的分析步骤,考虑问题规模在初始情况下的求解初始情况通常情况下是已经条件或者可以通过非递归求解的函数,考虑问题规模向较小规模的发展子问题的性质和原问题具有相同的性质,只是规模上比原问题有所缩小处理如何将子问题的解集合处理
2、得到原问题的解常常是约束使用递规思维的瓶颈,Services,分析与求解,递归问题,递归必须要有基本条件,f(n) = f(n-1) + f(n-2),递归必须朝基本条件运行,f(0) = 0f(n) = f(n/3+1) + n 1;,long function(int N) if(N=0) return 0; if(N1) return function(N/3+1);,long function(int N) return (function(N-1)+function(N-2);,递归问题的基本原则,分析与求解,递归问题,推理方法,归纳推理:从特殊归纳出普遍特殊:所有观察到的乌鸦都是黑
3、色的普遍:所有乌鸦都是黑色的,演绎推理:从前提的已知的事实,“必然的”得出的推理前提1:所有公乌鸦都是黑色的,所有母乌鸦都是黑色的前提2:乌鸦要么是公的,要么是母的结论:所有乌鸦都是黑色,基于公理的演绎推理总是正确的归纳推理在演绎上通常是无效的归纳是开放的,但是演绎是封闭的“对所有事情都坚持可靠的演绎上的正当有理的人会饿死 ” 大卫.休谟,分析与求解,递归问题,数学归纳方法,数学归纳法的定义证明当n等于任意一个自然数时,某命题成立。证明当n=1时,命题成立假设当n=m, m为任意自然数时命题成立,推导出n=m+1时命题也成立注意,这里的推导必须是演绎推理方法。,数学归纳法的变体从0以外的数字开
4、始只针对偶数或者奇数递降归纳法,超限归纳法将数学归纳法的第2步改成:假设当nm,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的时候也成立,分析与求解,递归问题,利用数
5、学归纳思想求解递规问题,最简单的数学归纳关系已知一个数组,对一个数组进行求和,解法,循环解法,依次遍历数组,求和,演绎推理思维,int Sum_Loop(int* array, int array_size) int sum = 0; for(int i = 0; i array_size; i+) sum += arrayi; return sum;,递规解法,假设前n-1项已经知道,那么加上第n项的值那么就是前n项的求和,归纳推理思想,int Sum_Recursion(int* array, int array_index) if(array_index = 0) return arra
6、y0; else return arrayarray_index + Sum_Recursion(array, array_index 1);,分析与求解,递归问题,1063斐波那契数列,描述,第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 = a = 20),菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数是多少。,输出,n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数的大小,输入,long function(int N) if(N = 1
7、 | N = 2) return 1; return (function(N-1)+function(N-2);,分析与求解,递归问题,1063斐波那契数列,解题思路,按照斐波那契数列的定义,对于每个输入调用计算的递归函数返回结果,主要问题,输入输出格式不对没有使用递归程序实现,分析与求解,递归问题,数学归纳关系适用场景,存在规模为n的问题和规模小于n的问题的映射,利用数学归纳法的思维去求解。,数学归纳关系求解过程,1. 确定问题规模。问题规模来自于原始问题中的各种变量,问题规模通常应该可以量化的表达,并且对于问题求解没有本质上的变化。2. 寻找初始条件初始条件通常是问题规模的特殊情况或者极端
8、化。在这种条件下这个问题应该足够简单。寻找初始条件和问题规模常常是一起考虑的。3. 归纳解决简单的归纳方法主要有两种:假设我们已经得到了问题规模为n-1的解决方案,针对这个解决方案考虑如何变换到问题规模为n的方案。(直接后继归纳)假设我们已经得到了所有问题规模小于n的解决方案,考虑问题规模为n的问题如何适用前面较小问题规模的来进行求解。(超限归纳),分析与求解,递归问题,猴子分苹果(单维上的直接后继归纳关系),描述,输入猴子数目n 和扔掉的个数 k,其中 k 小于 n,n 和 k 之间以空格间隔。,有1堆苹果共 m 个,由 n 只猴子按个数平均分配。每次到达苹果堆放地的猴子只有1只,而且每个猴
9、子都会平均分 1 次苹果。第1个到达的猴子将苹果平均分成 n 等份,但发现多 k ( k n )个,于是,将多余的k个扔掉,然后拿走其中的1等份。第 2 个猴子同样将剩余的苹果又分成 n 等份,也发现多 k 个,并同样将多余的 k 个扔掉,然后拿走其中1等份。之后的每个猴子都这样(将剩余的苹果又分成 n 等份,也发现多 k 个,并将多余的 k 个扔掉,然后拿走其中1等份)。假设最后的猴子分配后至少可以拿走1个苹果,请根据输入的 n 和 k值,计算最小的 m,输出,输出最小苹果数目,输入,分析与求解,递归问题,猴子分苹果(单维上的直接后继归纳关系),解题思路,寻找初始条件要想苹果总数最少,那么最
10、后一个猴子正好拿走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。,主要问题,输入输出格式不对没有使用递归程序实现结束条件没有搞清楚中间递推过程错误,long function(int N) if(N = La
11、stMonkeyNumber) return TotalMonkeyNumber + k; return TotalMonkeyNumber*function(N+1)/k + k;,分析与求解,递归问题,汉诺塔(单维上的直接后继归纳关系),描述,输入数据只有一个正整数 n (n = 16) , 表示开始时铁针 A 上的圆盘数。,略,输出,要求输出步数最少的搬动方案,方案是由若干个步骤构成的,输出的每行就表示一个移动步骤,例如,“A-B”就表示把铁针 A 最上层的一个圆盘移动到 B 上。,输入,分析与求解,递归问题,汉诺塔(单维上的直接后继归纳关系),解题思路,寻找初始条件汉诺塔中可以作为规模
12、的变量是盘子的数目。当盘子为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),输入输出格式不对依样画葫芦,移动的参数不对,主要问题,思考题,尝
13、试利用数学归纳法证明这样移动的方案的确是最优的,也就是移动次数是最少的。如果n是偶数,每次可以移动2个盘子,那么移动的方案又是如何?如果每次移动的盘子数目不超过k(从1到k之间的一个数字),那么移动的方案又是如何?如果柱子的数目不是固定的3,而是m,那么如何移动盘子?,分析与求解,递归问题,寻找最长公共子序列(多维上的直接后继归纳关系)已经两个数组a和b,子序列S如果既出现在a中,也出现在b中,那么S称为a和b的公共子序列。给定两个数组求解他们的最长的公共子序列的长度。如1, 3是序列1, 2, 3和1, 3, 5的最长公共子序列。,分析寻找初始条件初始条件只能从已经知道的条件中获取,题目中出
14、现的“规模” 有两个:a的长度和b的长度。那么最简单的,如果a的长度为1并且b的长度为1,那么可以知道最长公共子序列为1或者0。问题的规模是数组的长度,那么就要考虑数组的长度比M和N小的情况,一个最直接的想法是考虑a的前i(iM)个数字和b的前j(jN)个数字组成的序列。我们用L(i, j)表示我们得到的a的前i项和b 的前j项的公共子序列的长度,那么L(0, 0) = IsSame(a0, b0);寻找归纳关系设a的长度为M, b的长度为N,考虑以下问题:如何缩小问题的规模:问题的规模是a的长度i和b的长度j,那么对于L(i, j)的问题,我们可以考虑L(i-1, j)和L(i, j-1)以
15、及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) 如果ai和bj相等,那么L(i, j) = L(i-1, j-1) + 1。 b) 如果不相等,那么ai和bj不可能同时出现在公共子序列中,所以要么ai出现,此时L(i, j) = L(i, j-1),否则bj出现,此时L(i, j) = L(i-1, j)。到底ai出现还是bj出现,取决于两者的较大值。因此L(i, j) = max
16、(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
17、个盘子的方案都很容易。我们用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个盘子上,那么必须要满
18、足a(i) + 1 = a(i-1) 且 a(i) + 1 = a(i+1)想要确定这样的盘子,那么我们需要保存所有在N个盘子上放置M-1个苹果的方案。,void PlaceApple(int AppleNumber) if(AppleNumber = 1)/如果只放一个苹果,那么一定是把这个苹果放最后一个盘子上 for(int i = 0; i = Solutionsij-1 /产生一个可行方案,保存起来,分析与求解,递归问题,放苹果问题(多维上的超限归纳关系),解题思路,int PlaceApple(int AppleNumber, int PlateNumber, int limit)
19、if(AppleNumber PlateNumber * limit | PlateNumber = 0) return 0; if(AppleNumber = PlateNumber * limit | PlateNumber = 1) return 1; int sum; for(int i = limit; i AppleNumber/PlateNumber; i+) sum += PlaceApple(AppleNumber - i, PlateNumber 1, i); return sum;,分析与求解,递归问题,放苹果问题(多维上的超限归纳关系),解题思路,int PlaceAp
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 习题 分析 ppt 课件
链接地址:https://www.31ppt.com/p-1851749.html