第2章 递归与分治策略PPT讲稿.ppt

《第2章 递归与分治策略PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第2章 递归与分治策略PPT讲稿.ppt（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 递归与分治策略第1页，共30页，编辑于2022年，星期一以以Rk(c)记放记放k个车的不同放法，令个车的不同放法，令R0(c)=1上面的棋盘上面的棋盘C的棋盘多项式等于：的棋盘多项式等于：R(c)=1+n2x+()2x2 n2()2nr+n!xn但是，我们经常碰到的是不完整的棋盘，这类棋盘但是，我们经常碰到的是不完整的棋盘，这类棋盘称残缺棋盘。称残缺棋盘。R（）=1+XR ()=R()=1+2XR ()=1+4X+2X2R()=1+3X+X2R()=1+2X+X2=(1+X)2R()=1+6X+7X2+X3 第2页，共30页，编辑于2022年，星期一下面我们看一些应用：下面我们看一些应

2、用：example:在在a,b,c,d,e的全排列中，要求的全排列中，要求a不出现在不出现在 第第1和第和第5位，位，b不出现在第不出现在第2和第和第3位，位，c不出现在不出现在 第第3和第和第4位，位，e不出现在第不出现在第5位，问：满足这些要位，问：满足这些要 求的全排列有多少？求的全排列有多少？如果用一般方法：过程复杂如果用一般方法：过程复杂 结果为结果为25。下面让我们来用棋盘多项式的方法来求解。下面让我们来用棋盘多项式的方法来求解。第3页，共30页，编辑于2022年，星期一example:在在a,b,c,d,e的全排列中，要求的全排列中，要求a不出现在第不出现在第1和第和第5位，位，

3、b不出现在第不出现在第2和第和第3位，位，c不出现在第不出现在第3和第和第4位，位，e不出不出现在第现在第5位，问：满足这些要求的全排列有多少？位，问：满足这些要求的全排列有多少？1 2 3 4 5 a b c d e建立残缺棋盘在建立残缺棋盘在5*5的棋盘中，在被禁的棋盘中，在被禁止的小方格中用止的小方格中用红红色色填充，不难看出填充，不难看出它由两个正交的子它由两个正交的子图组成：图组成：（1+3X+X2)（1+4X+3X2)正交的相乘正交的相乘第4页，共30页，编辑于2022年，星期一R（C）=（1+3X+X2）*（1+4X+3X2）=1+7X+16X2+13X3+3X4对照得到：对照得

4、到：B（0）=5！-7*4！+16*3！-13*2！+3*1！+0 =25这是简单的棋盘多项式能解决的问题，如果这是简单的棋盘多项式能解决的问题，如果有不正交的情况，我们主要采用下面的方法有不正交的情况，我们主要采用下面的方法进行构造。进行构造。第5页，共30页，编辑于2022年，星期一Exm.小孩给他的三个叔叔小孩给他的三个叔叔u1,u2,u3和三个婶婶和三个婶婶 a1,a2,a3送送6张不同的贺卡张不同的贺卡c1,c2,c3,c4,c5,c6,他他 知道知道u2不喜欢不喜欢c1,u1和和a1不喜欢不喜欢c2，u1和和a2不不喜欢喜欢c4，u2和和a1不喜欢不喜欢c5，a3不喜欢不喜欢c6，

5、问问他要让大家都满意，有多少不同的寄法？他要让大家都满意，有多少不同的寄法？u1 u2 u3 a1 a2 a3 c1 c2 c3 c4 c5 c6经行列变换可得经行列变换可得*a第6页，共30页，编辑于2022年，星期一*a*Ca Ca C R(Ca)=(1+x)(1+3x+x2)2R(Ca)=(1+x)(1+2x)2R(C)=(1+x)(1+3x+x2)2+x(1+x)(1+2x)2 =1+8x+22x2+25x3+11x4+x5B(0)=6!-8*5!+22*4!-25*3!+11*2!-1!=159 第7页，共30页，编辑于2022年，星期一2.9 线性时间选择给定线性序集中给定线性序集

