第2章递归与分治策略.ppt

第2章 递归与分治策略,郭艺辉 广东金融学院 计算机科学与技术系 办公室：1622 电话：13503000588，37215835 Email：校内邮箱 gdufguo126.com,递归与分治策略,任何一个可以用计算机求解的问题所需的计算时间都与其规模有关，问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。要想直接解决一个较大的问题，有时是相当困难的。 凡治众如治寡，分数是也。 -孙子兵法,递归与分治策略,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。,2.1 递归的概念,分治法自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 2.1 递归的概念 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。,5,2.1 递归的概念,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,2.1 递归的概念,int factorial(int n) if(n=0) return 1； return n*factorial(n-1)； ,7,2.1 递归的概念,【例22】Fibonacci数列（斐波纳契数列） 无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,8,排列问题,例4 排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。,集合X中元素的全排列记为Perm(X)。 设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 (ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，Perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，Perm(R)由(r1) Perm(R1)，(r2) Perm(R2)，(rn) Perm(Rn)构成。,排列问题,template void Perm(Type list，int k，int m) 产生listk：m的所有排列 if(k=m) 只剩下1个元素 for(int i=0；i=m；i+) coutlisti； coutendl； else 还有多个元素待排列，递归产生排列 for (int i=k；i=m；i+) Swap(listk，listi)； Perm(list，k+1，m)； Swap(listk，listi)； ,Hanoi塔问题,传说在古代印度布拉玛神庙有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），並命令僧侣将所有的金盘从第一根石棒移至第二根石棒，在移动过程中可以借助于第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，也就是世界末日來临之时。到那时他们的虔诚信徒可以升天，而其他人则要下地狱。,11,Hanoi塔问题,例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自上而下，由小到大地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,12,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。,当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。,Hanoi塔问题,例6 Hanoi塔问题,Hanoi塔问题,解Hanoi塔问题的递归算法如下：,public static void Hanoi(int n, int a, int b, int c) if (n 0) Hanoi(n-1, a, c, b); move(a,b); Hanoi(n-1, c, b, a); 时间复杂度分析 O(2n）,Hanoi塔问题,264=18446744073709551616 1844万亿 6744千亿 0737亿 0955万 1千6百1十6,分治法的基本思想,22 分治法的基本思想 将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解。,Divide-and-Conquer(P) if ( |P|=n0) Adhoc(P); /直接求解问题p divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i = k; i+) yi=Divide-and-Conquer(Pi); return Merge( yl ,., yk); /将p1,p2,pk的解y1,y2,yk 合并成p的解,阈值,问 题 的 规 模,16,2.3 二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。 补充： 适用分治法求解问题的基本特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。 很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。,17,据此容易设计出二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,2.3 二分搜索技术,2.7 合并(merge)排序,问题:将n个元素排成非递减顺序。 合并排序算法是用分治策略实现对n个元素进行排序的算法。 其基本思想是：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。,2.7 合并(merge)排序,template void MergeSort(Type all，int left，int right) if(1eftright)至少有2个元素 int i=(left+right)2；取中点 MergeSort(a，left，i)； MergeSort(a，i+1，right)； Merge(a，b，left，i，right)；合并到数组b Copy(a，b，left，right)； ,template void merge(T C , T d ,int l, int m , int r) /把cl:m,cm+1：r归并到dl：r int i=l, /第段的游标 j=m+1, /第二段的游标 k=l ; /结果的游标 /只要段中存在i和j,则不断进行归并 while (im) for (int q=j; q=r;q+) dk+=cq； else for(int q=i ;q=m；q+) dk+=cq；,2.7 合并(merge)排序,8,7,6,5 8,7 6,5 8 7 6 5 7 8 5 6 5 6 7 8,计算过程：,O(1) n1,T(n)=,2.7 合并(merge)排序,初始序列a 8 4 5 6 2 1 7 3 4 8 5 6 1 2 3 7 4 5 6 8 1 2 3 7 1 2 3 4 5 6 7 8,Merge：,O(1) n1,T(n)=,2.8 快速排序,举例： a0:7=5, 3, 1, 9, 8, 2, 4, 7 结果1, 2, 3, 4, 5, 7, 8, 9,2.8 快速排序,快速排序算法基本思想是，对于输入的子数组ap：r，按以下三个步骤进行排序: (1)分解(Divide)：以ap为基准元素将ap：r划分成3段ap：q-1，aq和aq+1：r，使ap：q-1中任何一个元素小于等于aq，而aq+1：r中任何一个元素大于等于aq 。下标q在划分过程中确定。 (2)递归求解(conquer)：通过递归调用快速排序算法分别对ap：q-1和aq+l：r进行排序。 (3)合并(Merge)：由于对ap：q-1和aq+1：r的排序是就地进行的，所以在ap：q-1和aq+l：r都已排好的序后，不需要执行任何计算，ap：r就已排好序。,24,快速排序算法,template void QuickSoft(Type a, int p, int r) if(pr) int q=Partition(a, p, r) QuickSort(a, p, q-1); /对左半段排序 QuickSoft(a, q+1, r); /对右半段排序 ,template int Partion(Type a ,int p , int r ) int i=p; j=r+1; type x=ap； /将=x的元素交换到左边区域 /将 x)； if (i=j ) break; swap(ai,aj); ap = aj； a j = x; return j ,Tmin(n)=,O(1) n1,复杂性分析:,Tmax(n)=,O(1) n1,得: Tmax (n)=O(n2),2.8 快速排序,25,随机选择支点的快速排序,template int randomizedPartition(Type a, int p, int r) int i=random( p, r) swap( ai, ap ) return Partition (a,p,r) template void randomizedQuickSort(Type a, int p, int r) if (pr) int q=randomizedPartition(a, p, r) randomizedQuickSort(a, p, q-1); /对左半段排序 randomizedQuickSoft(a, q+1, r); /对右半段排序 ,26,本节讨论与排序问题类似的元素选择问题。元素选择问题的一般提法是：给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素,即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为要找的元素。当k=1时，就是要找的最小元素；当k=n时，就是要找最大元素；当k=(n+1)2时，称为找中位数。下面讨论解一般选择问题的一个分治算法RandomizedSelect。该算法实际上是模仿快速排序算法设计出来的。其基本思想也是对输人数组进行递归划分,不同的是，它只对划分出的子数组之一进行递归处理。 举例： 在 a0:7=5, 3, 1, 9, 8, 2, 4, 7 中找第3小元素。,2.9 线性时间选择,27,2.9 线性时间选择,private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=randomizedpartition(p,r), j=i-p+1; if (k=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); 举例： 在 a0:7=5, 3, 1, 9, 8, 2, 4, 7 中找第3小元素。,在最坏情况下，算法randomizedSelect需要O(n2)计算时间 但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。,28,A0:24=11,3,13,37,43,19,6,32,25,52,31,8,17,60,33,35,4,57,9,51 将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。 递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。,设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。故当n75时，3(n-5)/10n/4。所以按此基准划分所得的2个子数组的长度都至少缩短1/4。,2.9 线性时间选择,29,template Type Select(Type a, int p, int r, int k ) if (r-p75) 用某个简单排序算法对数组ap:r排序； return ap+k-1 ； for(int i=0;i=(r-p-4)/5; i+) 将ap+5*i至ap+5*i+4的第3小元素 与ap+i交换位置； /找中位数的中位数, r-p-4即上面所说的n-5 Type x=Select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r,x)， j=i-p+1; if (k=j) return Select(a,p,i,k) else return Select(a,i+1,r,k-j) ,30,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。,2.9 线性时间选择,2.9 线性时间选择,复杂度分析 T(n)=O(n),上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。,32,2.10 平面最接近点对,33,如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。 由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。 因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。,2.10 平面最接近点对,2.10 平面最接近点对,算法描述： bool CPair1(S, d) n=|S|; if (nm CPair1(S1, d1); CPair1(S2, d2); p=max(S1); q=min(S2); d=min(d1, d2, q-p); return ture; 复杂性分析： T(n)=O(nlogn) 该算法可推广到二维的情形中去。,35,下面来考虑二维的情形。,选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。 递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。,2.10 平面最接近点对,36,考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中 由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。 因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者,能否在线性时间内找到p3,q3？,证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则 distance(u,v)d。这与d的意义相矛盾。,2.10 平面最接近点对,37,为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。 因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。,2.10 平面最接近点对,38,public static double cpair2(S) n=|S|; if (n m 2. d1=cpair2(S1); d2=cpair2(S2); 3. dm=min(d1,d2);,4. 设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合； P2是S2中距分割线l的距离在dm之内所有点组成的集合； 将P1和P2中点依其y坐标值排序； 并设X和Y是相应的已排好序的点列； 5. 通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并； 当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动； 设dl是按这种扫描方式找到的点对间的最小距离； 6. d=min(dm,dl); return d; ,2.10 平面最接近点对,复杂度分析 T(n)=O(nlogn),2.10 平面最接近点对,结束,