递归与分治策略

《递归与分治策略》由会员分享，可在线阅读，更多相关《递归与分治策略（45页珍藏版）》请在金锄头文库上搜索。

1、1第二章第二章递归与分治策略递归与分治策略2Hanoi塔问题 例1：Hanoi塔问题：有A、B、C三根柱子。A 上有n个圆盘，自下而上由大到小地叠在一起 。ABCn现要将A上的全部圆 盘移到B上，并要求 ：(1)每次只能移动一 个圆盘；(2)任何时刻 都不允许将较大的圆 盘压在较小的圆盘上 ；(3)圆盘只能在A、 B、C三个柱子间移动 。nHanoi塔的解可以很自然地看成这样一个过程 ：(1)先将A上面n1 个盘移至C。 (2)再将A上剩下的 1个盘移至B。 (3)最后将C上的n 1个盘移至B。 于是可得到如下的程序： void Hanoi(int n, int Fr, int To, int

2、 As)if (n 0) Hanoi(n1, Fro, Ass, To);Move(Fro, To);Hanoi(n1, Ass, To, Fro)3递归的概念 简单地说，递归就是用自己来定义自己。递归 算法是一个直接或间接地调用自己的算法。 一般地说，一个递归过程P可以表示为基语句 S(不含P)和P自身的组合： P (S, P) 这样的表示包含了过程不终止的可能，因此递 归算法应更准确地表述为 P if B then Q else (S, P)其中Q也不包含P，B为递归终止条件。4递归元 递归算法的思想是将对较大规模的对象的操作 归结为对较小规模的对象实施同样的操作。 这种规模的变化就体现在

3、递归算法的变元中的 一类(一个或几个)变元上，这类变元被称之为 递归元。 递归元的变化是在递归定义中确定的，它的变 化应能导致递归算法的终止。 在递归算法的设计中递归元是非常重要的。5常见的递归形式 多变元递归； 多步递归； 嵌套递归； 联立递归 除基本的递归形式外，其它常见的递归 形式有四种，它们是：6多变元递归 多变元递归就是递归元多于一个的递归。 例2：整数划分问题：将一个正整数n表示为 一系列正整数之和， n = n1 + n2 +nk其中n1n2nk1, k1。 正整数n的一个这种表示称为正整数n的一个 划分。正整数n的不同的划分的个数成为正整 数n的划分数，记作(n)。 例如(6)

4、 = 11 ，即整数6的划分数为11种：6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+12+2+2, 2+2+1+1, 2+1+1+1+1， 1+1+1+1+1+17正整数的划分 有时候，问题本身具有比较明显的递归 关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分 数，则难以直接找到递归关系。8正整数的划分 因此考虑增加一个自变量：在正整数的所有 不同划分中，将最大加数n1不大于m的划分个 数记为q(n, m)，可以建立如下的递归关系： 最简单情形：(1) q(n, 1)=1，q(1, m) =1 n, m1; 递归关系： (2) q(

5、n, n) = 1 + q(n, n1)，n1; 产生的新情况： (3) q(n, m) = q(n, m1) + q(nm, m), nm1 (4) q(n, m) = q(n, n), nm。1 n = 1 或 m = 1q(n, m) = 1 + q(n, n1) n mq(n, m1)+q(nm, m) nm1 数记为q(n, m)，可以建立如下的二元递归函数：int q(int n, int m) if (n 1nFibonacci函数是一个两步的递归函数。10嵌套递归 所谓嵌套递归是指递归调用中又含有递归调用 ，又称为多重递归。 例如Ackermann函数：2 n=1, m=0A(

6、n, m) = 1 m= 0, n = 0n+2 n = 2, m=0A(A(n-1, m), m-1) n, m = 1nAckermann函数是一个双重的递归函数。11联立递归 联立递归是同时定义几个函数，它们彼 此相互调用，从而形成递归，又称间接 递归。12递归方法小结 递归方法是将复杂的问题分解为一些较为简单 的子问题的组合。这些子问题均与其相应的原 问题相同。 递归算法一定要有一个或几个最简单情况的计 算(非递归分支)，如果缺少将造成递归不终止 。 递归算法是有层次的，低层子问题的解组合成 高层问题的解。各层之间最好通过参数传递来 交流信息，如使用全局量，则要注意全局量的 及时修订。

7、13递归小结递归小结优点：结构清晰，可读性强，而且容易用 数学归纳法来证明算法的正确性，因此它 为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是 耗费的计算时间还是占用的存储空间都比 非递归算法要多。14解决方法：在递归算法中消除递归调用，使其转化为 非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作 栈。该方法通用性强，但本质上还是递归，只不过人 工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求 出结果。后两种方法在时空复杂度上均有较大改善，但其 适用范围有限。递归小结递归小结15分治

8、法16 将要求解的较大规模的问题分割成k个更小规模的 子问题。算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 对这k个子问题分别求解。如果子问题的规模仍然不够 小，则再划分为k个子问题，如此递归的进行下去，直 到问题规模足够小，很容易求出其解为止。17算法总体思想算法总体思想 对这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/

9、4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。18算法总体思想算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。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)19算法总体思想算法总体思想 将求出的小规模的问题的解合并为一个更大规模的问 题的解，

