算法递归与分治

递归与分治

递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。递归例

最大公约数

intgcd(intx,inty){returnx?gcd(y%x,x):y;}边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。分治的总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解

}分治法的基本步骤人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。例一二分搜索给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此容易设计出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}应用给定没有排序的n个元素a[0:n-1]，和一个元素x。问a中是否有两个数a[i]+a[j]=x如何使用二分？枚举a[i]，就变为查询a中是否存在x-a[i]了例二归并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){

if(left<right){//至少有2个元素

inti=(left+right)/2;//取中点

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到数组b

copy(a,b,left,right);//复制回数组a}}归并排序初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]应用：求逆序对逆序对指的是在一个数组中满足i<j,a[i]>a[j]的数对(a[i],a[j])5123645,15,25,35,46,4都是逆序对归并如何求逆序对？应用：求逆序对总逆序对数=前一半数组的逆序对数+后一半数组的逆序对数+第一个数在前一半,后一个数在后一半的逆序对数前两部分可以递归解决，对于最后一项，显然即使打乱前一半的数组或者后一半数组顺序，也不影响最后一项结果。那么如果顺便做了归并排序对求最后一项有什么帮助？提示：用两个指针从左到右扫描两个数组例三快速排序template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将<x的元素交换到左边区域

//将>x的元素交换到右边区域

while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6{7,8}快速排序template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将<x的元素交换到左边区域

//将>x的元素交换到右边区域

while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6{7,8}例四快速幂快速计算x^nmodpintpow(intx,intn){if(n==0)return1;inttmp=pow(x,n/2);tmp=tmp*tmp%p;if(n%2==1)tmp=tmp*x%p;returntmp;}Fi=a1Fi-1+a2Fi-2+a3Fi-3…+akFi-k已知F1,F2,…,Fk,求任意的Fn例五求解线性递推方程Fibonacci数数学方法通项公式由于分子第二项小于1，可以只算第一项，舍入到最近的整数求幂可以用对数或倍增法问题：精度误差！代码:直接递归可以直接写出递归代码intfib(intn){if(n<2)returnn;elsereturnfib(n-1)+fib(n-2);}分析注