算法设计与分析实用教程-电子教案-杨克昌 第4章 递归

《算法设计与分析实用教程-电子教案-杨克昌 第4章 递归》由会员分享，可在线阅读，更多相关《算法设计与分析实用教程-电子教案-杨克昌 第4章 递归（31页珍藏版）》请在金锄头文库上搜索。

1、教学要求 了解递归算法的概念与递归设计要领 掌握应用递归算法求解排序与选择、实现排列组合等典型案例 了解递归算法中的回溯过程 本章重点 递归关系与边界条件的探求与确定,第 4 章 递 归,4.1 分治策略与递归,1. 分治策略 (1) 当求解一个规模很大的问题时，可以考虑分解，即把原问题分解为若干个较小规模的问题处理，以便各个击破，分而治之，这就是分治的设计思想。 (2) 如果求解的问题可分解为k个子问题，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，这种分治是可行的。 (3) 通过例4-1 棋盘覆盖问题理解分治策略的应用。,2. 递归 (1) 递归（Recursion）是一个过程

2、或函数在其定义中直接或间接调用自身的一种方法，就是利用系统堆栈，实现函数自身调用或相互调用的过程。在通往边界的过程中，都会把单步地址保存下来，再按照先进后出进行运算。 (2) 递归算法通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。 (3) 递归需要有递归关系式与边界条件，递归过程有递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。,3. 递归关系与边界条件,（1） 递归设计需要有递归关系，这是递归的依据；同时需要有边界条件，这是递归的基础，是控制递归过程结束的条件。 （2） 递归过程分为递归前进段和递归返回段。当边界条件不满

3、足时，递归前进；当边界条件满足时，递归返回。 （3）编写递归函数，并设计主函数调用递归函数。,例4-2 应用递归计算n!。 计算整数n的阶乘n!是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 （1）描述递归关系 注意到，当n1时，n!=n*(n1)!，这就是一种递归关系。对于特定的k!，它只与k和(k1)!有关。 （2）确定递归边界 递归边界为: n=1时，n!=1。对于任意给定的n，程序将最终求解到1!。,4. 举例说明,（3）求n!的递归函数 long f(int x) long g; if(x=0) printf(“x=0, 输入错误！“); else if(x=1)

