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

常用算法与程序设计,*,第 3 章,递归与分治,1,常用算法与程序设计,3.1,递归及其应用,3.2,分治法概述,3.3,分治法的基本应用,3.4,消除递归,主要内容,2,常用算法与程序设计,3.1,递归及其应用,3.1.1,递归与递归调用,一个函数在它的函数体内调用它自身称为递归,(recursion),调用。,使用递归要注意以下几点：,(1),递归就是在过程或函数里调用自身；,(2),在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口递归和分治是相统一的，递归算法中含有分治思想，分治算法中也常用递归算法。,3,常用算法与程序设计,例如有函数,r,如下：,int,r(,int,a),b=r(a-1);,return b;,这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。,4,常用算法与程序设计,3.1.2,递归应用,【,例,3.1】,用递归法计算,n!,。,分析,n!,的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。,步骤,1,描述递归关系 递归关系是这样的一种关系。设,U1,U2,U3,Un,是一个序列，如果从某一项,k,开始，,Un,和它之前的若干项之间存在一种只与,n,有关的关系，这便称为递归关系。,注意到，当,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,常用算法与程序设计,确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：,#include,int,f(int,x),return(f(x-1);,main(),printf(f(5);,它没有规定递归边界，运行时将无限循环，会导致错误。,步骤,3,写出递归函数并译为代码 将步骤,1,和步骤,2,中的递归关系与边界统一起来用数学语言来表示，即,n*(n-1)!,当,n=1,时,n!=1,当,n=0,时,再将这种关系翻译为代码，即一个函数：,long,ff(int,n),long f;,if(n,0),printf(n,0,input error);,else,if(n,=0|n=1)f=1;,else f=ff(n-1)*n;,return(f,);,6,常用算法与程序设计,步骤,4,完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。,#include,long,ff(int,n),long f;,if(n,0),printf(n,0,input error);,else,if(n,=0|n=1)f=1;,else f=ff(n-1)*n;,return(f,);,void main(),int,n;,long y;,printf(n,input a integer number:n);,scanf(%d,&n,);,y=,ff(n,);,printf(%d,!=%,ld,n,y,);,7,常用算法与程序设计,3.2,分治法概述,3.2.1,分治法基本思想,在算法设计中，首先对求解问题进行系统的分析，之后将其分解成若干性质相同的子问题，所得结果称为求解子集，再对这些求解子集分别处理。如果某些子集还需分而治之，再递归的使用上述方法，直到求解子集不需要再细分为止。最后归并子集的解即得原问题的解。,8,常用算法与程序设计,9,常用算法与程序设计,因而对分治法算法设计过程可以如下描述：,设原问题输入为,an,，简记为,(1,，,n),；,子问题为,apaq,，,1pqn,，简记为,(p,，,q),。,已知：,SOLUTION;,int,divide(,int,int,);,int,small(,int,int,);,SOLUTION conquer(,int,int,);,SOLUTION combine(SOLUTION,SOLUTION);,10,常用算法与程序设计,分治法的抽象控制算法为：,SOLUTION,DandC(p,q,)/*divide and conquer*/,if(small(p,q,),return,conquer(p,q,);,else,m=,divide(p,q,);,return combine(,DandC(p,m,),DandC(m+1,q);,11,常用算法与程序设计,3.2.2,分治算法设计方法和特点,分治算法设计的两个基本特征：,(1),分治法求解子集是规模相同、求解过程相同的实际问题的分解。,(2),求解过程反复使用相同的求解子集来实现的，这种过程可以使用递归函数来实现算法，也可以使用循环。用分治法设计出来的程序一般是一个递归算法，因而例,3.4,中是用递归来来实现的。,12,常用算法与程序设计,【,例,3.4】,在含有,n,个不同元素的集合,an,中同时找出它的最大和最小元素。不妨设。,对求,n,个数的最大和最小，可以设计出许多种算法，这里使用分治法设计求解。,1.,直接搜索,StraitSearch(n,&max,&min),*max=*min=a0;,for(i,=1;i*max)*max=,ai,;,if(ai,*max)*max=,ai,;,else,if(ai,*min)*min=,ai,;,则有：,最好情况比较次数：,n-1,最坏情况比较次数：,2(n-1),平均情况比较次数：,3/2(n-1),13,常用算法与程序设计,2.,分治法,集合只有一个元素时：,*,max=*min=,ai,；,集合只有两个元素时：,if(ai,aj,)*max=,aj,;*min=,ai,;,else *max=,ai,;*min=,aj,;,集合中有更多元素时：,将原集合分解成两个子集,分别求两个子集的最大和最小元素,再合并结果。,算法如下：,typedef,struct,ElemType,max;,ElemType,min;,SOLUTION;,SOLUTION,MaxMin(i,j),SOLUTION s,s1,s2;,if(i,=j),s.max,=,s.min,=,ai,;return s;,if(i,=j-1),if(ai,=s2.max)?(,s.max,=s1.max):(,s.max,=s2.max);,(s1.min=s2.min)?(,s.min,=s1.min):(,s.min,=s2.min);,return s;,输入一组数,a,=22,10,60,78,45,51,8,36,，调用,MaxMin,函数，划分区间，区间划分将一直进行到只含有,1,个或,2,个元素时为止，然后求子解，并返回。,15,常用算法与程序设计,3.3,分治法的基本应用,3.3.1,数据查找与排序,【,例,3.5】,二分检索：已知,n,个按非降次序排列的元素,an,，查找元素,x,是否在表中出现，若找到，返回其下标值，否则返回一负数。,二分检索是数据查找中典型使用分治法的实例,16,常用算法与程序设计,原问题,:,(n,a0,an-1,x),数据分组,:,a0ak-2 ak-1 akan-1,三个子问题,:,(k-1,a0,ak-2,x)(1,ak-1,x)(,n-k,ak,an-1,x),17,常用算法与程序设计,递归算法,int,BinSearch1(p,q,x),int,k=(p+q)/2;,if(q,p)return 1;/*,参数错误*,/,if(x,=,ak,)return k;,if(x,ak,)return BinSearch1(k+1,q,x);,18,常用算法与程序设计,二元比较树,左子树上所有元素不比父节点元素值大,以有序表的中间元素为根节点的二分树,右子树上所有元素不比父节点元素值小,19,常用算法与程序设计,内节点,:,成功检索,外节点,:,不成功检索,二分检索树的深度,二元比较树的深度,20,常用算法与程序设计,3.3.2,计数逆序排名问题,一个核心问题是对两个排名进行比较的问题。你对一组,n,个电影排名，然后一个协同过滤系统向他的数据库咨询来找有着“类似”排名的其他人。但是从数量上说什么嗜好的方式来度量两个人的排名由多相似呢？显然一个相等的排名是非常相似的，一个完全相反的排名是非常不同的；我们想要的是介于整个中间区域的东西。,21,常用算法与程序设计,先放下这个定义，考虑一个例子，其中的序列是,1,，,4,，,1,，,3,，,5.,在这个序列中有三个逆序：（,2,，,1,），（,4,，,1,），（,4,，,3,）。也存在一个几何方法把它形象化，如图,3.6,所示。我们把输入数的序列按照它们被提供的次序画出来，而下面的序列处于上升次序。然后我们在顶部表格中的每个数与下面表各种相同的数之间划一条线段。每对交叉线段于在两个表格中相反次序的一对数,即一个逆序对应。,22,常用算法与程序设计,注意逆序个数怎样作为一个度量使得他平滑的介于完全一致（当序列是上升的次序，那么没有逆序）与完全不一致（如果序列是下降的次序，那么每对数构成一个逆竖，并且因此存在个序列）之间。,23,常用算法与程序设计,3.3.3,投资问题,有一个高计算的投资公司咨询员，有下面类型的问题想要一次又一次的求解，这个问题的一个典型实例如下所述。他们正在做一项模拟，在这项模拟中他们从过去的某点开始对一支给定的股票连续看天，让我们把这些天的纪录为数；对每天，他们有当天这支股票每股的价格（为简单起见，假设这个价格在每一天之内是固定的）。假设在这个时间区间内，某天他们想买,1000,股并且在以后的某天卖出所有的这支股。他们想知道：为了挣到最多的钱，他们应该什么时候买并且应该什么时候卖？,24,常用算法与程序设计,举例，假设,那么你应该返回“,2,买，,3,卖”。,通过分治策略我们可以把在元素对上的蛮力搜索减少到时间。这里由于面对的是类似情况，让我们考虑可以怎样应用分治策略。,25,常用算法与程序设计,一种简单的方法将是分别考虑前天和后天，对这两个集合中的每一个问题递归的求解，然后指出怎样从这些用时间得到一个全局的解。这将给出常用的递推式，因此得到。,此外，为了使得事情更容易，将使用,n,是,2,的幂，这个通常的假定，这并不减少一般性：如果是比,n,大的下一个,2,的幂，我们可以对在,n,与之间的所有,i,，令，以这种方式，我们不用改变答案，至多使输入的规模加倍。,26,常用算法与程序设计,3.4,消除递归,3.4.1,消除递归,递归算法的特点,符合人的递推求解问题的自然思维习惯,算法的结构简单，代码精炼，可读性好,效率低,27,常用算法与程序设计,消除递归的一般步骤,例,1,：,写一个递归函数,reverse(char*s),，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。,28,常用算法与程序设计,递归算法,void reverse(char*s),if(*s!=0),reverse(s+1);,putchar,(*s);,return;,29,常用算法与程序设计,输出,s=”,abc,”,的递归过程,进入递归调用,top=0,递归调用返回,top=6,顺序,条件,栈中元素,top=,s=,顺序,条件,addr,s,1,*,s=a,stack1=s,(a),stack2=L,2,(putchar,),2,s+1,1,top=6,addr,=stack6,s=stack5,2,*,s=b,stack3=s,(b),stack4=L,2,(,putchar,),4,s+2,2,top=4,addr,=stack4,s=stack3,3,*,s