10、自底向上逐步求出原来问题的解。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)分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。20分治法的一般算法 分治法的一般的算法模式为： Divide-and-Conquer(P) /|P|ai，同理我们只要在amid 的后面查找x即可。无论是在前面还是后面查找x，其方法都 和在a中查找x一样，只不过是查找的规模缩小了。这

11、就说明 了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前 面或后面查找x是独立的子问题，因此满足分治法的第四个适 用条件。二分搜索技术二分搜索技术 给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找 出一特定元素x。 分析： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。 24二分搜索技术二分搜索技术 给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找 出一特定元素x。据此容易设计出二分搜索算法： te

12、mplate int BinarySearch(Type a, const Typeif (x = am) return m;if (x 0时，将2k2k的棋盘分割成4个2k12k1的 子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1然而，这样一来四个子棋 盘的情形就不一致了。因 为递归求解是将问题归结 到较小的规模的同一问题 ，所以就需要将三个正常 子棋盘也转化成特殊棋盘 。为此，可以用一个L型骨 牌来覆盖其余三个子棋盘 的会合处，如左图所示。 这样原问题转化成了四个 较小规模的子问题。递归 地分割下去直至单格棋盘 。n特殊方格必定位于4个子棋盘之一中。30棋盘覆盖的算

13、法 1.棋盘覆盖(参数表) 2. 3. 如果是单个格子，则返回； 4. 将棋盘划分成尺寸为一半的子棋盘； 5. 判断特殊方格在哪个子棋盘中，再用相应 的骨牌覆盖相应结合部，并记下它们的位置 ； 6. 依次对左上角、右上角、左下角和右下角 这四个子棋盘进行棋盘覆盖； 7. 31棋盘覆盖算法的正确性 要证明一个算法的正确性，需要证明两点： (1)算法的部分正确性； (2)算法的终止性。 下面我们用归纳法证明棋盘覆盖算法的部分正 确性：n归纳基础：对尺寸为 21的特殊棋盘，无论特殊 方格在什么位置，显然都可正确覆盖。n假设对尺寸2k1的特殊棋盘均可正确覆盖。n对尺寸2k的特殊棋盘，算法划分为四个尺寸

14、为 2k1的子棋盘，再用一块L型骨牌覆盖三个正常 子棋盘的结合处后，恰好形成四个尺寸2k1的 特殊棋盘，由归纳假设，它们均可正确覆盖。 因而也正确覆盖了尺寸2k的特殊棋盘。n由归纳法可知，棋盘覆盖算法是部分正确。n算法的终止性：n递归的终止条件为递归元size为1时递归终止。n递归元size的初值为2k。每次递归时递归元减 半，即size=size/2；因此，必然在有穷步内递 减为1。n所以此算法必定终止。n由部分正确性和终止性可知，此算法是完全正 确的。32棋盘覆盖棋盘覆盖void chessBoard(int tr, int tc, int dr, int dc, int size)if

15、(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;/ 覆盖其余方格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);33棋盘覆盖算法中的参数参数表中应有哪些参数呢？它们是： 棋盘用一个二维整型数组Board表示。 递归元：棋盘尺寸size=2k。递归时棋盘尺寸减半 ，即size=size/2；当size为1时递归终止。 表示棋盘位置参