6、中n个元素和一个整数个元素和一个整数k，1kn，要求找出这要求找出这n个元素中第个元素中第k小的元素小的元素.templateType RandomizedSelect(Type a,int p,int r,int k)if(p=r)return ap;int i=RandomizedPartition(a,p,r),j=i-p+1;if(k=j)return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);在最坏情况下，算法在最坏情况下，算法randomizedSelect需要需要O(n2)计算时计算时间

7、间但可以证明，算法但可以证明，算法randomizedSelect可以在可以在O(n)平均时平均时间内找出间内找出n个输入元素中的第个输入元素中的第k小元素。小元素。如果将这如果将这n个元素依其线性序排列时个元素依其线性序排列时，排在第排在第k个个位置的元素即为我们要找的元素。位置的元素即为我们要找的元素。第8页，共30页，编辑于2022年，星期一如果能在线性时间内找到一个划分基准，使得按这个如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的基准所划分出的2个子数组的长度都至少为原数组长度个子数组的长度都至少为原数组长度的的倍倍(01是某个正常数是某个正常数)，那么就可以，那么就可以

8、在最坏情在最坏情况下况下用用O(n)时间完成选择任务。时间完成选择任务。例如，若例如，若=9/10，算法递归调用所产生的子算法递归调用所产生的子数组的长度至少缩短数组的长度至少缩短1/10。所以，在最坏情。所以，在最坏情况下，算法所需的计算时间况下，算法所需的计算时间T(n)满足递归式满足递归式T(n)T(9n/10)+O(n)。由此可得由此可得T(n)=O(n)。第9页，共30页，编辑于2022年，星期一我们可以按以下步骤来寻找一个好的划分基准：我们可以按以下步骤来寻找一个好的划分基准：l将将n个输入元素划分成个输入元素划分成 n/5 个组，每组个组，每组5个元素，个元素，只可能有一个组不是

9、只可能有一个组不是5个元素。用任意一种排序算法，个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共将每组中的元素排好序，并取出每组的中位数，共 n/5 个。个。l递归调用递归调用select来找出这来找出这 n/5 个元素的中位数。如果个元素的中位数。如果 n/5 是偶数，就找它的是偶数，就找它的2个中位数中较大的一个。以这个中位数中较大的一个。以这个元素作为划分基准。个元素作为划分基准。第10页，共30页，编辑于2022年，星期一 设所有元素互不相同。在这种情况下，找出设所有元素互不相同。在这种情况下，找出的基准的基准x至少比至少比3(n-5)/10个元素大，因为在每一

10、个元素大，因为在每一组中有组中有2个元素小于本组的中位数，而个元素小于本组的中位数，而n/5个中位个中位数中又有数中又有(n-5)/10个小于基准个小于基准x。同理，基准同理，基准x也也至少比至少比3(n-5)/10个元素小。而当个元素小。而当n75时，时，3(n-5)/10n/4所以按此基准划分所得的所以按此基准划分所得的2个子数组的长个子数组的长度都至少缩短度都至少缩短1/4。第11页，共30页，编辑于2022年，星期一Type Select(Type a,int p,int r,int k)if(r-p75)用某个简单排序算法对数组用某个简单排序算法对数组ap:r排序排序;return

11、ap+k-1;for(int i=0;i=(r-p-4)/5;i+)将将ap+5*i至至ap+5*i+4的第的第3小元素小元素 与与ap+i交换位置交换位置;/找中位数的中位数，找中位数的中位数，r-p-4即上面所说的即上面所说的n-5 Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i=Partition(a,p,r,x),j=i-p+1;if(k=j)return Select(a,p,i,k);else return Select(a,i+1,r,k-j);第12页，共30页，编辑于2022年，星期一复杂度分析复杂度分析T(n)=O(n)上述算

12、法将每一组的大小定为上述算法将每一组的大小定为5，并选取，并选取75作为是否作递归作为是否作递归调用的分界点。这调用的分界点。这2点保证了点保证了T(n)的递归式中的递归式中2个自变量个自变量之和之和n/5+3n/4=19n/20=n，01。这是使这是使T(n)=O(n)的关键之处。当然，除了的关键之处。当然，除了5和和75之外，还有之外，还有其他选择。其他选择。第13页，共30页，编辑于2022年，星期一2.10 最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。u为了使问题易于理解和分析，先来考虑一维的情形。此时，为了使问题易于理解和

