《算法设计与问题求解》PPT第二章 递归算法设计.pptx

1、概述递归算法设计思想递归算法示例与过程分析递归转化为非递归目录能力拓展1 1概述概述 递归算法（递归算法（Recursive AlgorithmRecursive Algorithm）是计算机科学领域中研究数据结构和算法一种非常重要的方法，在算法设计中被广泛的使用。对于许多利用计算机解决的问题，递归思想为算法设计提供了一种简洁、易于理解且相对高效的途径。递归算法在执行过程中向自身发出一个或多个调用，或者在原问题的数据结构表示中依赖于相同类型结构的更小的实例表述。1 概述 递归是通过将一个大问题简化为一个或多个子问题来解决的过程，这些子问题要求在结构上与原始问题相同，并且子问题解决起来更为简单。

2、而这些子问题又可以用相同的方法简化为更小、更容易解决的子问题，最终的子问题将变得非常简单，且不需要进一步简化即可直接求解。然后，将最终的解返回到上一层，组合出上一层的解。通过逐级返回及组合即可得到原问题的解。1 概述一个场景：一个场景：一个有员工10000人的大公司，在年终的时候，要收集每一位员工的“个人年终终结报告”，以便作为对员工年终考核的依据之一。分析：分析：最简单的办法就是请公司的行政主管挨个去收集每个员工的“个人年终终结报告”，或者每个员工都各自将自己的“个人年终终结报告”交到行政主管那里。算法过程如下所示。elemtype 收集个人年终终结报告函数(n)/n为员工人数，n=1000

3、0 for(每一个员工)员工撰写并提交“个人年终终结报告”给行政主管；return；1 概述需要负责人花费大量的时间来逐一通知每个员工，效率低下。假设该公司的结构由若干个大部门组成，每个大部门下面有若干个小部门，每个小部门下面有若干个小组，每个小组下面有若干个员工。为了描述简单，我们将这些部门或组重新命名如下：大部门：一级组小部门：二级组小组：三级组员工：四级组 每个层级的任意一个组都有组长，每一个员工都是四级组的组长，而行政主管仅直接管理一级组的组长。1 概述 在上述架构下，只需要各级组的组长收集本组所辖下级各组或个人的“个人年终终结报告”就可以了，而行政主管负责人只需找所属的一级组组长收集

4、全部报告即可。算法过程如下所示。elemtype收集所属下级组个人年终终结报告函数(n)/n为下级组组数 if（n=1）/n等于1，即最低层级组员工 员工撰写并提交“个人年终终结报告”给组长；else 收集所属下级组个人年终终结报告函数(n)；/n为下级组组数 return；1 概述整个工作将会高效地完成 上例中，第二种方法所设计的算法程序结构就是典型的递归算法递归算法。递归算法所设计的函数的第一步包括确定当前问题是否代表简单问题的测试实例，上面例子中即指当前问题是否为最低层级的组，如果是最低层级的组，则函数直接处理解决问题；若不是,则当前问题应该被分解为更小的子问题，即要求下一层级的组长收集

5、报告上交。显然，每一次分解出来的子问题都通过相同的递归策略解决。1 概述2 2递归算法设计思想递归算法设计思想 大多数情况下，一个问题是否能够使用递归的方法解决取决于问题本身。递归解决方案以一种相当简单的方式进行处理，该方案的第一步包括检查当前问题是否属于最简单的子问题，即不需要或不能再分解的子问题。如果是这样，问题就直接解决了。如果不是，整个问题将分解为更小的子问题，每个子问题都通过递归解决。最后，将这些子问题的解决方案中重新组合，形成原始问题的解决方案。2 递归算法设计思想 以C/C+环境为参考环境，程序处理单元往往以函数的方式处理。在设计程序的过程中，如果在定义一个函数时，其函数体包含了

6、对自身的调用就称之为递归递归，该函数称之为递归函数递归函数。一般来讲，如果一个函数直接调用自己，称之为直接递归直接递归，如果是间接调用自己，称之为间接递归间接递归。2 递归算法设计思想直接递归直接递归伪代码：elemtype function1(.).;.;function1(.);.2 递归算法设计思想间接递归间接递归伪代码：2 递归算法设计思想elemtype function1(.).;.;function2(.);.elemtype function2(.).;.;function1(.);.如果将函数function2()的代码适当 处 理，替 换 掉function1()中的fun

