《算法递归与分治策略ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法递归与分治策略ppt课件.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物算法递归与分治策略我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2Hanoi塔问题 例1：Hanoi塔
2、问题：有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上的n1个盘移至B。 于是可得到如下的程序：void Hanoi(int n, int Fr, int To, int As) if (n 0) Hanoi(n1, Fro, Ass, To); Move(Fro, To); H
3、anoi(n1, Ass, To, Fro) 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3递归的概念 简单地说，递归就是用自己来定义自己。递归算法是一个直接或间接地调用自己的算法。 一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合：P (S, P) 这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为P if B then Q else (
4、S, P) 其中Q也不包含P，B为递归终止条件。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4递归元 递归算法的思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。 这种规模的变化就体现在递归算法的变元中的一类(一个或几个)变元上，这类变元被称之为递归元。 递归元的变化是在递归定义中确定的，它的变化应能导致递归算法的终止。 在递归算法的设计中递归元是非常
5、重要的。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物5常见的递归形式 多变元递归； 多步递归； 嵌套递归； 联立递归 除基本的递归形式外，其它常见的递归形式有四种，它们是：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美
6、丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6多变元递归 多变元递归就是递归元多于一个的递归。 例2：整数划分问题：将一个正整数n表示为一系列正整数之和，n = n1 + n2 +nk 其中n1n2nk1, k1。 正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分的个数成为正整数n的划分数，记作(n)。 例如(6) = 11 ，即整数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我吓了一跳，蝎子是多么丑恶和恐怖的东西，
7、为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物7正整数的划分 有时候，问题本身具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以直接找到递归关系。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？
8、但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物8正整数的划分 因此考虑增加一个自变量：在正整数的所有不同划分中，将最大加数n1不大于m的划分个数记为q(n, m)，可以建立如下的递归关系： 最简单情形：(1) q(n, 1)=1，q(1, m) =1 n, m1; 递归关系： (2) q(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 = 1 q(n, m) = 1 + q(n, n1) n m q(n, m1
9、)+q(nm, m) nm1 数记为q(n, m)，可以建立如下的二元递归函数： int q(int n, int m) if (n 1) | (m 1) return 0; if (n = 1) | (m = 1) return 1; if(n 1nFibonacci函数是一个两步的递归函数。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物10嵌套递归 所谓嵌套递归是指递
10、归调用中又含有递归调用，又称为多重递归。 例如Ackermann函数： 2 n=1, m=0 A(n, m) = 1 m= 0, n = 0 n+2 n = 2, m=0 A(A(n-1, m), m-1) n, m = 1nAckermann函数是一个双重的递归函数。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物11联立递归 联立递归是同时定义几个函数，它们彼此相互调用
11、，从而形成递归，又称间接递归。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物12 将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)= 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为
12、止。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物13 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(
13、n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物14
14、将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，
15、证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物15 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4
16、)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4) 分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物16分治法的一般算法 分治法的一般的
17、算法模式为： Divide-and-Conquer(P) /|P|=n0表示P的规模不超过阈值n0，可直接求解 if (|P|=n0) return Adhoc(P); divide P into smaller subinstants P1, ., Pk; for (i =1; i = k; i+) yi = Divide-and-Conquer(Pi); return Merge(y1, , yk); /算法Merge(y1, , yk)表示将子问题的解合成P的解人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效
18、的。这种使子问题规模大致相等的做法是出自一种平衡平衡(balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物17分治法的时间复杂性 分治法的时间复杂性为： O(1) n = 1T(n) kT(n/m) + f(n) n1其中设子问题规模为n/m，Merge的时间为f(n)。n求解此递归方程可得：T(n)
19、 nlogmk logmn1 + kjf(n/mj) j=0我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物18该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问该问题可以分解为若干个规模较小的相同问题，即该问题具有题具有最优子结构性质最优子结构性质利用该问题分解出的子问题的解可以合并
20、为该问题的解；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。之间不包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共
21、的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物19分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还
22、是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。 分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析： 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题
23、的解；分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物20给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：template int Bina
24、rySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 算法复杂度分析：算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的
25、世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物练习1 设a0:n-1是一个有n个元素的数组，k(0=k=n-1)是一个非负整数。试设计一算法将子数组a0:k与ak+1:n-1换位。要求只用到O(1)的辅助空间，且时间复杂度尽可能低。21我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物练习2 设n个不同的整数排好序后存于T0:n-1中。若存在一个下标i，0=in，使得Ti=i, 设计一个有效算法找到这个下标。要求算法时间复杂度为O(logn)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物课后练习 http:/