《计算机算法分析与设计》由会员分享，可在线阅读，更多相关《计算机算法分析与设计（72页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 递归与分治策略递归与分治策略1学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术； （2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。2n将要求解的较大规模的问题分割成k个更小规模的子问 题。算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。3算法
2、总体思想算法总体思想n对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。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)n将求出的小规模问题的解, 合并为一个更大规模的问题 解，自底向上逐步求出原来问题的解。4算法总体思想算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。nT(n)
3、=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) 5算法总体思想算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。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)分治法的设计思想: 将一个难以直接解决
4、的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。62.1 递归的概念递归的概念n直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。n由分治法产生的子问题往往是原问题的较小模 式，这就为使用递归技术提供了方便。n反复应用分治手段，可使子问题与原问题类型 一致而其规模不断缩小，最终使子问题缩小到 很容易直接求解。这自然导致递归过程的产生 。n分治与递归像一对孪生兄弟，经常同时应用在 算法设计之中，并由此产生许多高效算法。下面来看几个实例7例1 阶乘函数阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函 数只有具备
5、了这两个要素，才能在有限次计算后得出 结果。8例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，称为 Fibonacci数列。它可以递归地定义为：边界条件递归方程p第n个Fibonacci数可递归地计算如下： int fibonacci(int n)if (n 1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)， ，(rn)perm(Rn)构成。参见 P9 代码 15例5 整数划分问题p将正整数n表示成一系列正整数之和： n=n1+n2+nk 其中n1n2nk1，k1。p正整数n的这种表示称为正整数n的划分。p求正整数n的不同划分个数1
6、6n分析：前面的几个例子中，问题本身都具有比较 明显的递归关系，易用递归函数直接求解。n本例若设p(n)为正整数n的划分数，则难以找到递 归关系。l例如正整数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。17(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即现考虑增加一个自变量：将最大加数n1不大于m的划 分个数记作q(n,
7、m)。q(n,m)有如下递归关系：18(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分,由n1m-1 的 划分和n1=m的划分组成。注意：正整数n的n1=m的所有划分形式为m+m1+mi =n where mj m, j=1,2,iThat is, m1+mi =n-m因此，n的n1=m的划分个数是q(n-m, m)(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。n1=m的划 分个数19q(n,m)递归关系:正整数n的划分数p(n)=q(n, n)代码见P1120例6 Hanoi塔问题
8、n设A,B,C是3个塔座。开始时，在A上有n个圆盘，这些圆盘自下而上，由大 到小地叠在一起。各圆盘从小到大编号为1,2,n。 n问题：现要求将A上的这一叠圆盘移到B上，并仍按同样顺序 叠置。 p在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上 ； 规则3：在满足规则1,2的前提下，可将圆盘移至A,B,C中任一 塔座上。21 在问题规模较大时，较难找到一般的解法，因此用递 归技术来解决这个问题。 当n=1时，问题比较简单。只要将编号1的圆盘从塔座 A直接移至塔座B上即可。 当n1时，用塔座C作为辅助，设法将n-1个较小的圆
9、盘从塔座A移至C，然后，将剩下的最大圆盘从塔座A 移至B。 再设法将n-1个较小的圆盘从塔座C移至B。22解Hanoi塔问题的递归算法如下：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);(n-1)个由A移 到C借用B编号n的圆盘 由A移到B(n-1)个由C移 到B借用A 由此可见，n个圆盘的移动问题可分为2次n-1个圆 盘的移动问题，这又可以递归地用上述方法来做。23递归小结递归小结 优点：结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性
10、。因此， 它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是 耗费的计算时间，还是占用的存储空间， 都比非递归算法要多。24解决方法：在递归算法中消除递归调用，使其 转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调 用工作栈。该方法通用性强，但本质上还是递 归，只不过人工做了本来由编译器做的事情， 优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为迭代求出结果 。后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。递归小结递归小结25分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题
11、一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该问 题具有最优子结构性质因为问题的计算复杂性一般是随着问题规模的增加 而增加，大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题 可以满足的，此特征反映了递归思想的应用26n利用该问题分解出的子问题的解可以合并为该问题的解 ；n该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。 能否利用分治法完全取决于问题是否具有这条特征 ，如果具备了前两条特征，而不具备第三条特征， 则可以考虑贪心算法或动态规划。如果各子问题是不独立的，则分治法要做许
12、多不必 要的工作，重复地解公共的子问题，此时虽然也可 用分治法，但一般用动态规划较好。27divide-and-conquer(P)if ( | P | amid，则x在amid的后面。n无论在哪部分查找x，其方法都和在a中查找x一样 ，只不过是查找的规模缩小了。这就说明此问题满 足分治法的第二个和第三个适用条件。n该问题可以分解为若干个规模较小的相同问题;n分解出的子问题的解可以合并为原问题的解；33分析：很显然此问题分解出的子问题相互独 立，即在amid的前面或后面查找x是独立 的子问题，因此满足分治法的第四个适用 条件。分解出的各个子问题是相互独立的。 34二分搜索技术二分搜索技术 给定
13、已按升序排好序的n个元素a0:n-1，现要在这n个元素中找 出一特定元素x。据此容易设计出二分搜索算法： template int BinarySearch(Type a , const Typeif (x = am) return m;if (x 0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘, Figure (a)所 示。l特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特 殊方格。l为将无特殊方格子棋盘转化为特殊棋盘，可以用一个骨牌覆盖 3个较小棋盘的会合处，如 Figure(b)所示，从而将原问题转化为 4个较小规模的棋盘覆盖问题。l递归地使用这种分割，直至棋盘简化为棋盘
14、11。 44棋盘覆盖棋盘覆盖 第第2 2版版p18-19 p18-19 第第3 3版版 20-21 20-21 void chessBoard(int tr, int tc, int dr, int dc, int size)if (size = 1) return;int t = tile+, / L型骨牌号s = size/2; / 分割棋盘/ 覆盖左上角子棋盘if (dr = tc + s)/ 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else / 此棋盘中无特殊方格/ 用 t 号L型骨牌覆盖左下角boardtr + s - 1tc + s = t
15、;/ 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);/ 覆盖左下角子棋盘if (dr = tr + s else / 用 t 号L型骨牌覆盖左上角boardtr + stc + s = t;/ 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);45复杂度分析T(n)=O(4k) 渐进意义下的最优算法 推导过程: 原式等价于 T(k)=4T(k-1)+1 递推得: 4T(k-1)=4(4T(k-2)+1)=42T(k-2)+4 T(k)= 42T(k-2)+4 +1 又有: 42T(k-2)=43T(k-3)+42 故 T(k)= 43T(k-3)+42+4+1 . T(k)=4kT(0)+4k-1+4+1=O(4k)462.7 2.7 合并排序合并排序(1)(1)用分治策略进行排序用分治策略进行排序基本思想：将元素分成2个子集合，分别对子集合进行排序， 最终将排好序的子集合合并为有序集合。n=1时中止。 void MergeSort(Type a , int left, int right)if