7、ction2()调用，则最 终 转 换 成 了 对function1()的直接递归调用简单例子：简单例子：用函数f(n)来表示n的阶乘2 递归算法设计思想该问题可以用循环来求解，伪代码如下。long f(long n)long i,s=1;if(n=0)s=1;else for(i=1;in;coutf(n,1)1)穿孔圆盘，盘的尺寸由下到上依次变小。现要求将A柱子上的N个圆盘全部移动到C柱子上，依然按照从上到下，从小到大的顺序排列。盘子移动规则如下：（1）一次只能移动一个盘子。（2）移动过程中大盘子不能出现在小盘子上面。求总共需要移动多少步数。3 递归算法示例与过程分析递归算法示例与过程分析

8、-汉诺塔问题汉诺塔问题问题分析：问题分析：要把n个圆盘从A柱子移动到C柱子上，第一步应该怎么做？可以肯定，第一步能做的，是移动A最上面的那个圆盘，但是应该将其移到B还是C呢？不能确定，并且接下来的第二步、第三步都是很难确定的。面对这种复杂的问题，我们可以先尝试小规模的解决。当圆盘数量较少时，可以一步步穷举计算，但当圆盘数量变多时，其计算量就会非常大。因此如果可以将圆盘数量多的情况转化为数量少的情况，问题就会简单化。当圆盘数量为2时通过把小的盘子先移动到B，大的盘子再放到C，最后小的从B到C就完成了，这样只需三步即可，如图所示：3 递归算法示例与过程分析递归算法示例与过程分析-汉诺塔问题汉诺塔问

9、题 当盘子的数量大于2时，可以把A柱中最上面的n-1个圆盘看成一个整体，那么就会变成n=2的情况了，即n-1个圆盘组成的整体放到B，最大的放到C，然后再把n-1个圆盘放到C。这样就做到了一开始提出的把多数化为少数，化繁为简。设函数hanno(n,x,y,z)代表把n个圆盘从x移到z，y作为过渡所需的步数，那么可以推出方程：hanno(n,a,b,c)=hanno(n-1,a,c,b)+1+hanno(n-1,b,a,c)。hanno(n-1,a,c,b)表示上面的n-1个圆盘从A移动到B，hanno(n-1,b,a,c)表示再把这n-1个圆盘从B移动到C，加1则表示第n个圆盘从A到C。3 递归

