计算机常用算法与程序设计教程 第3章 递归与分治

《计算机常用算法与程序设计教程 第3章 递归与分治》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章递归与分治1常用算法与程序设计3.1递归及其应用3.2分治法概述3.3分治法的基本应用3.4消除递归主要内容2常用算法与程序设计3.1递归及其应用3.1.1递归与递归调用一个函数在它的函数体内调用它自身称为递归(recursion)调用。使用递归要注意以下几点：(1)递归就是在过程或函数里调用自身；(2)在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口递归和分治是相统一的，递归算法中含有分治思想，分治算法中也常用递归算法。3常用算法与程序设计例如有函数r如下：intr(inta){b=r(a-1);return

2、b;}这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。4常用算法与程序设计3.1.2递归应用【例3.1】用递归法计算n!。[分析]n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。[步骤1]描述递归关系递归关系是这样的一种关系。设{U1,U2,U3,…,Un…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这

3、便称为递归关系。注意到，当n>=1时，n!=n*(n-1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k-1)!有关。[步骤2]确定递归边界在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。5常用算法与程序设计确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#includeintf(intx){return

4、(f(x-1));}main(){printf(f(5));}它没有规定递归边界，运行时将无限循环，会导致错误。[步骤3]写出递归函数并译为代码将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即n*(n-1)!当n>=1时n!=1当n=0时再将这种关系翻译为代码，即一个函数：longff(intn){longf;if(n<0)printf("n<0,inputerror");elseif(n==0

5、

6、n==1)f=1;elsef=ff(n-1)*n;return(f);}6常用算法与程序设计[步骤4]完善程序主要的递归

7、函数已经完成，将程序依题意补充完整即可。#includelongff(intn){longf;if(n<0)printf("n<0,inputerror");elseif(n==0

8、

9、n==1)f=1;elsef=ff(n-1)*n;return(f);}voidmain(){intn;longy;printf("inputaintegernumber:");scanf("%d",&n);y=ff(n);printf("%d!=%ld",n,y);}7常用算法与程序设计3.2分治法概述3.2.1分治法基本

10、思想在算法设计中，首先对求解问题进行系统的分析，之后将其分解成若干性质相同的子问题，所得结果称为求解子集，再对这些求解子集分别处理。如果某些子集还需分而治之，再递归的使用上述方法，直到求解子集不需要再细分为止。最后归并子集的解即得原问题的解。8常用算法与程序设计9常用算法与程序设计因而对分治法算法设计过程可以如下描述：设原问题输入为a[n]，简记为(1，n)；子问题为a[p]a[q]，1≤p≤q≤n，简记为(p，q)。已知：SOLUTION;intdivide(int,int);intsmall(int,int);SOLUTION

11、conquer(int,int);SOLUTIONcombine(SOLUTION,SOLUTION);10常用算法与程序设计分治法的抽象控制算法为：SOLUTIONDandC(p,q)/*divideandconquer*/{if(small(p,q))returnconquer(p,q);else{m=divide(p,q);returncombine(DandC(p,m),DandC(m+1,q));}}11常用算法与程序设计3.2.2分治算法设计方法和特点分治算法设计的两个基本特征：(1)分治法求解子集是规模相同、求解过程

12、相同的实际问题的分解。(2)求解过程反复使用相同的求解子集来实现的，这种过程可以使用递归函数来实现算法，也可以使用循环。用分治法设计出来的程序一般是一个递归算法，因而例3.4中是用递归来来实现的。12常用算法与程序设计【例3.4】在含有n个不同元素