2011算法2递归与分治策略

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,递归与分治策略,1,2,Hanoi,塔问题,例,1,：,Hanoi,塔问题：有,A,、,B,、,C,三根柱子。,A,上有,n,个圆盘，自下而上由大到小地叠在一起。,A,B,C,现要将,A,上的全部圆盘移到,B,上，并要求,：,(1),每次只能移动一个圆盘；,(2),任何时刻都不允许将较大的圆盘压在较小的圆盘上；,(3),圆盘只能在,A,、,B,、,C,三个柱子间移动。,Hanoi,塔的解可以很自然地看成这样一个过程：,(1),先将,A,上面,n1,个盘移至,C,。,(2),再将,A,上剩下的,1,个盘移至,B,。,(3),最后将,C,上的,n1,个盘移至,B,。,于是可得到如下的程序：,void Hanoi(int n, int Fr, int To, int As),if (n 0) ,Hanoi(n1, Fro, Ass, To);,Move(Fro, To);,Hanoi(n1, Ass, To, Fro),2,3,递归的概念,简单地说，递归就是用自己来定义自己。递归算法是一个直接或间接地调用自己的算法。,一般地说，一个递归过程,P,可以表示为基语句,S(,不含,P),和,P,自身的组合,：,P,(S, P),这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为,P, if B then Q else,(S, P),其中,Q,也不包含,P,，,B,为递归终止条件。,3,4,递归元,递归算法的思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。,这种规模的变化就体现在递归算法的变元中的一类,(,一个或几个,),变元上，这类变元被称之为递归元。,递归元的变化是在递归定义中确定的，它的变化应能导致递归算法的终止。,在递归算法的设计中递归元是非常重要的。,4,5,常见的递归形式,多变元递归；,多步递归；,嵌套递归；,联立递归,除基本的递归形式外，其它常见的递归形式有四种，它们是：,5,6,多变元递归,多变元递归就是递归元多于一个的递归。,例,2,：整数划分问题：将一个正整数,n,表示为一系列正整数之和，,n = n,1,+ n,2,+n,k,其中,n,1,n,2,n,k,1, k1,。,正整数,n,的一个这种表示称为正整数,n,的一个划分。正整数,n,的不同的划分的个数成为正整数,n,的划分数，记作,(n),。,例如,(6) = 11,，即整数,6,的划分数为,11,种：,6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1,2+2+2, 2+2+1+1, 2+1+1+1+1,，,1+1+1+1+1+1,6,7,正整数的划分,有时候，问题本身具有比较明显的递归关系，因而容易用递归函数直接求解。,在本例中，如果设,p(n),为正整数,n,的划分数，则难以直接找到递归关系。,7,8,正整数的划分,因此考虑增加一个自变量：,在正整数的所有不同划分中，将最大加数,n,1,不大于,m,的划分个数记为,q(n, m),，可以建立如下的递归关系：,最简单情形,：,(1),q(n, 1)=1,，,q(1, m) =1 n, m1;,递归关系,：,(2),q(n, n) = 1 + q(n, n,1),，,n,1;,产生的新情况：,(3) q(n, m) = q(n, m,1) + q(n,m, m), n,m,1,(4) q(n, m) = q(n, n), n,m,。,1 n = 1,或,m = 1,q(n, m) = 1 + q(n, n1) n m,q(n, m1)+q(nm, m) n,m,1,数记为,q(n, m),，可以建立如下的二元递归函数：,int q(int n, int m),if (n 1) | (m 1) return 0;,if (n = 1) | (m = 1) return 1;,if(n 1,Fibonacci,函数是一个两步的递归函数。,9,10,嵌套递归,所谓嵌套递归是指递归调用中又含有递归调用，又称为多重递归。,例如,Ackermann,函数：,2 n=1, m=0,A(n, m) = 1 m= 0, n = 0,n+2 n = 2, m=0,A(A(n-1, m), m-1) n, m = 1,Ackermann,函数是一个双重的递归函数。,10,11,联立递归,联立递归是同时定义几个函数，它们彼此相互调用，从而形成递归，又称间接递归。,11,将要求解的较大规模的问题分割成,k,个更小规模的子问题。,分治法算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这,k,个子问题分别求解。如果子问题的规模仍然不够小，则再划分为,k,个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,12,算法总体思想,对这,k,个子问题分别求解。如果子问题的规模仍然不够小，则再划分为,k,个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,13,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),14,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),分治法的设计思想是，将一个难以直接解决的大问题，,分割成一些规模较小的相同问题，以便各个击破，,分而治之。,15,分治法的一般算法,分治法的一般的算法模式为：,Divide-and-Conquer(P),/|P|=n,0,表示,P,的规模不超过阈值,n,0,，可直接求解,if (|P|=n,0,) return Adhoc(P);,divide P into smaller subinstants P,1, ., P,k,;,for (i =1; i = k; i+),y,i,= Divide-and-Conquer(P,i,);,return Merge(y,1, , y,k,);, /,算法,Merge(y,1, , y,k,),表示将子问题的解合成,P,的解,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的,k,个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种,平衡,(balancing),子问题,的思想，它几乎总是比子问题规模不等的做法要好。,16,分治法的时间复杂性,分治法的时间复杂性为：,O(1) n = 1,T(n) ,kT(n/m) + f(n) n,1,其中设子问题规模为,n/m,，,Merge,的时间为,f(n),。,求解此递归方程可得：,T(n) n,log,m,k,log,m,n1,+, k,j,f(n/m,j,),j=0,17,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题，即该问题具有,最优子结构性质,利用该问题分解出的子问题的解可以合并为该问题的解；,该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑,贪心算法,或,动态规划,。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用,动态规划,较好。,18,分析：,如果,n=1,即只有一个元素，则只要比较这个元素和,x,就可以确定,x,是否在表中。因此这个问题满足分治法的第一个适用条件,分析：,比较,x,和,a,的中间元素,amid,，若,x=amid,，则,x,在,L,中的位置就是,mid,；如果,xai,，同理我们只要在,amid,的后面查找,x,即可。无论是在前面还是后面查找,x,，其方法都和在,a,中查找,x,一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：,很显然此问题分解出的子问题相互独立，即在,ai,的前面或后面查找,x,是独立的子问题，因此满足分治法的第四个适用条件。,二分搜索技术,给定已按升序排好序的,n,个元素,a0:n-1,，现要在这,n,个元素中找出一特定元素,x,。,分析：,该问题的规模缩小到一定的程度就可以容易地解决；,该问题可以分解为若干个规模较小的相同问题,;,分解出的子问题的解可以合并为原问题的解；,分解出的各个子问题是相互独立的。,19,二分搜索技术,给定已按升序排好序的,n,个元素,a0:n-1,，现要在这,n,个元素中找出一特定元素,x,。,据此容易设计出,二分搜索算法,：,template,int BinarySearch(Type a, const Type& x, int l, int r),while (r = l),int m = (l+r)/2;,if (x = am) return m;,if (x am) r = m-1; else l = m+1;,return -1;,算法复杂度分析：,每执行一次算法的,while,循环， 待搜索数组的大小减少一半。因此，在最坏情况下，,while,循环被执行了,O(logn),次。循环体内运算需要,O(1),时间，因此整个算法在最坏情况下的计算时间复杂性为,O(logn),。,20,练习,1,设,a0:n-1,是一个有,n,个元素的数组，,k(0=k=n-1),是一个非负整数。试设计一算法将子数组,a0:k,与,ak+1:n-1,换位。要求只用到,O(1),的辅助空间，且时间复杂度尽可能低。,21,21,练习2,设n个不同的整数排好序后存于T0:n-1中。若存在一个下标i，0=in，使得Ti=i, 设计一个有效算法找到这个下标。要求算法时间复杂度为O(logn),22,课后练习,23,