分治与递归课件

第五讲分治与递归第五讲分治与递归引言分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。战术算法设计技术划分——治理——组合引言分治法的设计思想是，将一个难以直接解决的大问题，分割成一将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为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/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)直到问题规模足够小，很容易求出其解为止。可将规模为n的问题分解为多少个规模为n/2的子问题？为什么不一定是两个？nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向问题一：在一个整数组A[1...n]中，同时寻找最大值和最小值例一一个简单例子问题一：在一个整数组A[1...n]中，同时寻找最大值和最小方法一：顺序扫描法S1:min=A[1];max=A[1];S2:扫描数组，对i从2到n做：

S2a:如果A[i]<min，则min=A[i];S2b:如果A[i]>max，则max=A[i];S3:返回x,y的值比较次数：2n-2方法一：顺序扫描法方法二：分治法基本思想：（1）划分：将数组分割成两半（2）治理：在每一半中找到最大值和最小值。（3）合并：返回两个最大值中的最大值和两个最小值中的最小值。方法二：分治法算法1Minmax(intlow,inthigh){ifhigh-low=1then//如果只有两个元素直接解决

ifA[low]<A[high]thenreturn(A[low],A[high])elsereturn(A[high],A[low])endifelse//否则递归解决

mid=(low+high)/2;//将区间一分为二(x1,y1)=minmax(low,mid);//求左半区间的最大最小值(x2,y2)=minmax(mid+1,high);//右半区间的最大最小值x=min{x1,x2};y=max(y1,y2);//求整体最大最小值return(x,y);endif算法1讨论（1）请将以上算法改写为C程序注意：（1）以上算法要求函数同时返回两个值，显然是不符合C语言语法的，请给出你的解决方案（2）C中函数参数的传递是传值传递讨论（1）请将以上算法改写为C程序Minmax(intA[],intlow,inthigh,int*x,int*y){if(high-low==1)if(A[low]<A[high]){*x=A[low];*y=A[high];}else{*x=A[high];*y=A[low]);}else{mid=(low+high)/2;minmax(A,low,mid,&x1,&y1);minmax(A,mid+1,high,&x2,&y2);x=min{x1,x2};y=max(y1,y2);}}Minmax(intA[],intlow,inthig时间复杂度分析：

1若n=2C(n)=2C(n/2)+2若n>2求解递推式得：

C(n)=3n/2-2时间复杂度分析：例二二分搜索问题：在一个有序序列中搜索给定值x，若找到，返回x所在位置，否则返回查找失败标志-1。例二二分搜索问题：在一个有序序列中二分搜索过程midmid查找成功！因A[mid]<22，丢弃A[mid]及其左边所有元素midmid二分搜索过程midmid查找成功！因A[mid]<22，丢弃算法2.1二分搜索的非递归算法intBinarySearch(inta[],intn,intx){intlow=0;high=n-1;while(high>=low){//待搜区间非空

intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功

if(x<a[mid])high=mid-1;elselow=mid+1;}return-1;//查找失败，返回-1}算法2.1二分搜索的非递归算法算法2.2二分搜索的递归算法intBSearch(inta[],intx,intlow,inthigh){if(low>high)return-1//待搜区间为空

else{intmid=(low+high)/2;if(x==a[mid])returnmid;//查找成功

if(x<a[mid])returnBSearch(a,x,low,mid-1);elsereturnBSearch(a,x,mid+1,high);}}算法2.2二分搜索的递归算法二分搜索算法分析时间复杂度分析：

1若n=1C(n)=C()+1若n≥2求解递推式得：

二分搜索算法分析时间复杂度分析：例三合并排序原问题：对A[1...n]排序例三合并排序原问题：对A[1...n]排序先看一个简单问题：

合并两个已排序的表将两个已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。先看一个简单问题：

合并两个已排序200123 44913659776780AB0123 4567Cijk2001210123 44913659776780AB0123 4567Cijk72101220123 44913659776780AB0123 4567Cijk72201230123 44913659776780AB0123 4567Cijk7132301240123 44913659776780AB0123 4567Cijk713492401250123 44913659776780AB0123 4567Cijk713492501260123 44913659776780AB0123 4567Cijk71349652601270123 44913659776780AB0123 4567Cijk71349652701280123 44913659776780AB0123 4567Cijk7134965762801290123 44913659776780AB0123 4567Cijk7134965762901300123 44913659776780AB0123 4567Cijk713496576803001310123 44913659776780AB0123 4567Cijk713496576803101320123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。3201330123 44913659776780AB0123 4567Cijk71349657680至此B表的元素都已移入C表，只需将A表的剩余部分移入C表即可。973301用分治策略——合并排序用分治策略分析：（1）划分：将A[1...n]分为A[1...n/2]A[n/2+1...n]两部分；（2）治理：分别对A[1...n/2]和A[n/2+1...n]排序（3）组合：将两个有序子序列合并为一个有序序列用分治策略——合并排序用分治策略分析：算法3合并排序算法MergeSort(intA[],intn){Msort(A,1,n);}MSort(intA[],intlow,inthigh){if(low<high)//若区间有两个或两个以上元素

{mid=(low+high)/2;//计算划分点

Msort(A,low,mid);//治理左半个区间

Msort(A,mid+1,high);//治理右半个区间

Merge(A,low,mid,high);//组合步骤

}}算法3合并排序算法合并排序算法分析时间复杂度分析：

0若n=1C(n)=2C()+n-1若n≥2求解递推式得：

C(n)=nlogn-n+1合并排序算法分析时间复杂度分析：思考题：求数组的“逆序对”个数Sort公司是一个专门为人们提供排序服务的公司，该公司的宗旨是“顺序是最美丽的”。他们的工作是通过一系列移动，将某些物品按顺序摆好。他们的服务是通过工作量来计算的，即移动东西的次数。所以，在工作前必须先考察工作量，以便向用户提出收费数目。用户并不需要知道精确的移动次数，实际上，大多数人是凭感觉来认定这一列物品的混乱程度。思考题：求数组的“逆序对”个数Sort公司是一个专门为人们提假设我们将序列中第i件物品的参数定义为Ai,那么排序就是指将A1,…,An从小到大排序。若i<j且Ai>Aj，则<i,j>就是一个“逆序对”例如，数组（3，1，4，5，2）的逆序对有<3，1><3，2><4，2><5，2>，共4个。Sort公司请你写一个程序，在尽量短的时间内，统计出“逆序对”的数目。要求时间复杂度O(nlogn)假设我们将序列中第i件物品的参数定义为Ai,那么排序就是指将分治范式（1）划分步骤（2）治理步骤（3）组合步骤分治范式（1）划分步骤分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：因分治法的复杂性分析（1）划分步骤将规模为n的问题分成k个规模为n／m的子问题（2）治理步骤解k个规模为n／m的子问题（3）组合步骤将k个子问题的解合并为原问题的解设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。组合步骤需用f(n)个单位时间。用T(n)表示该分治法解规模为n的问题所需的计算时间，则有：通过迭代法求得方程的解：分治法的复杂性分析（1）划分步骤将规模为n的问题分成k例四快速排序先对序列进行划分，如对如下序列：

13，4，6，19，16，8，5，3，17，21以第一个元素为基准，把比13小的移到它的左边，比13大的移到它的右边

[4，6，8，5，3，]13，[19，16，17，21]先解决一个简单问题——划分算法13已经到位，原问题转化成规模更小的两个子问题！例四快速排序先对序列进行划分，如对如下序列：先解决一个例四快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。voidQuickSort(inta[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序

QuickSort(a,q+1,r);//对右半段排序

}}例四快速排序在快速排序中，记录的比较和交换是从两端向中划分算法初始序列{

,7,5,2,5,8}j--;{5,7,5,2,

,8}i++;{5,

,5,2,7,8}j--;{5,2,5,

,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6{7,8}用x为主元划分数组A后，x将处于一个正确位置j：

x=A[j]既不小于A[low...j-1]中的元素，也不大于A[j+1...high]中的元素划分算法初始序列{,7,5,2,5,8}j--intpartition(inta[],intlow,inthigh){inti=low,j=high;inttemp=a[low];while(i<j){ while(i<j&&a[j]>temp)j--; if(i<j) {a[i]=a[j];i++;} while(i<j&&a[i]<temp)i++; if(i<j) {a[j]=a[i];j--;}}a[i]=temp;returnj;}intpartition(inta[],intlow快速排序

快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)快速排序快速排序算法的性能取决于划分的对称性。通过修例五寻找中项和第k小元素问题：在序列A[1...n]中寻找第k小的元素当k=1,求序列中的最小值；当k=n,求序列中的最大值。简单！Θ(n)其他情况下,如n=100,k=40?方法一：对A[1...n]排序，A[40]即所求。时间复杂度为:Ω(nlogn)寻找一个O(n)的算法！例五寻找中项和第k小元素问题：在序列A[1...n]中寻启发一：受快速排序的启发，先对序列进行划分，如对如下序列找第4小的元素

13，4，6，19，16，8，5，3，17，21以第一个元素为基准，把比13小的移到它的左边，比13大的移到它的右边

[4，6，8，5，3，]13，[19，16，17，21]比13小的有5个元素，那么第4小的元素一定在13的左边，此时，可以丢弃13及13右边的元素。启发一：受快速排序的启发，先对序列进行划分，如对如下序列找第算法6.5区间划分算法partition(inta[],intlow,inthigh){//以a［low］为基准元素，对a[low...high]进行划分inti=low,j=high;temp=a［low］;//取第一个对象为进行调整的标准对象while(i<j){while(i<j&&temp<=a［j］)j--;//在数组的右端扫描if(i<j)a［i++］=a［j］;while(i<j&&a［i］<temp)i++;//在数组的左端扫描if(i<j)a［j--］=a［i］;}a［i］=temp;return(i)}算法6.5区间划分算法方法一：（1）以元素mm为基准，将A[1...n]拆分为三组：并返回基准元素的下标j（2）若j==k,则A[j]即第k小的元素；若j>k,丢弃A[j...n]，在A[1...j-1]中寻找第k小的元素；若j<k,丢弃A[1...j]，在A[j+1...n]中寻找第k-j小的元素；方法一：启发二：如果能在每一个划分步骤后，问题的规模以一个常数因子被减小，则原问题可在O(n)时间内解决。假设算法丢弃1/3并对剩余的2/3部分递归，假定在每次调用中，算法对每个元素耗费的时间不超过常数c，则算法所需的全部时间为：

cn+(2/3)cn+(2/3)2cn+...+(2/3)jcn+...==3cn启发二：如果能在每一个划分步骤后，问题的规模以一个常数因子被分析方法一：（1）在最坏情况下，算法需要O(n2)计算时间（2）若改进算法一，在划分时随机选取一个元素作为基准元素，算法可以在O(n)平均时间内找出n个输入元素中的第k小元素。但在最坏情况下，算法仍需要O(n2)计算时间。我们要找一个字最坏情况下只需O(n)时间的算法。（3）问题的关键是基准元素的选取分析方法一：关键问题：如何选择基准元素？方法一：以区间左端元素为基准元素方法二：随即选取基准元素在最坏情况下，效果极不理想，不能保证问题的规模以一个常数因子被减小关键问题：如何选择基准元素？中项的概念序列A[1...n]的中项是序列中第小的元素若能找到序列的中项，一中项为基准可将序列分成大致相等的两部分，这是最理想的！然而寻找中项是和原问题一样难降低难度：找一个接近中项的元素作为基准元素！中项的概念思路：（1）把n个元素划分成n/5组，每组5个元素；（2）找到每组元素的中项，共有n/5个（3）若（2）中所得元素已较少可直接确定中项做基准元素；否则，递归调用自身，寻找（2）中得到的n/5个元素的基准元素思路：例：在A中找第13小的元素，A中元素：8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7，9,34,18,53,解：（1）分成6组：（8,33,17,51,57）,（49,35,11,25,37）,(14,3,2,13,52）,（12,6,29,32,54）,

（5,16,22,23,7）,(9,34,18,53,58)(2)对每组升序排序（8,17,33,51,57）,（11,25,35,37,49）,(2,3,13,14,52）,（6,12,29,32,54）,

（5,7,16,22,23）,(9,18,34,53,58)例：在A中找第13小的元素，A中元素：8,33,17,51,(3)取每一组的中项元素形成中项集：M={33,35,13,29,16,34}M中元素已较少，可用直接排序法取中项mm=29（4）以29为基准，将A分成3部分A1={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A2={29}j=16A3={33,51,57,49,35,37,52,32,54}因13<16,A2和A3中元素可以丢弃，第13小的元素一定在A1中，重复上述过程。(3)取每一组的中项元素形成中项集：设A=A1,（1）把元素分为3组：（8,17,11,25,14）,（3,2,13,12,6）,（5,16,22,23,7）（2）每组排序后找到新的中项集{14，6，16}，（3）再取其中项14做为新的mm,

（4）将A划分为三个序列A1={8,11,3,2,13,12,6,5,7}A2={14}j=10A3={17,25,16,22,23}因为13>10,丢弃A1和A2，在A3中找第13-10大的元素，算法返回22设A=A1,算法6线性时间选择算法Select(intA[],intn,intk)//在A中寻找第k小的元素

{Slt(A,1,n,k);//在A[1...n]中寻找第k小的元素}算法6线性时间选择算法Slt(intA[],intlow,inthigh,intk){//在A[low...high]中寻找第k小的元素p=high-low+1If(p<44)直接对A排序，返回A[k]令q=p/5,将A分成q组，每组5个元素将q组中的每一组单独排序，找出各组中项，得中项集MMm=Slt(M,1,q,q/2);//mm为中项集的中项Slt(intA[],intlow,inthigh,ij=patition(A,low,high,mm);//以mm为基准划分A[low...high]，j为mm对应下标if(j==k)returnmm//找到第k小的元素if(j>k)Slt(A,low,j-1,k);//丢弃mm及其后元素elseSlt(A,j+1,high,k-j)//丢弃mm及其前元素}j=patition(A,low,high,mm);//以选择算法的分析不论那中情况出现，都至少丢弃个元素剩余元素个数不多于选择算法的分析不论那中情况出现，都至少丢弃Slt(intA[],intlow,inthigh,intk){//在A[low...high]中寻找第k小的元素S1:p=high-low+1S2:If(p<44)直接对A排序，返回A[k]令q=p/5,将A分成q组，每组5个元素S3:将q组中的每一组单独排序，找出各组中项，得中项集M需Θ(n)时间S4:Mm=Slt(M,1,q,q/2);//mm为中项集的中项需时间Slt(intA[],intlow,inthigh,iS5:j=patition(A,low,high,mm);//以mm为基准划分A[low...high]，j为mm对应下标需Θ(n)时间S6:if(j==k)returnmm//找到第k小的元素

if(j>k)Slt(A,low,j-1,k);//丢弃mm及其后元素

elseSlt(A,j+1,high,k-j)//丢弃mm及其前元素需时间

}S5:j=patition(A,low,high,mm选择算法分析时间复杂度分析：

c若n<44T(n)=

若n≥2求解递推式得：

选择算法分析时间复杂度分析：思考题——讨论Sort公司请你写一个程序，在尽量短的时间内，统计出“逆序对”的数目。思考题——讨论方法1——简单搜索法For(i=1ton)for(j=i+1ton){如果a[i]>a[j],计数器加1；

…….}时间复杂度：O(n2)方法1——简单搜索法For(i=1ton)方法2——分治法参考归并排序的思路（1）划分：划分为两个相等子区间；（2）治理：在各区间求逆序对个数（3）合并：将子问题的解合并成原问题的解。决定算法效率的关键在于合并的过程。方法2——分治法参考归并排序的思路分治过程用数组A[low…high]存放当前子序列，

Mid=(low+high)/2设左半区间A[low,…mid]中逆序对个数为num1右半区间A[mid+1,…high]中逆序对个数为num2逆序对的两个数分别取自以上两个半区间的逆序对个数为num3则：数组A[low…high]中逆序对个数为num1+num2+num3问题的关键是求num3分治过程用数组A[low…high]存放当前子序列，Num3的求解num3：xi位于左子区间上，xj为于右半区间上，求xi>xj形成的逆序对<xi,xj>的个数如果摆脱不了搜索思想的影响，仍然用双重循环的话，其时效不会提高，

For(i=low;i<=mid;i++)for(j=mid+1;j<=high;j++){……}这样下来时间复杂度仍是O(n2)这一步必须在线性时间内实现，才能使算法效率象归并排序那样达到O(nlogn).Num3的求解num3：xi位于左子区间上，xj为于右半区合并排序的启发

能否象合并排序中两子序列的合并一样，把两个子区间各扫描一遍即可，这样时间复杂度可达O(nlogn)可以！但要求两个子序列有序！讨论：若左右两个子区间都是有序的，能在线性时间内得到num3吗？合并排序的启发能否象合并排序中两子序列的合1，4，792，3，68一遍扫描可得逆序对个数：3+3+2+1mid=3i=0,j=4:c[1]=a[0]=1i=1,j=4:c[2]==a[4]=2count+=3(4,7,9都与2形成逆序）i=1,j=5:c[3]=a[5]=3count+=3(4,7,9都与3形成逆序）i=1,j=6:c[4]=a[1]=4i=2,j=6:c[5]==a[6]=6count+=2(7,9都与6形成逆序）i=2,j=7:c[6]==a[2]=7i=3,j=7:c[7]=a[7]=8count+=1(9与8形成逆序）排序的同时计算逆序对，同学们可在快速排序程序的基础上改1，4，792，3，68循环赛日程表设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。循环赛日程表设计一个满足以下要求的比赛日程表：按分治策略，将n=2时n=2时n=4时n=4时n=8时n=8时当n不是2的整数幂时，若n为奇数，能在n天内完成循环赛，若n为偶数，能在n-1天内完成循环赛。请给出你的设计方案。讨论（3）不合法！当n不是2的整数幂时，若n为奇数，能在n天内完成循环赛，若n以下是一个合法方案：讨论（3）以下是一个合法方案：讨论（3）棋盘覆盖在一个2k×2k

个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与规模较小的情况n=2规模较小的情况n=2规模较小的情况n=4规模较小的情况n=4规模较小的情况n=4规模较小的情况n=4规模较小的情况n=8规模较小的情况n=8规模较小的情况n=8规模较小的情况n=8规模较大的情况当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1

子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。规模较大的情况当k>0时，将2k×2k棋盘分割为4个2k-1棋盘覆盖voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号

s=size/2;//分割棋盘（1）覆盖左上角子棋盘：若特殊方格在此棋盘中，递归调用自身覆盖该子棋盘否则，此棋盘中无特殊方格，用t号L型骨牌覆盖右下角，再递归调用自身（2）覆盖右上角子棋盘若特殊方格在此棋盘中，递归调用自身覆盖该子棋盘

否则，此棋盘中无特殊方格，用t号L型骨牌覆盖右下角，再递归调用自身（3）覆盖左下角子棋盘

……（4）覆盖右下角子棋盘棋盘覆盖voidchessBoard(inttr,in棋盘覆盖voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++；//L型骨牌号

s=size/2;//分割棋盘

//覆盖左上角子棋盘

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中

chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格，用t号L型骨牌覆盖右下角

board[tr+s-1][tc+s-1]=t;

//覆盖其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}}棋盘覆盖voidchessBoard(inttr,in//覆盖右上角子棋盘

if(dr<tr+s&&dc>=tc+s)

//特殊方格在此棋盘中

chessBoard(tr,tc+s,dr,dc,s);

else

{//此棋盘中无特殊方格

//用t号L型骨牌覆盖左下角

board[tr+s-1][tc+s]=t;

//覆盖其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖右上角子棋盘//覆盖左下角子棋盘

if(dr>=tr+s&&dc<tc+s)

//特殊方格在此棋盘中

chessBoard(tr+s,tc,dr,dc,s);

else

{//用t号L型骨牌覆盖右上角

board[tr+s][tc+s-1]=t;

//覆盖其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}

//覆盖左下角子棋盘//覆盖右下角子棋盘

if(dr>=tr+s&&dc>=tc+s)

//特殊方格在此棋盘中

chessBoard(tr+s,tc+s,dr,dc,s);

else

{//用t号L型骨牌覆盖左上角

board[tr+s][tc+s]=t;

//覆盖其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}//覆盖右下角子棋盘最接近点对问题

设S是平面上n个点的集合，要在S内找到一对点（p,q），使其相互距离最短。蛮力算法：计算所有可能的n(n-1)/2个点对并返回最短间距的点对。时间复杂度：O(n2)本节将运用分治技术描述一个时间复杂度为Θ(nlogn)的算法最接近点对问题设S是平面上n个点的集合，要在S内最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。简单！排序后扫描一遍数组即可！最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得用分治法：（1）划分：我们用x轴上某个点m将S划分为2个子集S1和S2；（2）治理：分别在S1和S2上找出其最接近点对d1=d{p1,p2}和d2=d{q1,q2}，（3）合并：把S1中的点与S2中的点之间的最小距离d’=d{p3,q3}计算出来，最后所求的便是d=min{d1,d2,d}.能否在线性时间内找到p3和q3？用分治法：能否在线性时间内找到p3和q3？能否在线性时间内找到p3和q3如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d.由于在S1中，每个长度为d的半闭区间至多包含一个点