《函数的递归调用与分治策略20020.docx》由会员分享，可在线阅读，更多相关《函数的递归调用与分治策略20020.docx（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、函数的递归调用与分治策略递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。递归方法的构造构造递归方方法的关关键在于于建立递递归关系系。这里里的递归归关系可可以是递递归描述述的，也也可以是是递推描描述的。下下面由一一个求nn的阶乘乘的程序序为例，总总结出构构造递归归方法的的一般步步骤。例1从从键盘输输入正整整数N（00=NN=1时，NN!=NN*(NN-1)
2、!（NN=1时时，0!=1），这这就是一一种递归归关系。对对于特定定的K!，它只只与K与与(K-1)!有关。步骤2确定递递归边界界 在步步骤1的的递归关关系中，对对大于kk的Unn的求解解将最终终归结为为对Ukk的求解解。这里里的Ukk称为递递归边界界（或递递归出口口）。在在本例中中，递归归边界为为k=00，即00!=11。对于于任意给给定的NN!，程程序将最最终求解解到0!。确定递归边边界十分分重要，如如果没有有确定递递归边界界，将导导致程序序无限递递归而引引起死循循环。例例如以下下程序：#inclludee int ff(innt xx) retturnn(f(x-11);main() c
3、ouut=11时n!= 1 当NN=0时时再将这种关关系翻译译为代码码，即一一个函数数：long f(iint n) if (n=0) reeturrn(11); elsee reeturrn(nn*f(n-11);步骤4完善程程序 主主要的递递归函数数已经完完成，将将程序依依题意补补充完整整即可。/ex11.cppp#inclludee long f(iint n) if (n=0) reeturrn(11); elsee reeturrn(nn*f(n-11);main() int n; cinn; coutteendll=33）。从从键盘输输入N，输输出A(N)。分析递递归关系系十分明明
4、显，由由A(NN)的表表达式给给出。需需要注意意的是本本例中对对于N=3，AA(N)的值与与A(NN-1)和A(N-22)都有有关。代码/ex22.cppp#inclludee long fibbonaaccii(innt xx) if ( (xx=11) | (x=2) ) reeturrn(11); elsee reeturrn(ffiboonaccci(x-11)+ffiboonaccci(x-22);main() int n; cinn; coutteendllffiboonaccci(n); 例3Hannoi塔塔问题。 问题描描述在在霍比特特人的圣圣庙里，有有一块黄黄铜板，上上面插着
5、着3根宝宝石针（分分别为AA号，BB号和CC号）。在在A号针针上从下下到上套套着从大大到小的的n个圆圆形金片片。现要要将A针针上的金金片全部部移到CC针上，且且仍按照照原来的的顺序叠叠置。移移动的规规则如下下：这些些金片只只能在33根针间间移动，一一次只能能一片，且且任何时时候都不不允许将将较大的的金片压压在较小小的上面面。从键键盘输入入n，要要求给出出移动的的次数和和方案。分析由由金片的的个数建建立递归归关系。当当n=11时，只只要将唯唯一的金金片从AA移到CC即可。当当n11时，只只要把较较小的(n-11)片按按移动规规则从AA移到BB，再将将剩下的的最大的的从A移移到C（即即中间“借助”
6、B把金金片从AA移到CC），再再将B上上的(nn-1)个金片片按照规规则从BB移到CC（中间间“借助”A）。本题的特点点在于不不容易用用数学语语言写出出具体的的递归函函数，但但递归关关系明显显，仍可可用递归归方法求求解。代码/ex33.cppp#inclludee hanoii(innt nn,chhar t1,chaar tt2,ccharr t33) if (n=1) coout11 t11 t33eendll; elsee hannoi(n-11,t11,t33,t22); couutn tt1 tt3enddl; hannoi(n-11,t22,t11,t33); main() int
7、 n; couttn; couttAnsswerr:enndl; hanooi(nn,AA,B,C);函数递归调调用的应应用与分分治策略略许多算法都都采用了了分治策策略求解解，而可可以说分分治与递递归是一一对孪生生兄弟，它它们经常常同时被被应用于于算法的的设计中中。下面面讨论著著名的CCataalann数问题题，人们们在对它它的研究究中充分分应用了了分治策策略。例4CCataalann数问题题。问题描述述一个个凸多边边形，通通过不相相交于nn边形内内部的对对角线，剖剖分为若若干个三三角形。求求不同的的剖分方方案总数数H(nn)。HH(n)即为CCataalann数。例例如，nn=5时时H(55
8、)=55。分析CCataalann数问题题有着明明显的递递归子问问题特征征。在计计算Caatallan数数时虽然然可以推推导出只只关于nn的一般般公式，但但在推导导过程中中却要用用到递归归公式。下下面讨论论三种不不同的解解法，其其中第三三种解法法没有使使用递归归，它是是由前两两种解法法推导而而出的。解法1对于多多边形VV1V22Vn，对对角线VV1Vii（i=3,44,n-1）将将其分为为两部分分，一部部分是ii边形，另另一部分分是n-i+11边形。因因此，以以对角线线V1VVi为一一个剖分分方案的的剖分方方案数为为H(ii)*HH(n-i+11)。还还有一种种的特殊殊情形，是是对角线线V2V
9、Vn将其其分为一一个三角角形V11V2VVn和一一个n-2+11边形。为为了让它它同样符符合粗体体字给出出的公式式，规定定H(22)=11。于是是得到公公式：H(n)=H(ii)*HH(n-i+11) （ii=2,3,n-1） -公式式(1)H(2)=1有了这个递递归关系系式，就就可以用用递推法法或递归归法解出出H(nn)。解法2从V11向除了了V2和和Vn外外的n-3个顶顶点可作作n-33条对角角线。每每一条对对角线VV1Vii把多边边形剖分分成两部部分，剖剖分方案案数为HH(i)*H(n-ii+2)，由于于Vi可可以是VV3V44Vn-1中的的任一点点，且VV1可换换成V22，V33，Vn
10、n中任一一点也有有同样的的结果。考考虑到同同一条对对角线在在2个顶顶点被重重复计算算了一次次，于是是对每个个由顶点点和对角角线确定定的剖分分方案都都乘以11/2，故故有H(n)=n(1/2)HH(i)*H(n-ii+2) （ii=3,4,n-1）把(1/22)提到到外面，H(n)=n/(2*(n-33)H(ii)*HH(n-i+22) （ii=3,4,n-1） -公式式(2)规定H(22)=HH(3)=1，这这是合理理的。由公式(22)和HH(2)=1，同同样可以以用递推推法或递递归法解解出H(n)。解法3 把公公式(11)中的的自变量量改为nn+1，再再将刚刚刚得出的的公式(2)代代入公式式
11、(1)，得到到H(n+11)=H(ii)*HH(n-i+22) （ii=2,3,n） 由由公式(1)H(n+11)=22*H(n)+H(ii)*HH(n-i+22) （ii=3,4,n-1） 由由H(22)=11H(n+11)=(4n-6)/n*HH(n) 由公式式(2)H(n)=(4nn-100)/(n-11)*HH(n-1) -公式式(3)这是一个较较之前两两种解法法更为简简单的递递归公式式，还可可以继续续简化为为H(n)=1/(n-11)*CC(n-2,22n-44) -公式(4)这就不需要要再使用用递归算算法了。然然而在程程序设计计上，公公式(44)反而而显得更更加复杂杂，因为为要计算
12、算阶乘。因因此最后后给出由由公式(3)作作为理论论依据范范例程序序代码。代代码相当当简单，这这都归功功于刚才才的推导导。如果果用前两两种解法法中的递递归关系系，程序序会变得得复杂且且容易写写错。因因此，有有时对具具体问题题将递归归关系公公式进行行必要的的化简也也是至关关重要的的。代码/ex44.cppp#inclludee #defiine MAXXN 1100long f(iint x) if (x=3) rretuurn(1); elsse rretuurn(4*x-110)*f(xx-1)/(xx-1);main() intt n; couutnn; if ( (n=3) ) ccout
13、tThee annsweer iis:ff(n);本例编程时时还有一一个细节节问题需需要注意意。注意意函数ff中的斜斜体部分分，按照照公式(4)计计算时一一定要先先进行乘乘法再进进行除法法运算，因因为(44*x-10)并不总总能整除除(x-1)，如如果先进进行除法法则除出出的小数数部分将将自动被被舍去，从从而导致致得到不不正确的的解。数学上许多多有重要要意义的的计数问问题都可可以归结结为对CCataalann数的研研究。可可以看到到，本例例中的递递归关系系经简化化还是相相当简单单的。下下面讨论论一个递递归关系系略为复复杂的例例子。例5快快速排序序问题。快速排序是是程序设设计中经经常涉及及的一种
14、种排序算算法。它它的最好好时间复复杂度为为O(nnlogg2n)，最差差为O(n2)，是一一种不稳稳定的排排序方法法（大小小相同的的数在排排序后可可能交换换位置）。算法描述述快速速排序的的一种基基本思想想是：要要将n个个数按由由小到大大排列，在在待排序序的n个个数中选选取任一一个数（在在本例中中取第一一个），称称为基准准数，在在每一次次快速排排序过程程中设置置两个指指示器ii和j，对对基准数数左边和和右边的的数同时时从最左左（i）和和最右（jj）开始始进行扫扫描（ii逐1递递增，jj逐1递递减），直直到找到到从左边边开始的的某个ii大于或或等于基基准数，从从右边开开始的某某个j小小于或等等于基
15、准准数。一一旦发现现这样的的i和jj（暂且且称之为为一个“逆序对对”），则则把第ii个数和和第j个个数交换换位置，这这样它们们就不再再是逆序序对了，紧紧接着再再将i递递增1，jj递减11。如此此反复，在在交换过过有限个个逆序对对后，ii和j将将越来越越靠近，最最后“相遇”，即ii和j指指向同一一个数，暂暂且称之之为相遇遇数（极极端情况况下，如如果一开开始就不不存在逆逆序对，ii和j将将直接“相遇”）。相相遇后就就保证数数列中没没有逆序序对了（除除了在上上述的极极端情况况下基准准数和自自身也算算构成一一个逆序序对，注注意粗体体字给出出的逆序序对的定定义）。继继续扫描描，非极极端情况况下，由由于数
16、列列中已经经没有逆逆序对，ii递增11（如果果相遇数数小于基基准数）或或者j递递减1（如如果相遇遇数大于于基准数数）后即即算完成成了一趟趟快速排排序，这这时第11到第jj个数中中的每个个都保证证小于或或等于基基准数，第第i到第第n个数数中的每每个保证证大于或或等于基基准数。此此时，递递归调用用函数，对对第1到到第j个个数和第第i到第第n个数数分别再再进行一一趟快速速排序。如如果在极极端情况况下，程程序认为为基准数数和自身身构成逆逆序对，则则将基准准数与自自身交换换（这其其实没有有作用）之之后i递递增1，jj递减11（注意意斜体字字给出的的对逆序序对的处处理方法法），同同样对第第1到第第j个数数
17、和第ii到第nn个数分分别再进进行一趟趟快速排排序。最后的问题题就是确确定递归归边界。由由于被排排序的数数列将不不断被划划分为两两个至少少含一个个数的子子列（因因为在每每趟排序序最后进进行递归归调用函函数时iijj），最最后子列列的长度度将变为为1。这这就是递递归的边边界。在在程序实实现是，本本着“能排则则排”的原则则，只要要第一个个数小于于j（或或者第ii个数小小于最后后一个数数），即即进行递递归。主程序（递递归函数数体）void QuiickSSortt(ReecTyype R ,iint s,iint t) intt i=s,jj=t,k; ReccTyppe ttempp; if (s
18、i&Rj.keyyteemp.keyy) jj-; iff(ij) Ri=Rjj; i+; whiile( ij&Rii.kkeytemmp.kkey) ii+; iff(ij) Rj=Rii; j-; Ri=temmp; QuuickkSorrt(RR,s,i-11); QuuickkSorrt(RR,i+1,tt); 例6“九宫阵阵”智力游游戏。问题描述述一个个99方阵阵，由99个“九宫格格”组成，每每个九宫宫格又由由33共99个小格格子组成成。请在在每个空空白小格格子里面面填上119的的数字，使使每个数数字在每每个九宫宫格内以以及在整整个九宫宫阵中的的每行、每每列上均均出现一一次。（1）
19、编程程将下面面图中的的九宫阵阵补充完完整。（2）讨论论是否可可能给出出“九宫阵阵”的全部部解？分析本本题可利利用回溯溯法解决决，其基基本思想想为深度度优先搜搜索（DDFS），这这也是一一种以分分治策略略为基础础的算法法。回溯溯法与纯纯粹的DDFS不不同的是是，它在在搜索过过程中不不断杀死死不合题题意的结结点。这这一点保保证了解解法的效效率。首先考虑如如何得出出全部解解的情况况。解空间树容容易构造造，只需需按顺序序（从第第一行第第一个数数字开始始到第一一行最后后一个，然然后第二二行，一直直到最后后一行最最后一个个数字）“尝试”填入数字即可。为了解决这这个问题题，我们们需要先先编写一一个函数数ch
20、eeck，其其原型为为intt chheckk(innt ii,innt jj,innt kk)，用用于求第第i行第第j列能能否填上上数字kk。如果果可以，返返回1，否否则返回回0。由由于我们们是按顺顺序填入入数字的的，看起起来一个个数字后后面的数数字并不不在判断断能否填填的范围围内。但但为了解解决题中中某个特特解问题题的方便便，还是是引入较较为严谨谨的判断断方法。函数cheeck代代码如下下：int cchecck(iint i,iint j,iint k) intt l,m,ppi,ppj; /11. CChecck tthe linne forr (ll=1;l=9;ll+) iif (
21、 (ll!=jj) & (aiill!=0) & (ail=k) ) reeturrn(00); /22. CChecck tthe collumnn forr (ll=1;l=9;ll+) iif ( (ll!=ii) & (alljj!=0) & (alj=k) ) reeturrn(00); /33. CChecck tthe 3x33 maatriix /33.1 Firrstlly we willl hhavee too chheckk thhe ppareent_i(ppi) andd paarennt_jj(pjj) if (i=3) pii=1; elsse iif (i=6)
22、 pi=4; elsse ppi=77; if (j=3) pjj=1; elsse iif (j=6) pj=4; elsse ppj=77; /33.2 Noww wee caan cchecck iit forr (ll=0;l=2;ll+) foor (m=00;m=2;m+) if ( (pii+l)!=ii) & (pjj+m)!=jj) ) iif ( ( appi+llppj+mm!=0 ) & ( appi+llppj+mm=k ) ) retturnn(0); retturnn(1);结合注释很很容易就就能接受受函数的的思想，不不予过多多说明。下面考虑程程序最重重要的部部分
23、，即即递归函函数。思思路是这这样的：假设某某一格能能填入某某数，把把这个格格子看成成解空间间树的一一个结点点，由它它可以扩扩展出99个儿子子，即下下一格填填什么数数（由11到9逐逐个尝试试）。对对下一格格，同样样这样考考虑。不不断用函函数chheckk函数考考察某一一个能否否填入某某数，一一旦函数数cheeck返返回0，则则杀死这这个结点点。如果能一直直填到最最后一个个数，结结点仍未未被杀死死，则这这是一个个解。这种思想可可用伪代代码表示示如下：proceedurre bbackktraack(i,jj,k:inttegeer); if cheeck(i,jj,k)=trrue theen b
24、eggin ai,jj=kk; Geenerratee_neext_i_aand_j; iff i10 theen beeginn forr l:=1 to 9 ddo bbackktraack(i,jj,l);endelse Do_Outtputt;ai,jj:=0; endd;注意斜体的的“aii,j:=00”必不可可少！当当对某个个结点(x,yy)扩展展的过程程中，可可能在扩扩展到(x+mm,y+n)时时它的子子树被完完全杀死死（每个个结点都都被杀死死，亦即即按照(x,yy)及之之前的填填数方案案填数，无无解）。这这时需要要保证(x,yy)以后后所填的的数被重重新置零零，这个个语句的的作
25、用即即在每个个结点被被杀死时时都将其其置零。将伪代码翻翻译为CC+代代码：backttracck(iint i,iint j,iint k) intt l; iff (cchecck(ii,j,k)=1) aaij=k; /Filll iin tthe okaay ssoluutioon /Geenerratee neext i,jj iif (j99) jj+; ellse ii+; j=1; /Ennd oof GGeneeratte nnextt i,j iif (i110) forr (ll=1;l=9;ll+) bbackktraack(i,jj,l); eelsee ouutpuu
26、t(); aaij=0; /*Wheen ffaills aand goees uuppeerwaardss, tthe vallue musst bbe ccleaaredd*/ 函数outtputt()用用双重循循环完成成输出。在在主函数数maiin()对baackttracck(11,1,i)进进行一个个循环，ii从1取取到9，即即可完成成整个程程序。运运行时发发现九宫宫格的解解相当多多，即使使保存到到文件中中也不现现实。这这就回答答了第22个问题题。对于第1个个问题，将将这个程程序略加加改动，即即赋予全全局数组组a以初初值，并并在过程程baccktrrackk中产生生下一个个i和jj时
27、跳过过有初值值的部分分，即可可将程序序转化为为求填有有部分空空缺的九九宫格程程序。最后给出填填充有部部分空缺缺的九宫宫格的完完整源代代码。#inclludee usingg naamesspacce sstd;int aa111111=0;int cchecck(iint i,iint j,iint k) intt l,m,ppi,ppj; /11. CChecck tthe linne forr (ll=1;l=9;ll+) if ( (ll!=jj) & (aiill!=0) & (ail=k) ) reeturrn(00); /22. CChecck tthe collumnn forr
28、 (ll=1;l=9;ll+) if ( (ll!=ii) & (alljj!=0) & (alj=k) ) reeturrn(00); /33. CChecck tthe 3x33 maatriix /33.1 Firrstlly wwe wwilll haave to cheeck thee paarennt_ii(pii) aand parrentt_j(pj) if (i=3) pii=1; elsse iif (i=6) pi=4; elsse ppi=77; if (j=3) pjj=1; elsse iif (j=6) pj=4; elsse ppj=77; /33.2 Noww
29、 wee caan cchecck iit forr (ll=0;l=2;ll+) foor (m=00;m=2;m+) if ( (pii+l)!=ii) & (pjj+m)!=jj) ) iif ( ( appi+llppj+mm!=0 ) & ( appi+llppj+mm=k ) ) reeturrn(00); retturnn(1); voidd ouutpuut() intt i,j; couutOnne ssoluutioon iis:eendll; forr (ii=1;i=9;ii+) for (j=1;jj=99;j+) cooutaij ; coutteendll; vo
30、id baccktrrackk(innt ii,innt jj,innt kk) intt l; if (chheckk(i,j,kk)=1) aij=k; /Filll iin tthe okaay ssoluutioon /Geenerratee neext i,jj do if (j9) j+; elsse i+; j=11; whiile (aij!=0); /Ennd oof GGeneeratte nnextt i,j if (i110) forr (ll=1;l=9;ll+) baccktrrackk(i,j,ll); elsee ouutpuut(); aij=0; /*Whe
31、en ffaills aand goees uuppeerwaardss, tthe vallue musst bbe ccleaaredd*/ void iniit() a1122=99; aa16=4; a17=5; a1199=77; a2233=33; aa25=7; a26=9; a2277=44; a3344=33; aa35=6; a38=8; a3399=99; a4411=33; aa44=1; a5533=44; aa58=2; a59=3; a6622=11; aa63=2; a66=3; a7711=88; aa78=5; a8822=66; aa84=2; a85=9; a9922=22; aa93=1; a97=8; /mmemsset(a,00,siizeoof(aa);int mmainn() intt i; forr (ii=1;i=9;ii+) initt(); backktraack(1,11,i); sysstemm(PPAUSSE); retturnn 0; 递归方法法在算法法与数据据结构中中的应用用无所不不在，如如动态规规划（状状态方程程）、回回溯法（深深度优先先搜索）等等等，以以上两例例只是冰冰山一角角。只有有熟悉掌掌握函数数递归调调用的编编程方法法，深入入理解分分治策略略的重要要思想，才才能编写写出功能能强大、高高效简明明的程序序。