递归与分治

Size: px

Start display at page:

Download "递归与分治"

饶鲁
4 years ago
Views:

1 递归与分治

2 递归函数设计阶乘的计算公式 5! = = 120 N! = N N 换一种思路可以写成 5! = 5 4! 4! = 4 3! 3! = 3 2! 2! = 2 1! 1! = 1 自底向上计算结果 2

3 递归函数设计阶乘公式可以写成 N! = N N 1! 1! = 1 这其实就是递归的思想, 即函数的定义中使用函数自身的方法除了计算机科学中, 还有更多的递归的例子 3

4 递归的例子从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢? 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢? 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢? 4

5 递归的例子德罗斯特效应 Droste effect 是递归的一种视觉形式是指一张图片的某个部分与整张图片相同, 如此产生无限循环 5

6 德罗斯特效应 6

7 德罗斯特效应 7

8 设计递归函数程序设计中如何设计这样的函数呢? N! = N N 1! 1! = 1 1 def fac(n): 2 return N * fac(n-1) 这个函数没有边界条件, 函数 fac 的调用将无法终止一定要注意首先递归函数要有一个边界条件, 之后再考虑递归的步骤 8

9 9

10 设计递归函数 def fac(n): if N <= 1: return 1 边界条件 else: return N * fac(n-1) 递归步骤 10

11 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) >>> fac(1) Result: 1 初始条件没有问题! 11

12 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 12

13 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 13

14 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * fac(3) 14

15 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * fac(3) 3 * fac(2) 15

16 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * fac(3) 3 * fac(2) 2 * fac(1) 16

17 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) 栈 fac(5) 5 * fac(4) 4 * fac(3) 保存了所有对 fac 的调用 3 * fac(2) 2 * fac(1) 1 17

18 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * fac(3) 3 * fac(2) 2 * 1 18

19 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * fac(3) 3 * 2 19

20 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * fac(4) 4 * 6 20

21 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) 5 * 24 21

22 def fac(n): if N <= 1: return 1 函数幕后 else: return N * fac(n-1) fac(5) Result:

23 递归函数设计挖掘自相似的特性产生简介优雅的代码更少的工作! def fac(n): if N <= 1: return 1 else: return N * fac(n-1) 你需要控制边界条件也就是你能想到的最简单的情况! 递归完成了几乎所有的剩余工作! 23

24 递归函数设计但是你也必须自己完成一步 def fac(n): if N <= 1: return 1 else: return fac(n) 这样是无法工作的! 24

25 递归定义递归 (Recursion) 就是子程序 ( 或函数 ) 直接调用自己或通过一系列调用语句间接调用自己, 是一种描述问题和解决问题的基本方法递归有两个基本要素 : 1. 边界条件 : 确定递归到何时终止 ; 2. 递归模式 : 大问题是如何分解为小问题的 25

26 Fibonacci 数列无穷数列 1,1,2,3,5,8,13,21,34, 55,, 称为 Fibonacci 数列它可以递归地定义为 : F( n) F( n 1) 1 1 F( n 2) n n n 边界条件递归模式 26

27 Fibonacci 数列 def Fibonacci(N): if N <= 1: return 1 else: return Fibonacci(N-2) + Fibonacci(N-1) 这段程序中什么是边界条件? 什么是递归模式? 你能模拟一下这个程序的运行吗? 27

这就是所谓的汉诺塔不论白天黑夜, 总有一个僧侣在按照下面的法则移动这些金片 : 一次只移动一片, 不管在哪根针上,

28 Hanoi 塔问题在印度, 有这么一个古老的传说 : 在世界中心贝拿勒斯 ( 在印度北部 ) 的圣庙里, 一块黄铜板上插着三根宝石针印度教的主神梵天在创造世界的时候, 在其中一根针上从下到上地穿好了由大到小的 64 片金片, 这就是所谓的汉诺塔不论白天黑夜, 总有一个僧侣在按照下面的法则移动这些金片 : 一次只移动一片, 不管在哪根针上, 小片必须在大片上面僧侣们预言, 当所有的金片都从梵天穿好的那根针上移到另外一根针上时, 世界就将在一声霹雳中消灭, 而梵塔庙宇和众生也都将同归于尽 28