4、 g=1; else g=x*f(x1); return(g); （4）设计调用递归函数的主程序 void main() int n;long y; scanf(“%d“, ,（5） 递归调用的实现 主函数调用f(n)后即进入函数f(n)执行。 设执行本程序时输入为n=5，即求 5!。在主函数中的调用语句即为y=f(5)，执行f函数，由于n=5，不等于1，故应执行g=n*f(n1)，即g=5*f(4)。该语句调用f(4), 进行4次递归调用后，f函数参数值变为1，故不再继续递归调用而开始逐层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为2*1=2，f(3)的返回值为3*2=6，f(

5、4) 的返回值为4*6=24，最后返回值f(5)为5*24=120。,4.2 汉诺塔游戏,（1）有三根桩子A、B、C。A桩上有n个圆盘，最大的一个圆盘在底下，其余圆盘一个比一个小，依次叠上去。 （2）每次只移动一块圆盘，规定小盘的只能叠放在大盘的上面，而大盘不能叠放在小盘的上面。 （3）目标是把所有n个圆盘从A桩全部移到C桩上，如图4-4所示。 试求解n个圆盘从A桩全部移到C桩上的移动次数，并展示这n个圆盘的移动过程。,4.2.1 移动次数求解,设计要点：设移动n个盘需g(n)次完成。 (1) 首先将n个盘的上面的n-1个盘借助C桩从A桩移到B桩上，需g(n-1)次； (2) 然后将A桩上最大

6、的第n个盘移到C桩上，需1次； (3) 最后，将B桩上的n-1个盘借助A桩移到C桩上，需g(n-1)次。 因而有递归关系：g(n)=2*g(n-1)+1 初始条件(递归出口)：g(1)=1,递归设计要点： 设递归函数hn(m,a,b,c)展示把m个盘从A桩借助B桩移到C桩的过程,函数mv(a,c)输出从a桩到c桩的一次移动过程，即AC。 实现hn(m,a,b,c)，当m=1时，即mv(a,c)。 当m1时，分以下三步： (1) 将A桩上面的m-1个盘借助C桩移到B桩上，即hn(m-1,a,c,b)； (2) 将A桩上第m个盘移到C桩上，即mv(a,c)； (3) 将B桩上的m-1个盘借助A桩移

7、到C桩上，即hn(m-1,b,a,c)。 在主程序中，带实参n, A,B,C调用hn(m,a,b,c)，这里n为具体移动盘的个数。同时设置变量k统计移动的次数。,4.2.2 移动过程实现,4.3 排队购票问题,4.3.1 常规排队 一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数 。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）,递归设计要点,令f(m,n)表示有m个人手持50元的钞票，n个人手持1

8、00元的钞票时共有的排除总数。 分以下3种情况来讨论。 (1) n=0 n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。 (2）mn 当mn时，即购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，这时排队总数为0，即f(m,n)=0。,(3）其它情况 1） 第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。 2） 第m+n个人手持50元的钞票，则在

9、他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。 由加法原理得到f(m,n)的递归关系： f(m,n)=f(m,n-1)+f(m-1,n) 初始条件： 当mn时，f(m,n)=0 当n=0时，f(m,n)=1,4.3.2 带条件限制的排队,为了满足“第5位为持50元”的规定，把图中左下角两条可位于第5位的“竖段”标注“”，列为禁止通过。这两段的上交叉点(4,1)与(3,2)就只能与其左边的(3,1)与(2,2)点发生关系，即 if(j=4 ,4.4 多转向旋转方阵,递归设计要点： 设计以顺转向内展开，设置二维数组a(h,v)存放方

10、阵中第h行第v列元素。 把n阶方阵从外到内分圈，外圈内是一个n-2阶顺转方阵，除起始数不同外，具有与原问题相同的特征属性。 因此，设置旋转方阵递归函数t(b,s,d)，其中b为每个方阵的起始位置；s是方阵的阶数；d是为a数组赋值的整数。 b赋初值0, 因方阵的起始位置为(0,0)。以后每一圈后进入下一内方阵，起始位置b需增1。 d从1开始递增1取值，分别赋值给数组的各元素，至n2 为止。 s从方阵的阶数n开始，以后每一圈后进入下一内方阵，s=s-2。 若s1时，在函数t(b,s,d)中还需调用t(b+1,s-2,d)。 至s=0时返回，作为递归的出口。,4.5 快速排序与选择,1.逐项比较排序

11、 最简单的排序是把存放在数组的n个数据逐个比较，必要时进行数据交换。 n项逐项比较排序进行升序排序的算法描述如下： for(i=1;irj) t=ri;ri=rj;rj=t; 逐项比较排序的时间复杂度为O(n2)。,（1）快速排序思路 快速排序又称为分区交换排序，其基本思想是分治，即分而治之：在待排序的n个数据r1,2,n中任取一个数（例如r1）作为基准，把其余n-1个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。 这样分成的两个区实际上是待排序数据的两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果。,4.5.1 分区交换

12、排序,（2） 分区交换描述,while(i!=j) while(rj=r0 / 把大于基准的一个数赋给r(j) ,（4）快速排序的时间复杂度分析,（3） 快速排序实现 (实际测试算法),(1) 选择问题 在一个无序序列r(1),r(2),r(n)中，寻找第k小元素的问题称为选择。这里第k小元素是序列按升序排列后的第k个元素。 特别地，当k=n/2时，即寻找位于n个元素中的中间元素，称为中值问题。,4.5.2 分区交换选择,（2） 选择问题的分区交换设计,参照上述分区交换的快速排序算法，在待选择的n个数据r1,2,n中任取一个数（例如r1）作为基准，把其余n-1个数据分为两个区，小于基准的数放在

13、左边，大于基准的数放在右边，基准定位在s，则 1) 若s=k，基准数即为所寻求的第k小元素。 2) 若sk，可知左边小于该基准数的个数s-1k，则在左边的子区继续分区。 3) 若sk，可知所寻求的第k小元素在右边子区，则在右边的子区继续分区。 依此2），3）继续，直到出现1）结束，输出结果。,(3) 快速选择的时间复杂度分析,4.6 实现排列组合,排列组合是组合数学的基础，从n个不同元素中任取m个，约定1mn，按任意一种次序排成一列，称为排列，其排列种数记为A(n,m)。 从n个不同元素中任取m个(约定1mn)成一组，称为一个组合，其组合种数记为C(n,m)。 计算A(n,m)与C(n,m)只

14、要简单进行乘运算即可，要具体展现出排列的每一列与组合的每一组，决非轻而易举。 本节应用递归设计来具体实现排列与组合。,1. 递归设计要点 递归函数p(k)的变量k从1开始取值。当km时，第k个数a(k)取i(1n)，并标志量u=0。 （1）若a(k)与其前面已取的数a(j)(jk)比较，出现a(k)=a(j)，即第k个数取i不成功，标志量u=1。 （2）若a(k)与所有前面已取的a(j)比较，没有一个相等，则第k个数取i成功，标志量保持u=0，然后判断： 1） 若k=m，即已取了m个数，输出这m个数即为一个排列，a(k)继续从i+1开始，在余下的数中取一个数。直到全部取完，则返回上一次调用p(

15、k)处，即回溯到p(k-1)，第k-1个数继续往下取值。 2） 若km，即还未取m个数，即在p(k)状态下调用p(k+1)继续探索下一个数，下一个数a(k+1)又从(1n)中取数。,4.6.1 基本排列实现,（3）若标志量u=1，第k个数取i不成功，则接着从i+1开始中取下一个数。若在1n中的每一个数都取了，仍是u=1，则返回上一次调用p(k)处，即回溯到p(k-1)，第k-1个数继续往下取值。 可见递归具有回溯的功能，即p(k)在取所有n个数之后，自动返回调p(k)的上一层，即回溯到p(k-1)，第k-1个数继续往下取值。这也是递归能把所有排列一个不剩全部展示的原因所在。 在主程序，只要调用

16、p(1)即可，所有排列在递归函数中输出。最后返回p(1)的a(1)取完所有数，返回排列个数s，输出排列的个数后结束。 （4）以上实现A(n,m)的递归深度为m，递归算法的时间复杂度为O(mn)。,4.6.3 组合实现,注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。因而，把以上排序程序中的约束条件作简单修改: “aj=ai” 修改为：“ aj=ai” “ak=aj” 修改为 ：“ak=aj” 即可实现从n个不同元素中取m个（约定1mn）的组合C(n,m)。 这样修改实现组合的取值次数、判别次数均与实现排列相同，做了大量无效操作，效率太低。,1. 实现组合递归设计,约定组合中的组成元素递增排序，实现a 数组取值的i循环设置为： for(i=ak-1+1;i=n+k-m;i+) ak=i; 循环起点为：ak-1+1，即ak取值要比ak