《《递归与分治》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《递归与分治》PPT课件.ppt（117页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 2005第第2章章 递归与分治策略递归与分治策略n几个例子几个例子n2.1递归的概念递归的概念n2.2分治法的基本思想分治法的基本思想n2.3分治法的应用分治法的应用n本章小结本章小结1算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 几个例子|称球游戏称球游戏n给定给定n个球，其中一个球为次品。次品在外表上与正常球个球，其中一个球为次品。次品在外表上与正常球无区别，但重量有分别（可能偏重或偏轻）。现在给一个无区别，但重量有分别（可能偏重或偏轻）。现在给一个天平，问：需要称几次才能将次品甄别出来？天平，问：需要称几次才能将次品甄别出来？|募捐问题募
2、捐问题n向贫困山区儿童募捐向贫困山区儿童募捐10,000元。元。|世界杯足球赛世界杯足球赛n全球全球200多支球队里，选出最好的。多支球队里，选出最好的。分治法的设计思想是分治法的设计思想是:将一个难以直接解决的大问题，分割成一将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而些规模较小的相同问题，以便各个击破，分而治之。治之。凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法2算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念例例1:阶乘函数阶乘函数 阶乘函数可递归地定义为：阶乘函数可递归
3、地定义为：边界条件边界条件递归方程递归方程注意：注意：(1)边界条件与递归方程是递归函数的二个要素，递归函数只边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：非递归定义：3算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例2:Fibonacci数列数列n问题引入问题引入n裴波那契（裴波那契（Fibonaccileonardo，约，约1170-1250）是意大）是意大利著名数学家在他的著作算盘书中许多有趣的问利著名
4、数学家在他的著作算盘书中许多有趣的问题，最富成功的问题是著名的题，最富成功的问题是著名的“兔子繁殖问题兔子繁殖问题”：如如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？n问题分析问题分析4算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念月份月份初生初生成熟成熟总数总数01011011211231234235535865813012345算法设计与分析算法设计与分析递归与分治策略递归与分
5、治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|数列的特点数列的特点n（1）数列的增长速度）数列的增长速度n（2）自然科学中的若干实例）自然科学中的若干实例n（3）构造一个新数列）构造一个新数列6算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|定义：定义：2.1 递归的概念7算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念如何求解？如何求解？n解法解法1：O(0.618n)int fib(int n)if(n=0)|(n=1)return n;return fibona
6、cci(n-1)+fibonacci(n-2);n解法解法2：O(n)n解法解法3：O(logn)fib(110)：O(0.618n)1022次运算次运算O(n)111次运算次运算O(logn)7次运算次运算8算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|思考：思考：n楼梯问题楼梯问题n有一楼梯共有有一楼梯共有n阶，上楼可以一步上一阶，也可以一步阶，上楼可以一步上一阶，也可以一步上两阶。上两阶。n编一个程序，计算共有多少种不同的走法？编一个程序，计算共有多少种不同的走法？9算法设计与分析算法设计与分析递归与分治策略递归与分治策
7、略 四川师范大学 计算机科学学院 刘芳 例例3Ackerman函数函数 当一个函数及它的一个变量是由函数自身定义时，称这个当一个函数及它的一个变量是由函数自身定义时，称这个函数是函数是双递归函数双递归函数。Ackerman函数函数A(n,m)定义如下定义如下：2.1 递归的概念10算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|Ackerman函数函数nA(n,0)n+2nA(n,1)2nnA(n,2)2n。nnA(n,4)的增长速度非常快，以至于没有适当的数的增长速度非常快，以至于没有适当的数学式子来表示这一函数。学式子来表示
8、这一函数。11算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例4排列问题排列问题n设计一个递归算法生成设计一个递归算法生成n个元素个元素r1,r2,rn的全的全排列。排列。n设设R=r1,r2,rn是要进行排列的是要进行排列的n个元素，个元素，Ri=R-ri。n集合集合X中元素的全排列记为中元素的全排列记为perm(X)，(ri)perm(X)表示在全排列表示在全排列perm(X)的每一个排列前加上前缀得的每一个排列前加上前缀得到的排列。到的排列。12算法设计与分析算法设计与分析1时，时，perm(R)由由:(r1)perm
9、(R1)(r2)perm(R2)(rn)perm(Rn)n构成。构成。|参考算法：参考算法：13算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例5整数划分问题整数划分问题n将一个正整数将一个正整数n表示成形如下式的一系列正整数的表示成形如下式的一系列正整数的和，称为和，称为n的一个划分。的一个划分。n形如：形如：nn1n2nk其中：其中：(ni1，i1,2,k，k1)且且nn1n2nk114算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念n例如：整数例如：整数6
10、的分划数有的分划数有11种种:n6；n5+1；n4+2，4+1+1；n3+3，3+2+1，3+1+1+1；n2+2+2，2+2+1+1，2+1+1+1+1；n1+1+1+1+1+1;15算法设计与分析算法设计与分析m1;n正整数正整数n的最大加数的最大加数n1不大于不大于m的划分的划分由由n1=m的划分的划分和和n1m-1的划分的划分组成。组成。16算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 而：正整数而：正整数n的划分数的划分数p(n)=q(n,n)。2.1 递归的概念|因此：因此：nq(n,m)的递归定义如下的递归定义如下17算法设计与分析
11、算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|例例6Hanoi塔问题塔问题n问题描述：问题描述：18算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题分析问题分析：2.1 递归的概念？A B C A B CHanoi(n ,A ,B ,C )圆盘数圆盘数 源柱源柱 辅助柱辅助柱 目标柱目标柱19算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 =+A B CHanoi(n-1,A,C,B)A B CHanoi(n-1,B,A,C)A B CMove(
12、n,A,C)2.1 递归的概念20算法设计与分析算法设计与分析 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);|递归函数的运行轨迹递归函数的运行轨迹2.1 递归的概念21算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A
13、,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束22算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分析：分析：n规模为规模为n的的Hanoi(n)问题，可以分解为问题，可以分解为2个规模为个规模为n-1的的Hanoi(n-1)问题和一个问题和一个Move操作。操作。n所以，所以，n个盘子的移动次数为个盘子的移动次数为2.1 递归的概念若若n=64，则移动次数为，则移动次数为264-1264
14、118,446,744,073,709,551,61523算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|264118,446,744,073,709,551,615是个什么概念？是个什么概念？n实例实例1：n假设每秒钟移动一次，一年约假设每秒钟移动一次，一年约31556926秒，秒，n计算表明：移动计算表明：移动64个盘子需要个盘子需要5800多亿年。多亿年。n实例实例2：n国王的麦子问题国王的麦子问题p一个高一个高4米、宽米、宽10米的粮仓装麦子，这个粮仓有米的粮仓装麦子，这个粮仓有3000万公里长，能绕地球赤道万公里长，能
15、绕地球赤道700圈，可以把地球全部表圈，可以把地球全部表面（包括海洋）铺上面（包括海洋）铺上2米厚的小麦层！它相当于全世米厚的小麦层！它相当于全世界两千多年小麦产量的总和界两千多年小麦产量的总和24算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|广义广义hanoi问题问题n问题描述问题描述n算法分析算法分析？Hanoi(n ,A ,B ,C ,D)圆盘数圆盘数 源柱源柱 辅助柱辅助柱 目标柱目标柱 A B C D A B C D2.1 递归的概念25算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1
16、 递归的概念|递归的优点和缺点递归的优点和缺点n优点：优点：n结构清晰，可读性强，而且容易用数学归纳法来证明算结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方法的正确性，因此它为设计算法、调试程序带来很大方便。便。n缺点：缺点：n递归算法的运行效率较低，无论是耗费的计算时间还是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。占用的存储空间都比非递归算法要多。26算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代
17、码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难2.1 递归的概念27算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.1 递归的概念|消除递归的方法消除递归的方法n采用一个用户定义的栈来模拟系统的递归调用工作栈。该采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。由编译器做的事情，优化效果不明显。n用递推来实现递归函数。用递推来实现递归函数。n通过变换能将一
18、些递归转化为尾递归，从而迭代求出结果。通过变换能将一些递归转化为尾递归，从而迭代求出结果。|注意：注意：n后两种方法在时空复杂度上均有较大改善，但其适用范围后两种方法在时空复杂度上均有较大改善，但其适用范围有限。有限。28算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 分治法的设计思想是分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。凡治众如治寡，分数是也。-孙子兵法孙子兵法2.2 分治法的
19、基本思想29算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解该问题的规模缩小到一定的程度就可以容易地解决；决；n该问题可以分解为若干个规模较小的相同问题，该问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，即子问题之间不包且各个子问题是相互独立的，即子问题之间不包含公共的子问题。含公共的子问题。n利用该问题分解出的子问题的解可以合并为该问利用该问题分解出的子问题的解可以合并为该问题
20、的解；题的解；30算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法（分治法（Divide and Conquer）的基本思想）的基本思想:n分解分解(Divide)：n将一个规模为将一个规模为n的问题，的问题，分解分解为为k个规模较小的子问题，个规模较小的子问题，这些子问题互相独立且与原问题形式相同。这些子问题互相独立且与原问题形式相同。n求解求解(Conquer):n若子问题规模较小而容易被解决则直接解，否则若子问题规模较小而容易被解决则直接解，否则递归递归地地解这些子问题。解这些子问题。n合并合并(Merge)：
21、n将各个子问题的解将各个子问题的解合并合并得到原问题的解。得到原问题的解。31算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法的分治法的设计模式设计模式divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题解决小规模的问题divide P into smaller subinstances P1,P2,.,Pk；/分解问题分解问题for(i=1;i=k;i+)/递归的解各子问题递归的解各子问题 yi=divide-and-conquer(Pi);return merge(y
22、1,.,yk);/将各子问题的解合将各子问题的解合并并/为原问题的解为原问题的解32算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|启发式规则：启发式规则：n平衡子问题：平衡子问题：n在用分治法设计算法时，最好使子问题的规模大致相同。在用分治法设计算法时，最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的也就是将一个问题划分成大小相等的k个子问题（通常个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种），这种使子问题规模大致相等的做法是出自一种平衡（平衡（Balancing）子问题）子问题的思想，它几
23、乎总是比子问的思想，它几乎总是比子问题规模不等的做法要好。题规模不等的做法要好。n独立子问题：独立子问题：n各子问题之间相互独立，这涉及到分治法的效率，如果各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子各子问题不是独立的，则分治法需要重复地解公共的子问题。问题。33算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.2 分治法的基本思想|分治法的典型情况分治法的典型情况 A Problem of size nSubproblem1 of size n/2Subproblem2 of size n/2
24、A solution to subproblem1A solution to subproblem2A solution to the original problem34算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分治法的时间复杂性分析分治法的时间复杂性分析通过迭代法求得方程的解通过迭代法求得方程的解：2.2 分治法的基本思想35算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 例：二分搜索技术|问题提出：问题提出：n给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n1，现要在这现要在这
25、n个元素中找出一特定元素个元素中找出一特定元素x。|分析：分析：36算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 2.3 分治法的应用n数值计算问题中的分治法数值计算问题中的分治法n组合问题中的分治法组合问题中的分治法n排序问题中的分治法排序问题中的分治法n几何问题中的分治法几何问题中的分治法37算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 应用专题一|数值计算问题中的分治法数值计算问题中的分治法n大数及其存储大数及其存储n大整数的乘法大整数的乘法nstrassen矩阵乘法矩阵乘法38算法设计与分析
26、算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大数及其存储|大数大数n计算机存储数据是按类型分配空间的。计算机存储数据是按类型分配空间的。n例如：例如：n在微型机上在微型机上数据类型数据类型存贮字节存贮字节数据范围数据范围int23276832767longint421474836482147483647float4（精确位数：位）（精确位数：位）(3.4e-383.4e+38)double8（精确位数：（精确位数：17位）位）(1.7e-3081.7e+308)39算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|
27、大数的存储方案大数的存储方案n数组数组n数值数组数值数组p从计算的方便性考虑，决定将数据是由低到高还是从计算的方便性考虑，决定将数据是由低到高还是由高到低存储到数组中；由高到低存储到数组中；p可以每位占一个数组元素空间，也可几位占一个数可以每位占一个数组元素空间，也可几位占一个数组元素空间。组元素空间。n字符型数组字符型数组p从键盘输入要处理的高精度数据，无需对高精度数从键盘输入要处理的高精度数据，无需对高精度数据进行分段输入，但计算是需要类型转换的操作。据进行分段输入，但计算是需要类型转换的操作。大数及其存储40算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科
28、学学院 刘芳 大数及其存储|大数的运算大数的运算n加法加法n减法减法n乘法乘法n100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963 895217 599993 229915 608914 463976 156578 286253 697920 827223 758251 185210 916864 000000 000000 000000 000000n除法除法n41算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题描述：问题描述：n设设X和和
29、Y都是都是n位的二进制整数，请设计一个有效位的二进制整数，请设计一个有效的算法，可以进行两个的算法，可以进行两个n位大整数的乘法运算。位大整数的乘法运算。|分析：分析：n1.小学的方法：小学的方法：O(n2)效率太低效率太低1111011000100000000110110011101大整数的乘法42算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 n2.可以用分治法的原理设计一个更有效的算法。可以用分治法的原理设计一个更有效的算法。将将n位的二进制整数分为位的二进制整数分为2段：段：An/2位位Bn/2位位Cn/2位位Dn/2位位X=Y=则：则：X
30、=A2n/2+B（乘乘2n/2，相当于左移相当于左移n/2位位）Y=C2n/2+D于是：于是：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD (1)大整数的乘法43算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法|效率：效率：n4次次n/2位整数乘法位整数乘法(AC,AD,BC,BD)；n3次不超过次不超过n位整数加法；位整数加法；n2次移位次移位(分别对应乘以分别对应乘以2n和和2n/2)n所有加法和移位共用所有加法和移位共用O(n)步计算。步计算。时间复杂性分析时间复杂性分析T(n)=O(n2)没
31、有改进没有改进44算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 时间复杂性分析时间复杂性分析 T(n)=O(nlog3)=O(n1.59)较大的改进较大的改进大整数的乘法改进：把改进：把(1)式稍作修改：式稍作修改：XY=AC2n+(AB)(DC)+AC+BD)2n/2+BD (2)效率：效率：3次次n/2位整数乘法位整数乘法(AC,BD,(AB)(DC)；6次不超过次不超过n位整数加、减法和位整数加、减法和2次移位；次移位；45算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法Char*M
32、ult(char X,char Y,int n)/两个两个n位整数相乘位整数相乘 S=sign(X)*sign(Y);/取乘积的符号取乘积的符号 X=abs(X);Y=abs(Y);if(n=1)return(S*X*Y);else A=X的左边的左边n/2位；位；B=X的右边的右边n/2位；位；C=Y的左边的左边n/2位；位；D=Y的右边的右边n/2位；位；m1=Mult(A,C,n/2);m2=Mult(A-B,D-C,n/2);m3=Mult(B,D,n/2);S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return S;注意注意：该算法可改为十进制数乘法，只需将基数该
33、算法可改为十进制数乘法，只需将基数2变为变为10，即：即：2n 10n,2n/2 10n/246算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 大整数的乘法|分析分析u传统的方法传统的方法：O(n2)效率太低效率太低u分治法分治法:O(n1.59)较大的改进较大的改进|更快的方法？更快的方法？n对于大整数乘法，它能在对于大整数乘法，它能在O(nlogn)时间内解决。时间内解决。|是否能找到线性时间的算法？是否能找到线性时间的算法？n目前为止还没有结果目前为止还没有结果。47算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算
34、机科学学院 刘芳 strassen矩阵乘法|矩阵乘法矩阵乘法n问题描述问题描述nAnnBnn=Cnnn求解方法求解方法n传统方法：传统方法：O(n3)n分治法分治法pO(n2.81)pO(n2.376)48算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|分治法分治法n将矩阵将矩阵A，B和和C中每一矩阵都分块成中每一矩阵都分块成4个大小相等的子矩个大小相等的子矩阵，每个子矩阵都是阵，每个子矩阵都是n/2n/2的方阵。的方阵。n由此可将方程由此可将方程C=AB重写为：重写为：由此可得由此可得：strassen矩阵乘法49算法设计与分析算法设计与分析递归
35、与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 n为了降低时间复杂度，必须减少乘法的次数。为了降低时间复杂度，必须减少乘法的次数。nStrassen矩阵乘法矩阵乘法strassen矩阵乘法50算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 验证验证:C22=M5+M1-M3-M7 =(A11+A22)(B11+B22)+A11(B12-B21)-(A21+A22)B11-(A11-A21)(B11+B12)=A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22-A21B11-A22B11-A11B11
36、-A11B12+A21B11+A21B12 =A21B12+A22B22strassen矩阵乘法51算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 strassen矩阵乘法52算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 完整的完整的Strassen算法如下：算法如下：STRASSEN(n,A,B,C)if(n=2)MATRIX-MULTIPLY(A，B，C);/普通普通2*2矩阵相乘矩阵相乘 else /将矩阵将矩阵A和和B分块分块;STRASSEN(n/2,A11,B12-B22,M1);STRA
37、SSEN(n/2,A11+A12,B22,M2);STRASSEN(n/2,A21+A22,B11,M3);STRASSEN(n/2,A22,B21-B11,M4);STRASSEN(n/2,A11+A22,B11+B22,M5);STRASSEN(n/2,A12-A22,B21+B22,M6);STRASSEN(n/2,A11-A21,B11+B12,M7);strassen矩阵乘法53算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 应用专题二|组合问题中的分治法组合问题中的分治法n棋盘覆盖问题棋盘覆盖问题n循环日程赛安排问题循环日程赛安排问题n
38、最大子段和问题最大子段和问题54算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题描述：问题描述：n在一个在一个2k2k个方格组成的棋盘中，恰有一个方格个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称与其它方格不同，称该方格为一特殊方格，且称该棋盘为特殊棋盘。该棋盘为特殊棋盘。n在棋盘覆盖问题中，要用图示的在棋盘覆盖问题中，要用图示的4种不同形态的种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何所有方格，且任何2个个L型骨牌不得重叠覆盖。型骨牌不得重叠覆盖
39、。棋盘覆盖问题55算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 棋盘覆盖问题|例如：例如：nk2时的一个特殊棋盘时的一个特殊棋盘2k 2k的棋盘覆盖中，用到的骨牌数为的棋盘覆盖中，用到的骨牌数为(4k-1)/356算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|例如：例如：554451143122332棋盘覆盖问题57算法设计与分析算法设计与分析0时，考虑采用分治策略：时，考虑采用分治策略：棋盘覆盖问题58算法设计与分析算法设计与分析0时时,测试哪个子棋盘残缺以及形成测试哪个子棋盘残缺以及形成3个残缺
40、子棋盘个残缺子棋盘需要需要O(1),覆盖覆盖4个残缺子棋盘需四次递归调用个残缺子棋盘需四次递归调用,共需时共需时间间4T(k1)。T(k)=O(4k)渐进意义下的最优算法渐进意义下的最优算法与所需骨与所需骨牌数同阶牌数同阶棋盘覆盖问题59算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|还可以将棋盘覆盖推广到一般情况：还可以将棋盘覆盖推广到一般情况：887786675446554321133221121111109912121110109877655887665433211443221棋盘覆盖问题60算法设计与分析算法设计与分析递归与分治策略递归与分
41、治策略 四川师范大学 计算机科学学院 刘芳|问题描述：问题描述：n设计一个满足以下要求的比赛日程表：设计一个满足以下要求的比赛日程表：n(1)每个选手必须与其他每个选手必须与其他n1个选手各赛一次；个选手各赛一次；n(2)每个选手一天只能赛一次；每个选手一天只能赛一次；n(3)循环赛一共进行循环赛一共进行n1天。天。循环赛日程表61算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|例如：例如：1234567821436587341278564321876556781234658721437856341287654321队队天天62算法设
42、计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|分析：分析：n法法1：分治策略：分治策略n按分治策略，将所有的选手分为两半，按分治策略，将所有的选手分为两半，n个选手的比赛个选手的比赛日程表就可以通过为日程表就可以通过为n/2个选手设计的比赛日程表来决个选手设计的比赛日程表来决定。定。n递归地用对选手进行分割，直到只剩下递归地用对选手进行分割，直到只剩下2个选手时，比个选手时，比赛日程表的制定就变得很简单。这时只要让这赛日程表的制定就变得很简单。这时只要让这2个选手个选手进行比赛就可以了。进行比赛就可以了。A1A2A2A163算法设计与分析
43、算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|分析分析n法法2：递推法：递推法(迭代法迭代法)122112342143341243211234567821436587341278564321876556781234658721437856341287654321加加2加加464算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 循环赛日程表|递推法递推法(迭代法迭代法)n即即2k个选手的比赛日程在个选手的比赛日程在2k-1个选手的比赛日程基础个选手的比赛日程基础上通过迭代完成，每次迭代，将问题分为上通过迭
44、代完成，每次迭代，将问题分为4个部分：个部分：n左上角：左上角：2k-1个选手前半程的比赛日程个选手前半程的比赛日程n左下角：另左下角：另2k-1个选手前半程的比赛日程，由左上角加个选手前半程的比赛日程，由左上角加2k-1得得到到n右上角：将左下角抄到右上角，得到另右上角：将左下角抄到右上角，得到另2k-1个选手后半程的个选手后半程的比赛日程。比赛日程。n右下角：将左上角抄到右下角，得到右下角：将左上角抄到右下角，得到2k-1个选手后半程的比个选手后半程的比赛日程。赛日程。65算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|问题提出问题提出(P59
45、)：n给定由给定由n个整数（可能为负数）组成的序列：个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为均为负数，定义其最大子段和为0。依其定义，所。依其定义，所求的最优值为：求的最优值为：最大子段和问题66算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|1.最大子段和问题的简单算法最大子段和问题的简单算法int MaxSum(int n,int*a,int&besti,int&bestj)int sum=0;for(int i=1;i=n;i+)for(in
46、t j=i;j=n;j+)int thissum=0;for(int k=i;k sum)sum=thissum;besti=i;bestj=j;return sum;显然：显然：T(n)=O(n3)最大子段和问题67算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|2.一点改进一点改进int MaxSum(int n,int an,int&besti,int&bestj)int sum=0;for(int i=1;i=n;i+)int thissum=0;for(int j=i;j sum)sum=thissum;besti=i;bestj=j;r
47、eturn sum;显然：显然：T(n)=O(n2)最大子段和问题68算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳|3.最大子段和问题的分治策略最大子段和问题的分治策略n划分：划分：n按照平衡子问题的原则，将序列按照平衡子问题的原则，将序列(a1,a2,an)划分成划分成长度相同的两个子序列长度相同的两个子序列(a1,an/2)和和(an/21,an)；n求解子问题：求解子问题：n合并合并：n比较在划分阶段的三种情况下的最大子段和，取三者之比较在划分阶段的三种情况下的最大子段和，取三者之中的大者为原问题的解。中的大者为原问题的解。最大子段和问题6
48、9算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 aleft ai acenter acenter+1 aj arightleftsum maxleftsum,sum,rightsum最大子段和问题sumaleft ai acenter acenter+1 aj anrightsum 70算法设计与分析算法设计与分析0?aleft:0;else int center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right)
49、;int s1=0,lefts=0;for(int i=center;i=left;i-)lefts+=ai;if(lefts s1)s1=lefts;/for 最大子段和问题71算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 int s2=0,rights=0;for(int j=center+1;j s2)s2=rights;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;/elsereturn sum;最大子段和问题72算法设计与分析算法设计与分析递归与分治策略递
50、归与分治策略 四川师范大学 计算机科学学院 刘芳 最大子段和问题int MaxSum(int n,int*a)return MaxSubSum(a,1,n);复杂度分析复杂度分析73算法设计与分析算法设计与分析递归与分治策略递归与分治策略 四川师范大学 计算机科学学院 刘芳 最大子段和问题|应用举例：最佳游览路线问题应用举例：最佳游览路线问题n问题描述：问题描述：n某旅游区的街道成网格状。某旅游区的街道成网格状。n其中：其中：p东西向的街道为旅游街，南北向的为林荫道。东西向的街道为旅游街，南北向的为林荫道。p规定旅游街为单行道，旅客只能从西向东走；规定旅游街为单行道，旅客只能从西向东走；p在林