29 Hanoi 塔问题一共有 3 个塔座, 在一个塔座上有一叠圆盘, 这些圆盘自下而上, 由大到小地叠在一起要求将塔座上的这一叠圆盘移到另一塔座上, 并仍按同样顺序叠置并遵守以下移动规则 : 1. 每次只能移动 1 个圆盘 ; 2. 任何时刻都不允许将较大的圆盘压在较小的圆盘之上 ; 3. 在满足移动规则 1 和 2 的前提下, 可将圆盘移至任一塔座上 29

30 Hanoi 塔问题首先将 A 上的黄色和绿色通过 C 移动到 B 上 A B C 30

31 Hanoi 塔问题首先将接着将 A 上的黄色和绿色通过红色移动到 CC 移动到柱上 B 上 A B C 31

32 Hanoi 塔问题接着将最后将 A B 柱上的红色移动到黄色和绿色通 C 柱上过 A 柱移动到 C 上, 完成! A B C 32

33 Hanoi 塔问题最后将 B 柱上的黄色和绿色通过 A 柱移动到 C 上, 完成! A B C 33

34 Hanoi 塔问题汉诺塔问题可以通过以下三个步骤实现 : 1. 将塔 A 上的 n-1 个碟子借助塔 C 先移到塔 B 上 2. 把塔 A 上剩下的一个碟子移到塔 C 上 3. 将 n-1 个碟子从塔 B 借助塔 A 移到塔 C 上显然, 这是一个递归求解的过程 34

35 Hanoi 塔问题 35

36 Hanoi 塔问题 1 def Hanoi(N, A, B, C): 2 3 if N == 1: 4 Move(A,C) 5 6 else: 7 Hanoi(N-1, A, C, B) 8 Move(A, C) 9 Hanoi(N-1, B, A, C) 36

37 递归函数的运行轨迹在递归函数中, 调用函数和被调用函数是同一个函数, 需要注意的是递归函数的调用层次, 如果把调用递归函数的主函数称为第 0 层, 进入函数后, 首次递归调用自身称为第 1 层调用 ; 从第 i 层递归调用自身称为第 i+1 层反之, 退出第 i+1 层调用应该返回第 i 层采用图示方法描述递归函数的运行轨迹, 从中可较直观地了解到各调用层次及其执行情况 37

38 Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,A,B,C) Move (A,C) Hanio(1,C,A,B) Move (C,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Hanio(1,B,C,A) Move (B,A) Hanio(2,B,A,C) Move (B,C) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) 结束 38

39 Hanoi 塔问题由上面的递归函数我们可以推得 f n = 2f n f(n) 是 n 个金片时需要移动的次数, 并且 f 1 = 1 我们可以得到 f n = 2 n 1 39

40 Hanoi 塔问题那么把 64 片金片都移动到位的话, 需要多长的时间呢? f 64 = = 如果假设每秒移动一次, 一年有秒, 那么需要 = 年 = 5849 亿年而地球存在至今不过 45 亿年, 太阳系的预期寿命据说也就是数百亿年真的过了 5845 亿年, 不说太阳系和银河系, 至少地球上的一切生命, 连同梵塔庙宇等, 都早已经灰飞烟灭 40

41 总结递归递归算法结构清晰, 可读性强, 而且容易用数学归纳法来证明算法的正确性, 因此, 它为设计算法和调试程序带来很大方便, 是算法设计中的一种强有力的工具但是, 因为递归算法是一种自身调用自身的算法, 随着递归深度的增加, 工作栈所需要的空间增大, 递归调用时的辅助操作增多, 因此, 递归算法的运行效率较低 41