10、算法示例与过程分析递归算法示例与过程分析-汉诺塔问题汉诺塔问题参考代码：int hanno(int n,char a,char b,char c)if(n 0)return hanno(n-1,a,c,b)+hanno(n-1,b,a,c)+1;/n-1个先从a到b，再从b到c else if(n=0)return 0;int main()int n;cinn;couthanno(n,a,b,c)=0&si0=9)return atof(si.c_str();/字符串转数字 else if(si0=+)int x=bolan(-i),y=bolan(-i);/求得嵌套在里面的逆波兰表达式 re

11、turn y+x;else if(si0=-)i n t x=b o l a n(-i),y=bolan(-i);return y-x;else if(si0=*)i n t x=b o l a n(-i),y=bolan(-i);return y*x;else if(si0=/)i n t x=b o l a n(-i),y=bolan(-i);return y/x;3 递归算法示例与过程分析递归算法示例与过程分析-逆波兰表达式逆波兰表达式样例输入：3 5 2-*7+样例输出：16样例解释：bolan(7)=bolan(5)+bolan(6)=bolan(5)+7 bolan(5)=bola

12、n(1)*bolan(4)=3*bolan(4)bolan(4)=bolan(2)-bolan(3)=5-2=3那么可以推出：bolan(5)=3*3=9、bolan(7)=7+9=16。bolan(7)bolan(5)bolan(2)bolan(6)bolan(3)bolan(4)bolan(1)返回3*3=9返回5返回2返回5-2=3返回7返回3返回9+7=16+*-4 4递归转化为非递归递归转化为非递归 递归转尾递归递归转尾递归 递归转非递归递归转非递归4 递归转化为非递归递归转化为非递归例例2.3 2.3 斐波那契数列转尾递归求解斐波那契数列转尾递归求解问题描述：设f(0)=1，f(1

13、)=1，f(n)=f(n-1)+f(n-2)，给定整数n，求f(n)。解题思路：斐波那契数列的递归代码如下：long long Fib(int n)if(nn;f0=f1=1;for(int i=2;i=n;i+)fi=fi-1+fi-2;coutfnendl;4 递归转化为非递归递归转化为非递归例例2.5 2.5 递归转化为非递归递归转化为非递归-间接转换法（二叉树遍历的非递归实现）间接转换法（二叉树遍历的非递归实现）问题描述：问题描述：给出一棵根节点为1的二叉树和每个节点的左右儿子节点，要求用前序遍历方式遍历这棵二叉树。解题思路：解题思路：设某个节点为u，其左儿子节点为lsonu,右儿子节

14、点为rsonu。利用递归方式遍历二叉树的过程如下：从根节点开始递归，判断左儿子节点是否为空，如果不是，则继续递归遍历左儿子节点，在递归完左子树后，判断右儿子节点是否为空，如果不是，则递归遍历右儿子节点。4 递归转化为非递归递归转化为非递归递归参考代码：void dfs(int u)coutun;for(int i=1;ilsonirsoni;stacks;s.push(1);while(!s.empty()int node=s.top();s.pop();coutnode2时有an=2*an-1+3*an-2，则称该数列为K数列。给定整数k，求数列第k项是多少。解题思路：解题思路：该题为斐波那

15、契数列数列的变形，但本质其实是一样的，都可以用普通递归、尾递归还有非递归求解，下面给出这三种解法。5 能力拓展-K数列普通递归：普通递归：和普通的斐波那契一样，同样设f(i)表示数列第i项的值，要求第i项，就先求得f(i-1)和f(i-2)，那么利用递归调用自己本身求得，最后返回3*f(i-1)+2*f(i-2)即可。代码如下所示：long long f(int n)/结果可能会超过int范围，所以用long long if(n=1|n=2)return 1;else return 2*f(n-1)+3*f(n-2);5 能力拓展-K数列尾递归：尾递归：在求解斐波那契尾递归的时候，我们是设Fi

16、b(n,m,a,b)表示递归到第m个数，还需要递归n次，第m个数的值为a，第m-1个数为b。此问题的表示方法于斐波那契数列相似，不同的是每次递归到下一个状态时，a位置的值为下一个数的值，而下一个数的值为当前数乘2加上前一个数乘3，所以递归转移式要改变为：Fib(n,m,a,b)Fib(n-1,m+1,2*a+3*b,a)。代码如下所示：long long Fib(int n,int m,long long a,long long b)/结果可能会超过int范围，所以 /用long long if(n=0)return a;else return Fib(n-1,m+1,2*a+3*b,a);/

17、还要递归n-1次，下一到达第m+1个5 能力拓展-K数列非递归：非递归：非递归的实现相对简单，只需用数组去存下这个数列的值，然后循环去计算出这个数列即可。代码如下所示：long long a35;int main()int n;cinn;a1=a2=1;for(int i=3;i=n;i+)ai=2*ai-1+3*ai-2;coutanmn;coutF(m,n)endl;return 0;5 能力拓展-猴子爬树样例输入：3 2样例输出：30样例解释：当m=3，n=2时，递归状态转移如图2.13所示：F(3,2)F(2,6)F(0,30)F(1,14)5 能力拓展-分黑球 有m个相同的盒子和n个

18、相同的黑球，把n个黑球放到这m个盒子里，允许有盒子为空，求有多少种放法？注意：1 2 3 和3 2 1是同一种放法。解题思路：解题思路：将盒子从小到大编号为1、2、3、.、m，设第i个盒子里放si个黑球，由于数量调换是同一种放法，所以可令s1s2s3.sm。然后我们用递归的方式去枚举每个盒子里面放多少个黑球即可。5 能力拓展-分黑球 设f(x,y,pre)表示将x个黑球放在y个盒子里，且前一个盒子放了pre个黑球的放法，初始状态时pre为-1。当递归到第i个盒子时，如果pre为-1，表示当前为第一个盒子，那么能放的黑球数量就在区间0,x里，如此逐一枚举即可；如果pre不为-1，那么在这个盒子里

19、放的黑球数k就不能超过前一个盒子，即必须k=pre，而且剩下的x个黑球也存在k=x，综合两种情况可知k=min(pre,x)，因此这个盒子里能放的黑球数量就在区间0,min(pre,x)。设t=min(pre,x)，递归过程如图所示：5 能力拓展-分黑球递归出口条件为：y=0，此时所有的盒子都已经遍历过了。但还需注意x可能不为0，即还剩有黑球没有分配，这种情况说明当前放法不合法。因此，在递归出口的时候要判断x是否为0，若为0，则返回1，反之则为0。代码如下：int f(int n,int m,int pre)if(m=0)if(n)return 0;/还有剩余的黑球，则不合法 else return 1;int ans=0;if(pre=-1)/当前为第一个盒子 for(int i=0;i=n;i+)ans+=f(n-i,m-1,i);else for(int i=0;i=min(pre,n);i+)/最多只能放min(pre,n)个 ans+=f(n-i,m-1,i);return ans;