第2章递归与分治策略.ppt
《第2章递归与分治策略.ppt》由会员分享,可在线阅读,更多相关《第2章递归与分治策略.ppt(41页珍藏版)》请在三一文库上搜索。
1、第2章 递归与分治策略,郭艺辉 广东金融学院 计算机科学与技术系 办公室:1622 电话:13503000588,37215835 Email:校内邮箱 ,递归与分治策略,任何一个可以用计算机求解的问题所需的计算时间都与其规模有关,问题的规模越小,解题所需的计算时间往往也越少,从而也较容易处理。要想直接解决一个较大的问题,有时是相当困难的。 凡治众如治寡,分数是也。 -孙子兵法,递归与分治策略,分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治
2、手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。,2.1 递归的概念,分治法自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 2.1 递归的概念 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。,5,2.1 递归的概念,例1 阶乘函数 阶乘函数可递归地定义为:,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。,2.1 递归的概念,int factorial(int n) if(n=0) return
3、 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中元素的全
4、排列记为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;
5、coutendl; else 还有多个元素待排列,递归产生排列 for (int i=k;i=m;i+) Swap(listk,listi); Perm(list,k+1,m); Swap(listk,listi); ,Hanoi塔问题,传说在古代印度布拉玛神庙有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),並命令僧侣将所有的金盘从第一根石棒移至第二根石棒,在移动过程中可以借助于第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,也就是世界末日來临之时。到那时他们的虔诚信徒可
6、以升天,而其他人则要下地狱。,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
7、的圆盘从塔座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 (
8、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 subins
9、tances 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。 补充: 适用分治法求解问题的基本特征: 该问题的规模缩小到一定的程度就可以容易地解决; 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解; 分解出的各个子问题是相互独立的。 很显然此问
10、题分解出的子问题相互独立,即在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) 时间,因此整个算法在最坏情况下的计算时
11、间复杂性为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,
12、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,
13、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:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 分治 策略
链接地址:https://www.31doc.com/p-2549064.html