42 分治法将一个难以直接解决的大问题, 划分成一些规模较小的子问题, 以便各个击破, 分而治之更一般地说, 将要求解的原问题划分成 k 个较小规模的子问题, 对这 k 个子问题分别求解如果子问题的规模仍然不够小, 则再将每个子问题划分为 k 个规模更小的子问题, 如此分解下去, 直到问题规模足够小, 很容易求出其解为止, 再将子问题的解合并为一个更大规模的问题的解, 自底向上逐步求出原问题的解 42

43 分治法的典型情况原问题的规模是 n 子问题 1 的规模是 n/2 子问题 2 的规模是 n/2 子问题 1 的解子问题 2 的解原问题的解 43

44 分治法的求解过程分治法的求解过程由以下三个阶段组成 : 1. 划分把规模为 n 的原问题划分为 k 个规模较小的子问题, 并尽量使这 k 个子问题的规模大致相同 2. 求解子问题各子问题的解法与原问题的解法通常是相同的, 可以用递归的方法求解各个子问题, 有时递归处理也可以用循环来实现 3. 合并把各个子问题的解合并起来, 合并的代价因情况不同有很大差异, 分治算法的有效性很大程度上依赖于合并的实现 44

45 归并排序二路归并排序的分治策略是 : 1. 划分 : 将待排序序列 r 1, r 2,, r n 划分为两个长度相等的子序列 r 1,, r n/2 和 r n/2+1,, r n ; 2. 求解子问题 : 分别对这两个子序列进行排序, 得到两个有序子序列 ; 3. 合并 : 将这两个有序子序列合并成一个有序序列 45

46 归并排序 r 1 r n/2 r n/2+1 r n 划分 r 1 < <r n/2 r n/2+1 < <r n 递归处理 r'' 1 < <r'' n/2 <r'' n/2+1 < <r '' n 合并解 46

47 快速排序快速排序的分治策略是 : 1. 划分 : 选定一个记录作为基准, 将整个序列划分为两个子序列 r 1 r i-1 和 r i+1 r n, 前一个子序列中记录的值均小于或等于基准值, 后一个子序列中记录的值均大于或等于基准值 ; 2. 求解子问题 : 分别对划分后的每一个子序列递归处理 ; 3. 合并 : 由于对子序列 r 1 r i-1 和 r i+1 r n 的排序是就地进行的, 所以合并不需要执行任何操作 47

48 快速排序 [ r 1 r i-1 ] r i [ r i+1 r n ] 均 r i 基准均 r i 位于最终位置归并排序按照记录在序列中的位置对序列进行划分, 快速排序按照记录的值对序列进行划分 48

49 二分查找法二分查找法的分治策略是 : 1. 划分 : 取排过序的序列 r 1, r 2,, r n 中间一个数分为两个长度相等的子序列 ; 2. 求解子问题 : 判断是否是要查找的数字, 以及查找的数字在哪个序列中 ; 3. 合并 : 返回最终是否查找了到了相应的值 49

50 棋盘覆盖问题在一个 2 k 2 k (k 0) 个方格组成的棋盘中, 恰有一个方格与其他方格不同, 称该方格为特殊方格棋盘覆盖问题要求用 4 种不同形状的 L 型骨牌覆盖给定棋盘上除特殊方格以外的所有方格, 且任何 2 个 L 型骨牌不得重叠覆盖 50

51 棋盘覆盖问题如何利用分治的思想来解决棋盘覆盖问题呢? 分治法求解棋盘覆盖问题的技巧在于划分棋盘, 使划分后的子棋盘的大小相同, 并且每个子棋盘均包含一个特殊方格, 从而将原问题分解为规模较小的棋盘覆盖问题 51

