第3章 递归与分治（章节课程）

1、第 3 章 递归与分治1主要内容：3.1 递归及其应用 3.2 分治法概述 3.3 分治法的基本应用 3.4 消除递归 2递归方法通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。优点： 函数的定义和算法易于描述和理解、证明简单33.1 递归及其应用3.1.1 递归与递归调用 一个函数在它的函数体内调用它自身称为递归(recursion) 调用。 递归策略只需要少量的程序就可描述解题过程所需要的多次重复计算。（减少程序代码量） 用有限的语句来定义对象的无限集合。 需要边界条件、递归前进段和递归返回段。 43.1 递归及其应用递归函数： 使用函数自身给出定义的函数。 使用递归要注意以

2、下几点： (1) 递归就是在过程或函数里调用自身； (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。递归和分治是相统一的，递归算法中含有分治思想，分治算法中也常用递归算法。 5例如有函数r如下：int r (int a)b=r(a-1);return b;这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 63.1.2 递归应用【例3.1】 用递归法计算。 1 n=0 n*(n-1)! n=1步骤1 描述递归关

3、系 设U1,U2,U3,Un是一个序列，如果从某一项k 开始，Un和它之前的若干项之间存在一种只与n有 关的关系，这便称为递归关系。步骤2 确定递归边界 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。 在本例中，递归边界为k=0，即0!=1。对于任意给定的n!，程序将最终求解到0!。 n!=7确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include int f(int x) return(f(x-1);main() printf(f(5);它没有规定递归边界，运行时将无限循环，会导致错

4、误。8步骤3 写出递归函数并译为代码 将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即 n*(n-1)! 当n=1时 n!= 1 当n=0时再将这种关系翻译为代码，即一个函数：long ff(int n) long f; if(n0) printf(n0,input error);else if(n=0|n=1) f=1; else f=ff(n-1)*n; return(f); 9步骤4 完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。#include int f(int n)int m; if (n0) printf(the number is less than

5、 0:); else if(n=0 |n=1) m=1; else m=f(n-1)*n; return m; void main()int n; int y; printf(input the number:); scanf(%d,&n); y=f(n); printf(%d!=%dn,n,y); (递推和回归求解)10不用递归实现：#include int f(int n)int m=1;int i; if (n0) printf(the number is less than 0:); else for (i=1; i=n;i+) m=m*i; return m; void main()

6、int n,y; printf(input the number:); scanf(%d,&n); y=f(n); printf(%d!=%dn,n,y); 11#include void main()int n,i,p=1; printf(input the number:); scanf(%d,&n); if (n0) printf(the number is less than 0:); else for (i=1; i=n;i+) p=p*i; printf(%d!=%dn,n,p); 12程序的输出结果？int fan(int n)int k;if(n=0|n=1) return 3

7、;else k=n-fan(n-2);return k;main()printf(%dn,fan(9);13汉诺塔#include hanoi(int n,int A,int B,int C)if(n=1)printf(%C-%Cn,A,C);elsehanoi(n-1,A,C,B);printf(%C-%Cn,A,C);hanoi(n-1,B,A,C);void main()int h; printf(input the number:n); scanf(%d,&h); printf(the step of moving %d diskes:n,h); hanoi(h,a,b,c); 14思

8、考汉诺塔的时间复杂性是多少？如何计算？15运用递归算法实现:输入一个任意整数，然后将它反向输出。如:输入12345，输出应为54321. 输入5432， 输出应为2345163.2 分治法概述3.2.1 分治法基本思想（分而治之）将问题分解成若干子问题，然后求解子问题。 在算法设计中，首先对求解问题进行系统的分析，之后将其分解成若干性质相同的子问题，所得结果称为求解子集，再对这些求解子集分别处理。如果某些子集还需分而治之，再递归的使用上述方法，直到求解子集不需要再细分为止。最后归并子集的解即得原问题的解。17包含两个过程：问题的分解和子集解的合并18设计过程分为三个阶段:Divide： 整个问

9、题划分为多个子问题Conquer：求解各子问题(递归调用正设计的算法)Combine：合并子问题的解, 形成原始问题的解19原始问题求解子问题子问题子问题子问题求解子问题求解子问题子问题解子问题解子问题解合并子解问题分解DivideConquerMerge原始问题的解20另一种描述：Divide-and-conquer(P) if(|p|=n0) return(solve(P) else 将P划分为多个子问题P1，P2，Pk for(i=1;iaq，1pqn，简记为(p,q)。已知：SOLUTION;int divide (int, int); int small (int, int); SO

10、LUTION conquer (int, int); (问题的解)SOLUTION combine (SOLUTION, SOLUTION); 22分治法的抽象控制算法为：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) ); 233.2.2 分治算法设计方法和特点分治算法设计的两个基本特征：(1) 分治法求解子集是规模相同、求解过程相同的

11、实际问题的分解。(2) 求解过程反复使用相同的求解子集来实现的，这种过程可以使用递归函数来实现算法，也可以使用循环。用分治法设计出来的程序一般是一个递归算法，因而例3.4中是用递归来来实现的。 24【例3.4】 在含有n个不同元素的集合an中同时找出它的最大和最小元素。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)25

12、2. 分治法集合只有一个元素时： *max=*min=ai；集合只有两个元素时： if(aiaj) *max=aj; *min=ai; else *max=ai; *min=aj;集合中有更多元素时： 将原集合分解成两个子集, 分别求两个子集的最大和最小元素, 再合并结果。26算法如下：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) ? (

13、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个元素时为止，然后求子解，并返回。 283.3 分治法的基本应用3.3.1 数据查找与排序【例3.5】 二分检索：已知n个按非降次序排列的元素an，查找元素x是否在表中出现，若找到，返回其下标值，否则返回一负数。 二分检索是数据查找中典型使用分治法的实例 29原问题: (n, a0,an-1,

14、 x)数据分组: a0ak-2 ak-1 akan-1三个子问题: (k-1, a0,ak-2, x) (1, ak-1, x) (n-k, ak,an-1, x)k-1个元素 n-k个元素30有一组数如下：（10，14，20，32，45，50，68，90，100，120）下面分析在其中二分检索关键字20的过程。 31下面分析二分检索关键字95的过程:32递归算法 int BinSearch1(low, high, x) int mid=(low+high)/2; if(highlow) return 1; /* 参数错误 */ if(x=amid) return mid; if(xamid)

15、 return BinSearch1(mid+1, high, x); 33A=-15,-6,0,7,9,23,54,82,101求解成功查找和不成功查找的平均比较次数34节点总数：19内节点: 成功检索 9外节点: 不成功检索 10二分检索树的深度（路径）二元比较树的深度(元素) 二元比较树以有序表的中间元素为根节点的二分树：左子树上所有元素不比父节点元素值大；右子树上所有元素不比父节点元素值小4353.3.2 计数逆序排名问题一个核心问题是对两个排名进行比较的问题。你对一组n个电影排名，然后一个协同过滤系统向他的数据库咨询来找有着“类似”排名的其他人。但是从数量上说什么嗜好的方式来度量两个

16、人的排名有多相似呢？显然一个相等的排名是非常相似的，一个完全相反的排名是非常不同的；我们想要的是介于整个中间区域的东西。36先放下这个定义，考虑一个例子，其中的序列是1，4，1，3，5.在这个序列中有三个逆序：（2，1），（4，1），（4，3）。也存在一个几何方法把它形象化，如图3.6所示。我们把输入数的序列按照它们被提供的次序画出来，而下面的序列处于上升次序。然后我们在顶部表格中的每个数与下面表各种相同的数之间划一条线段。每对交叉线段于在两个表格中相反次序的一对数即一个逆序对应。37注意逆序个数怎样作为一个度量使得他平滑的介于完全一致（当序列是上升的次序，那么没有逆序）与完全不一致（如果序列

17、是下降的次序，那么每对数构成一个逆竖，并且因此存在个序列）之间。383.3.3 投资问题有一个高计算的投资公司咨询员，有下面类型的问题想要一次又一次的求解，这个问题的一个典型实例如下所述。他们正在做一项模拟，在这项模拟中他们从过去的某点开始对一支给定的股票连续看天，让我们把这些天的纪录为数；对每天，他们有当天这支股票每股的价格（为简单起见，假设这个价格在每一天之内是固定的）。假设在这个时间区间内，某天他们想买1000股并且在以后的某天卖出所有的这支股。他们想知道：为了挣到最多的钱，他们应该什么时候买并且应该什么时候卖？ 39举例，假设那么你应该返回“2买，3卖”。通过分治策略我们可以把在元素对

18、上的蛮力搜索减少到时间。这里由于面对的是类似情况，让我们考虑可以怎样应用分治策略。 40一种简单的方法将是分别考虑前天和后天，对这两个集合中的每一个问题递归的求解，然后指出怎样从这些用时间得到一个全局的解。这将给出常用的递推式，因此得到。此外，为了使得事情更容易，将使用n是2的幂，这个通常的假定，这并不减少一般性：如果是比n大的下一个2的幂，我们可以对在n与之间的所有i，令，以这种方式，我们不用改变答案，至多使输入的规模加倍。413.4 消除递归3.4.1消除递归递归算法的特点： 符合人的递推求解问题的自然思维习惯 算法的结构简单，代码精炼，可读性好 效率低42消除递归的一般步骤例 写一个函数

19、 reverse (char arr)，按逆序输出一个字符串。43#include #include void reverse(char arr)int i,j,n;char tmp;n = strlen(arr)-1;for(i = 0; i = n; i+) if(arri != 0) for(j = 0; j = n-1-i; j+) tmp = arrj;arrj = arrj+1;arrj+1 = tmp; int main() char arr20; gets(arr);reverse(arr);printf(%sn,arr); return 0；44消除递归的一般步骤例3.8 写

20、一个递归函数 reverse (char *s)，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。递归算法:调用自身迭代算法:它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值45递归算法 void reverse (char * s) if( *s!=0 ) reverse(s+1); putchar (*s); return; 46输出s=”abc”的递归过程进入递归调用, top=0递归调用返回, top=6顺序条件栈中元素top=, s= 顺序条件addr, s 1*

21、s=astack1=s, (a)stack2=L2, (putchar)2, s+11top=6addr=stack6s=stack52*s=bstack3=s, (b)stack4=L2 , (putchar)4, s+22top=4addr=stack4s=stack33*s=cstack5=s, (c)stack6=L2 , (putchar)6, s+33top=2addr=stack2s=stack14*s=0调用结束，转返回处理4top=0完全返回47改写的迭代算法 void reverse (char * s) extern ElemType stack2*n+1, top=0;

22、 L1: if( *s!=0 ) stack+top=s; stack+top=L2; s=s+1; goto L1; L2: putchar(*s); / 接下来处理返回语句 if(top=0 ) return; / 栈为空 else addr=stacktop-; / 恢复地址 s=stacktop-; / 恢复参数 if(addr = L2) goto L2; 48优化后的迭代算法 void reverse(char * s) int top=0; while(*s!=0) top+; s+; while (top!=0) putchar(*s); s-; top-; 49 例3.9:

23、写一个求数组an中的最大元素的递归算法并将其改写成迭代算法。 分治的思路递归：ai ai+1 an-1int max (int i) int j=i, k; if(iaj) k=i; else k=j; else k=n-1; return k; 50(0) 开始，照搬（所有不涉及递归调用和返回语句的代码都照搬）(1) 定义和初始化堆栈(存储参数、局部变量、返回值和返址).int max(int i) extern stack4*n+1, top=0; int j=i, k;(2) 对第一条可执行语句定义标号L1,每次递归调用执行步骤 (3). (3) 将所有参数和局部变量进栈. (4) 建立

24、第i个返回地址的标号Li，进栈. (5) 计算本次递归调用实参的值，并赋给形参变量.(6) 无条件转移到L1进入递归. (7) 如果是带返回值的调用，从栈顶取回返回值并代替调用，其余代码按原方式处理，并将(4)建立的标号附于该语句；如果是不带返回值的调用，则将(4)建立的标号直接附于(6)对应的语句之后的那条语句. L1: if(in-1) stack+top=i; stack+top=j; stack+top= L2; i=i+1; goto L1； L2: j=stacktop-; if(ai=i; j-) if (ajak) k=j; return k; 53（P66）例3.8 合并排序

25、。将原始数组A中的元素分成两个子集合A1和A2。分别对这两个子集合单独排序，然后将已排序的两个子序列合并成一个含有n个元素的有序序列。分析对 24 13 26 1 2 27 38 15 采用合并排序的过程54#include int main()int a100,i;int low=0,high=9,k;for(i=0;i=high;i+)scanf(%d,&ai);printf(待排序的数为:n);for(k=low;k=high;k+)printf(%d ,ak);MergeSort(a,low,high);printf(n);printf(归并排序后的结果为:n);for(k=low;k

26、=high;k+)printf(%d ,ak);55/归并排序MergeSort(int *a,int low,int high)int mid;if(low high)mid=(low+high)/2;MergeSort(a,low,mid);MergeSort(a,mid+1,high);Merge(a,low,mid,high);56Merge(int *A,int low,int mid,int high)int h,i,j,k;int B100;h=low;i=low;j=mid+1;while(h=mid & j=high)/当两个集合都没有取尽时，将较小的元素先存放到B中if(A

27、hmid)for(k=j;k=high;k+)Bi=Ak;i+; else for(k=h;k=mid;k+)Bi=Ak;i+; for(k=low;k=high;k+)Ak=Bk;/ifelse段代码可以写成while(h=mid)Bi=Ah; h+; i+;while(jv) i=i+1;while(Ajv) j=j-1;if(ij)temp = Ai; Ai = Aj; Aj =temp;else return j; 61void QuickSort (int *A, int p,int q)/对区间p,q的数快排 int r;if(pq) r=Partition(A,p,q);/划分为

28、ap,r-1,每个元素小于等于ar;划分为ar+1,qQuickSort(A,p,r-1);/递归调用快排对ap,r-1排序QuickSort(A,r+1,q);62int main()int i,n=9;int A=310,285,179,652,351,423,861,254,450,520;printf(输入待排序个数：n);scanf(%d,&n);for (i=0;i=n;i+)scanf(%d,&Ai);/printf(输出排序前数据：n);for (i=0;i=n;i+)printf(%d ,Ai);printf(n);QuickSort(A,0,n);printf(输出排序后数

29、据：n);for (i=0;i=n;i+)/输出排序数据printf(%d ,Ai);printf(n);633.4.2 分治算法中的递归转化抽象控制递归算法： SOLUTION DandC (p, q) /* divide and conquer */ int m; SOLUTION s1, s2, s; if( small (p, q) ) s=conquer (p, q); else m=divide (p, q); s1=DandC (p, m); s2=DandC (m+1, q); s=combine (s1, s2); return s; 64抽象控制迭代算法：SOLUTION

30、DandC (p, q) extern ElemType stack5*n+1, top=0; int m; SOLUTION s1, s2;L1: if(small(p,q) s=conquer(p,q); else m=divide(p,q); stack+top=p; stack+top=q; stack+top=m; stack+top=L2; p=p; q=m; goto L1; L2: s1= stacktop-; stack+top=p; stack+top=q; stack+top=m; stack+top=L3; p=m+1; q=q; goto L1; L3: s2=sta

31、cktop-; s=combine(s1,s2); if(top=0) return s； else addr=stacktop-; m=stacktop-; q=stacktop-; p=stacktop-; stack+top=s; if(addr=L2) goto L2; else goto L3; 656 2 9 3 5 1 8 7max=a1;j=1;for(i=2;imax) max=ai; j=i;66思考：对13个元素：3 9 12 32 41 45 62 75 77 82 95 100采用二分查找，查找数字82需要比较多少次才能查找成功.67 A Bn/2位X=n/2位 C

32、Dn/2位Y=n/2位XY = (A2n/2 + B)(C2n/2 + D) = AC2n + (A+B)(C+D)-AC-BD)2n/2 + BD计算A-B和C-D；计算n/2位乘法AC、BD、(A+B)(C+D)；计算(A+B)(C+D)-AC-BD；AC左移n位，(A+B)(C+D)-AC-BD)左移n/2位；计算XY。3.2 整数乘法输入：n位二进制整数X和Y 输出：X和Y的乘积通常，计算X*Y时间复杂性位O(n2)，我们给出一个复杂性为O(n1.59)的算法。68建立递归方程 T(n)=(1) if n=1T(n)=3T(n/2)+O(n) if n1使用Master定理 T(n)=