13、分析，先来考虑一维的情形。此时，S中的中的n个点退化为个点退化为x轴上的轴上的n个实数个实数 x1,x2,xn。最接近最接近点对即为这点对即为这n个实数中相差最小的个实数中相差最小的2个实数。个实数。假设我们用假设我们用x轴上某个点轴上某个点m将将S划分为划分为2个子集个子集S1和和S2，基基于于平衡子问题平衡子问题的思想，用的思想，用S中各点坐标的中位数来作分割点。中各点坐标的中位数来作分割点。递归地在递归地在S1和和S2上找出其最接近点对上找出其最接近点对p1,p2和和q1,q2，并设并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是中的最接近点对或者是p1,p2，或者是

14、或者是q1,q2，或者是某个或者是某个p3,q3，其中其中p3 S1且且q3 S2。能否在线性时间内找到能否在线性时间内找到p3,q3？第14页，共30页，编辑于2022年，星期一u如果如果S的最接近点对是的最接近点对是p3,q3，即即|p3-q3|d，则则p3和和q3两者与两者与m的的距离不超过距离不超过d，即，即p3(m-d,m，q3(m,m+d。u由于在由于在S1中，每个长度为中，每个长度为d的半闭区间至多包含一个点（否则必有两的半闭区间至多包含一个点（否则必有两点距离小于点距离小于d），），并且并且m是是S1和和S2的分割点，因此的分割点，因此(m-d,m中至多包中至多包含含S中的一个

15、点。由图可以看出，如果中的一个点。由图可以看出，如果(m-d,m中有中有S中的点，则此点中的点，则此点就是就是S1中最大点。中最大点。u因此，我们用线性时间就能找到区间因此，我们用线性时间就能找到区间(m-d,m和和(m,m+d中所有中所有点，即点，即p3和和q3。从而我们用线性时间就可以将从而我们用线性时间就可以将S1的解和的解和S2的解合的解合并成为并成为S的解。的解。能否在线性时间内找到能否在线性时间内找到p3,q3？第15页，共30页，编辑于2022年，星期一u下面来考虑二维的情形。下面来考虑二维的情形。选取一垂直线选取一垂直线l:x=m来作为分割直线。其中来作为分割直线。其中m为为S

16、中各点中各点x坐标的中位数。由此将坐标的中位数。由此将S分割为分割为S1和和S2。递归地在递归地在S1和和S2上找出其最小距离上找出其最小距离d1和和d2，并设并设d=mind1,d2，S中的最接近点对或者是中的最接近点对或者是d，或者是某个或者是某个p,q，其中其中p P1且且q P2。能否在线性时间内找到能否在线性时间内找到p,q？第16页，共30页，编辑于2022年，星期一能否在线性时间内找到能否在线性时间内找到p3,q3？u考虑考虑P1中任意一点中任意一点p，它若与它若与P2中的点中的点q构成最接近点对的候选者，构成最接近点对的候选者，则必有则必有distance(p，q)d。满足这满

17、足这个条件的个条件的P2中的点一定落在一个中的点一定落在一个d2d的矩形的矩形R中中u由由d的意义可知，的意义可知，P2中任何中任何2个个S中的点的距离都不小于中的点的距离都不小于d。由此可以由此可以推出矩形推出矩形R中最多只有中最多只有6个个S中的点。中的点。u因此，在分治法的合并步骤中最因此，在分治法的合并步骤中最多只需要检查多只需要检查6n/2=3n个候选者个候选者第17页，共30页，编辑于2022年，星期一证明证明:将矩形将矩形R的长为的长为2d的的边边3等分，将它的长为等分，将它的长为d的的边边2等分，由此导出等分，由此导出6个个(d/2)(2d/3)的矩形。若矩的矩形。若矩形形R中

18、有多于中有多于6个个S中的点，中的点，则由鸽舍原理易知至少有一则由鸽舍原理易知至少有一个个(d/2)(2d/3)的小矩形中的小矩形中有有2个以上个以上S中的点。设中的点。设u，v是位于同一小矩形中的是位于同一小矩形中的2个点，则个点，则distance(u,v)d。这与这与d的意义相矛盾。的意义相矛盾。第18页，共30页，编辑于2022年，星期一为了确切地知道要检查哪为了确切地知道要检查哪6个点，可以将个点，可以将p和和P2中所有中所有S2的点投影到垂直线的点投影到垂直线l上。由于能与上。由于能与p点一起构成最接近点对候选者的点一起构成最接近点对候选者的S2中点一定在矩中点一定在矩形形R中，所

19、以它们在直线中，所以它们在直线l上的投影点距上的投影点距p在在l上投上投影点的距离小于影点的距离小于d。由上面的分析可知，这种投影由上面的分析可知，这种投影点最多只有点最多只有6个。个。因此，若将因此，若将P1和和P2中所有中所有S中点按其中点按其y坐标排好坐标排好序，则对序，则对P1中所有点，对排好序的点列作一次扫中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查中每一点最多只要检查P2中排好序的相继中排好序的相继6个点。个点。第19页，共30页，编辑于2022年，星期一*鸽舍原理（也称抽屉原理）鸽舍原理（

20、也称抽屉原理）首先让我们先看一下抽屉原理的定理：首先让我们先看一下抽屉原理的定理：定理：定理：把把n+1个球，放入个球，放入n个抽屉，则一定有一个个抽屉，则一定有一个抽屉内至少有抽屉内至少有2个球。个球。（抽屉原理用途广泛，下面我们举几个例子来认识一下）（抽屉原理用途广泛，下面我们举几个例子来认识一下）（抽屉原理应用中的难点是抽屉原理应用中的难点是怎样构造抽屉？怎样构造抽屉？）例例1：任意的：任意的367个人，证明至少有个人，证明至少有2个人同一天出生。个人同一天出生。这时抽屉是这时抽屉是365或或366。第20页，共30页，编辑于2022年，星期一例例2：有边长为：有边长为1的正方形，任意在

21、内部给的正方形，任意在内部给5个点，个点，证明其中一定有证明其中一定有2个点的距离个点的距离=2/2。分析：此题有分析：此题有5个点，若能分成个点，若能分成4个抽屉即可。个抽屉即可。11/22/2抽屉构造完，命抽屉构造完，命题得证。题得证。第21页，共30页，编辑于2022年，星期一例例3：用：用2种不同的颜色给种不同的颜色给3*9的棋盘小格子染色，的棋盘小格子染色，证明：无论怎么染，一定有证明：无论怎么染，一定有2列上对应的小格子列上对应的小格子染的色相同。染的色相同。证：证：3*9的棋盘的每列有的棋盘的每列有3个小格，个小格，2种颜色染这种颜色染这3个小格个小格 共有共有23=8种不同的染

22、法，种不同的染法，现在有现在有9列，列，一定有一定有2列的染法完全相同。列的染法完全相同。第22页，共30页，编辑于2022年，星期一例例4：往一个边长为：往一个边长为1的等边三角形内任意放的等边三角形内任意放5个点，个点，证明：一定有证明：一定有2个点的距离小于等于个点的距离小于等于1/2。证：用等边三角形的中点的连线证：用等边三角形的中点的连线把它分成四个小等边三角形，把它分成四个小等边三角形，边长是边长是1/2。5个点无论怎么放，一定会至少有个点无论怎么放，一定会至少有 2个点落在同一个小三角形内，此个点落在同一个小三角形内，此2点的距离不大于点的距离不大于1/2。第23页，共30页，编

23、辑于2022年，星期一例例5：任取：任取m个整数，证明其中一定有个整数，证明其中一定有若干个它们若干个它们的和能够被的和能够被m整除整除。证明：令证明：令a1,a2am 为任取的为任取的m个整数。个整数。设，设，S1=a1 S2=a1+a2 Si=a1+a2+ai;i=1,2,m再令再令Si（mod m)=ri 表示一个数除表示一个数除m 的余数为的余数为ri则则 0=rim 即即 0=r1,r2,rm=m-1从从ri到到rm有有m 个数，从个数，从0到到m-1有有m个数，个数，不能用原理。不能用原理。第24页，共30页，编辑于2022年，星期一讨论：若讨论：若rj=0 则表示则表示sj能被能

24、被m整除，命题得证；整除，命题得证；若若rj=0 则存在则存在 0r1,r2,rm=m-1 所以，根据抽屉原理其中一定存在所以，根据抽屉原理其中一定存在 rs=rt 满足（满足（st)这两个余数可以表示为：这两个余数可以表示为：a1+a2+as=a1+a2+as+at(mod m)即即as+1+at=0(mod m)即即St-Ss 能被能被m整除整除第25页，共30页，编辑于2022年，星期一例例6：任意：任意n个人集会，证明：其中必有个人集会，证明：其中必有2个人个人他们在与会的人中有同样数目的朋友，（此时他们在与会的人中有同样数目的朋友，（此时有一个约定，两个人为互相认识，或互相不认识）有

25、一个约定，两个人为互相认识，或互相不认识）证：令证：令ni表示表示i个人认识的人数个人认识的人数 i=1,2,3,n 则则 0=ni=n-1 此时此时ni为为n个个（表面上看对于抽屉数是（表面上看对于抽屉数是0到到n-1，实际上让实际上让我们来进一步分析一下）我们来进一步分析一下）注意到如果有一个注意到如果有一个ni=0（他谁也不认识）他谁也不认识）那么一定存在一个那么一定存在一个nj0(即表示即表示nj不能谁也不认识）不能谁也不认识）综上，综上，n1,n2,nn 落在落在0，1，2，n-2)或或1，2，n-1中，前者为中，前者为n个数，后面集合为个数，后面集合为n-1个数，必有个数，必有ni

26、=nj 。命题得证命题得证第26页，共30页，编辑于2022年，星期一double cpair2(S)n=|S|;if(n 2)return;1、m=S中各点中各点x间坐标的中位数间坐标的中位数;构造构造S1和和S2；/S1=p S|x(p)m2、d1=cpair2(S1);d2=cpair2(S2);3、dm=min(d1,d2);第27页，共30页，编辑于2022年，星期一4、设、设P1是是S1中距垂直分割线中距垂直分割线l的距离在的距离在dm之内的所有点组成之内的所有点组成的集合；的集合；P2是是S2中距分割线中距分割线l的距离在的距离在dm之内所有点组成的集合；之内所有点组成的集合；将

27、将P1和和P2中点依其中点依其y坐标值排序；坐标值排序；并设并设X和和Y是相应的已排好序的点列；是相应的已排好序的点列；5、通过扫描、通过扫描X以及对于以及对于X中每个点检查中每个点检查Y中与其距离在中与其距离在dm之之内的所有点内的所有点(最多最多6个个)可以完成合并；可以完成合并；当当X中的扫描指针逐次向上移动时，中的扫描指针逐次向上移动时，Y中的扫描指针可在中的扫描指针可在宽为宽为2dm的区间内移动；的区间内移动；设设dl是按这种扫描方式找到的点对间的最小距离；是按这种扫描方式找到的点对间的最小距离；6、d=min(dm,dl);return d;复杂度分析复杂度分析T(n)=O(nlo

28、gn)第28页，共30页，编辑于2022年，星期一2.11循环赛日程表设计一个满足以下要求的比赛日程表：设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，按分治策略，将所有的选手分为两半，n个选手的比赛个选手的比赛日程表就可以通过为日程表就可以通过为n/2个选手设计的比赛日程表个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时个选手时，比赛日程表的制定就变得很简单。这时只要让这只要让这2个选手进行比赛就可以了。个选手进行比赛就可以了。第29页，共30页，编辑于2022年，星期一1234567821436587341278564321876556781234658721437856341287654321第30页，共30页，编辑于2022年，星期一