52 棋盘覆盖问题 k>0 时, 可将 2 k 2 k 的棋盘划分为 4 个 2 k-1 2 k-1 的子棋盘, 这样划分后, 由于原棋盘只有一个特殊方格, 所以, 这 4 个子棋盘中只有一个子棋盘包含该特殊方格, 其余 3 个子棋盘中没有特殊方格为了将这 3 个没有特殊方格的子棋盘转化为特殊棋盘, 以便采用递归方法求解, 可以用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处, 从而将原问题转化为 4 个较小规模的棋盘覆盖问题递归地使用这种划分策略, 直至将棋盘分割为 1 1 的子棋盘 52

53 棋盘覆盖问题 2 k-1 2 k-1 2 k-1 2 k-1 2 k-1 2 k-1 2 k-1 2 k-1 棋盘分割构造相同子问题 53

54 棋盘覆盖问题采用分治法解决棋盘覆盖问题比单纯的穷举法要快速很多想一想你能不能写出像解决 Hanoi 塔问题的递归程序吗? 54

55 循环赛日程安排问题设有 n=2 k 个选手要进行网球循环赛, 要求设计一个满足以下要求的比赛日程表 : 1. 每个选手必须与其他 n-1 个选手各赛一次 ; 2. 每个选手一天只能赛一次按此要求, 可将比赛日程表设计成一个 n 行 n-1 列的二维表, 其中, 第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手 55

56 循环赛日程安排问题按照分治的策略, 可将所有参赛的选手分为两部分,n=2 k 个选手的比赛日程表就可以通过为 n/2=2 k-1 个选手设计的比赛日程表来决定递归地执行这种分割, 直到只剩下 2 个选手时, 比赛日程表的制定就变得很简单 : 只要让这 2 个选手进行比赛就可以了 56

57 循环赛日程安排问题 1 2 加 2 (a) 2 k (k=1) 个选手比赛加 (b) 2 k (k=2) 个选手比赛 (c) 2 k (k=3) 个选手比赛 57

58 循环赛日程安排问题显然, 这个求解过程是自底向上的迭代过程, 其中左上角和左下角分别为选手 1 至选手 4 以及选手 5 至选手 8 前 3 天的比赛日程, 据此, 将左上角部分的所有数字按其对应位置抄到右下角, 将左下角的所有数字按其对应位置抄到右上角, 这样, 就分别安排好了选手 1 至选手 4 以及选手 5 至选手 8 在后 4 天的比赛日程, 如图 (c) 所示具有多个选手的情况可以依此类推 58

59 循环赛日程安排问题这种解法是把求解 2 k 个选手比赛日程问题划分成依次求解 k 个选手的比赛日程问题换言之,2 k 个选手的比赛日程是在 2 k-1 个选手的比赛日程的基础上通过迭代的方法求得的 59

60 循环赛日程安排问题在每次迭代中, 将问题划分为 4 部分 : 1. 左上角 : 左上角为 2 k-1 个选手在前半程的比赛日程 ; 2. 左下角 : 左下角为另 2 k-1 个选手在前半程的比赛日程, 由左上角加 2 k-1 得到, 例如 2 2 个选手比赛, 左下角由左上角直接加 2 得到,2 3 个选手比赛, 左下角由左上角直接加 4 得到 ; 3. 右上角 : 将左下角直接抄到右上角得到另 2 k-1 个选手在后半程的比赛日程 ; 4. 右下角 : 将左上角直接抄到右下角得到 2 k-1 个选手在后半程的比赛日程 ; 60

幻灯片 1

幻灯片 1 算法分析与设计 Analysis and Design of Algorithm 第 3 次课要点回顾算法复杂度的概念时间复杂度空间复杂度复杂度的渐近性态略去低阶项所留下的主项五个渐近分析记号及其性质 NP 完全性理论问题的复杂度易解难解不可解问题 P NP NPC NP 难问题 1. 渐近上界记号 O 2. 渐近下界记号 3. 紧渐近界记号 4. 非紧上界记号 o 5. 非紧下界记号