33、O(nlog3)=O(n1.59)69把C=AB中每个矩阵分成大小相同的4个子矩阵。每个子矩阵都是一个n/2 n/2矩阵。于是=展开并整理等式的右边，即得到计算的方法矩阵乘法：问题定义输入：两个n n矩阵A和A 输出：X和Y的积通常，计算XY的时间复杂性位O(n3)我们给出一个复杂性为O(n2.81)的算法。70M1 = A11 (B12 - B22)M2 = (A11 + A12) B22M3 = (A21 + A22) B11M4 = A22 (B21 - B11)M5 = (A11 + A22) (B11 + B22)M6 = (A12 - A22) (B21 + B22)M7= (A1

34、1 - A12) (B11 + B12) 计算n/2n/2矩阵的10个加减和7个乘法71C11 = M5 + M4 - M2 + M6C12 = M1 + M2C21 = M3 + M4C22 = M5 + M1 M3 M7 计算n/2n/2矩阵的8个加减 18个n/2n/2矩阵加减法，每个需O(n2) 7个n/2n/2矩阵乘法 建立递归方程 T(n)=O(1) n=2 T(n)=7T(n/2) + O(n2) n2 使用Master定理求解T(n) T(n) = O(nlog7) O(n2.81)72Volker Strassen（施特拉森）演算法 （1936now）In 2008 he w

35、as awarded the Knuth Prize Best now：Coppersmith-Winograd方法O(n2.376) 73寻找最近的配对点输入：Euclidean空间上的n个点的集合Q输出：P1, P2Q, Dis(P1, P2)=MinDis(X, Y) | X, YQ Dis(X, Y)是Euclidean距离: 如果X=(x1, x2), Y=(y1, y2)，则74一维空间算法利用排序的算法算法把Q中的点排序通过排序集合的线性扫描找出最近点对时间复杂性T(n)=O(nlogn)Divide-and-conquer算法预处理: 如果Q中仅包含2个点，则返回这个点对；求Q中点的中位数m。75Divide: 1. 用Q中点坐标中位数m把Q划分为两个 大小相等的子集合 Q1 = xQ | xm, Q2 = xQ | xmQ1Q2p1p2p3q3q2q1m76Conquer: 1. 递归地在Q1和Q2中找出最接近点对 (p1, p2)和(q1, q2)Q1Q2p1p2p3q3q2q1m2. 在(p1, p2)、(q1, q2)和某个(p3, q3)之间选择最接近点对(x, y), 其中p3是Q1中最大点, q3是Q2中最小点，(x, y)