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

《算法设计与分析实用教程杨克昌 第4章 递归》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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）描述递归关系注意到，当n>1时，n!=n*(n−1)!，这就是一种递归关系。对于特定的k!，它只与k和(k−1)!有关。（2）确定递归边界递归边界为:n=1时，n!=1。对于任意给定的n，程序将最终求解到1!。4.举例说明（3）求n!的递归函数longf(intx){longg;if(x<=0)printf("x<=0,输入错误！");elseif(x=

4、=1)g=1;elseg=x*f(x−1);return(g);}（4）设计调用递归函数的主程序voidmain(){intn;longy;scanf("%d",&n);y=f(n);//调用函数f(n)printf("%d!=%ld",n,y);}（5）递归调用的实现主函数调用f(n)后即进入函数f(n)执行。设执行本程序时输入为n=5，即求5!。在主函数中的调用语句即为y=f(5)，执行f函数，由于n=5，不等于1，故应执行g=n*f(n−1)，即g=5*f(4)。该语句调用f(4),…进行4次递归调用后，f函数参数值变为1，故不再继续递归调用而开始逐

5、层返回主调函数。f(1)的函数返回值为1，f(2)的返回值为2*1=2，f(3)的返回值为3*2=6，f(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

6、)次完成。(1)首先将n个盘的上面的n-1个盘借助C桩从A桩移到B桩上，需g(n-1)次；　(2)然后将A桩上最大的第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桩的一次移动过程，即A-->C。实现hn(m,a,b,c)，当m=1时，即mv(a,c)。当m>1时，分以下三步：(1)将A桩上面的

7、m-1个盘借助C桩移到B桩上，即hn(m-1,a,c,b)；(2)将A桩上第m个盘移到C桩上，即mv(a,c)；(3)将B桩上的m-1个盘借助A桩移到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个人排队购票，使售票处不至出现找不开

8、钱的局面的不同排队种数。（约定：开始售