算法設(shè)計(jì)與分析 課件 許瑾晨 第四章 分治法

算法設(shè)計(jì)與分析算法設(shè)計(jì)-分治信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版一二三算法引例算法基本思想分治法解題步驟分治法適用條件分治法代碼框架典型應(yīng)用二分搜索快速排序歸并排序棋盤(pán)覆蓋大整數(shù)乘尋找假幣尋找金塊重點(diǎn)掌握：1.算法的基本思想2.平衡劃分原則

3.分治法的優(yōu)化方法算法設(shè)計(jì)與分析分治引例-尋找假幣信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版已知條件：一個(gè)裝有16枚硬幣的袋子，其中有一枚硬幣是偽造的，并且偽造的硬幣比真的硬幣要輕一些。工具：一臺(tái)天枰，可用來(lái)比較兩組硬幣的重量。問(wèn)題：找出這枚偽造的硬幣。方法一任意取1枚硬幣，與其它硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，則輕者為假幣。最多可能有15次比較。123456789101112131415方法二將硬幣分為8組，每組2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為假幣。最多可能有8次比較。12345678方法三第1組第2組1次比較第1組第2組1次比較第1組第2組1次比較第1組第2組1次比較共4次比較每次將待比較硬幣分為相等兩組，共4輪比較。算法分析與比較上述三種方法，分別需要比較15次，8次，4次。比較次數(shù)差異的根本原因是什么?方法1：每枚硬幣都至少進(jìn)行了一次比較，而有一枚硬幣進(jìn)行了15次比較。方法2：每一枚硬幣只進(jìn)行了一次比較。方法3：一次比較可以將硬幣的范圍縮小到原來(lái)的一半，充分利用了只有1枚假幣的基本性質(zhì)。方法四第1組第2組1次比較第1組第2組1次比較第3組共3次比較不等相等1次比較1次比較首輪采取平分，第二輪采取三分法。測(cè)試選擇題：現(xiàn)有24個(gè)硬幣，其中有1個(gè)硬幣是假幣（重量更輕），利用一個(gè)天枰，在最壞情況下，最少需要（）次比較。A：3B：4C：5D：6方法二8方法三4方法四3分治法的主要內(nèi)容之一：如何實(shí)現(xiàn)更好的問(wèn)題劃分比較次數(shù)算法設(shè)計(jì)與分析分治引例-尋找金塊信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版已知條件：某老板有一袋金塊。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。工具：一臺(tái)天枰，可用來(lái)比較金塊的重量。問(wèn)題：用最少的比較次數(shù)找出最輕和最重的金塊。方法一假設(shè)袋中有n個(gè)金塊：

先找最重的金塊：n-1次比較

再找最輕的金塊：n-2次比較方法一算法描述：max:=a[1];fori:=2tondo//n-1次比較，找n個(gè)元素中最大ifa[i]>maxthenbegin max:=a[i];j:=i;end;fori:=j+1tondoa[i-1]:=a[i];//去掉最大的數(shù)a[j]min:=a[1];fori:=2ton-1do//n-2次比較，找剩下元素中最小ifa[i]<minthenbegin min:=a[i];方法二n≤2，找出最重和最輕的金塊，一次比較；n＞2step1:把金塊平分成兩個(gè)小袋A和B；step2:分別找出在A和B中最重和最輕的金塊（HA與LA、HB和LB分別表示A和B中最重和最輕的金塊）；step3:比較HA和HB找到最重的金塊；比較LA和LB找到最輕的金塊。

step2中，若n>2，則遞歸的繼續(xù)平分為兩部分。方法二10，8，2，4，5，3，9，110，8，2，45，3，9，110，82，45，39，1方法二10，82，45，39，1第一輪比較4次比較10，42，85，93，1第二輪比較4次比較10，29，110，92，1第三輪比較10，12次比較共10次比較算法分析當(dāng)有8個(gè)金塊的時(shí)候，方法1需要比較15次，方法2只需要比較10次。比較次數(shù)差異的根本原因是什么?方法2：對(duì)金塊實(shí)行了分組比較。對(duì)于n(n是2的次冪)枚金塊，比較次數(shù)c(n)：

方法1：c(n)=(n-1)+(n-2)=2n-3

方法2：c(n)=2c(n/2)+2,c(2)=1,=3n/2-2淘汰賽法思想：先按淘汰賽法找出最大項(xiàng)；再在首輪敗者中（包括首輪未參加比較的項(xiàng)）找出最小項(xiàng)。方法三1.找出最大項(xiàng)需要n-1次比較2.參加找“最小”的項(xiàng)數(shù)至多有

n/2

個(gè)，故可用

n/2-1次比較找到最小項(xiàng)。共：n-1+n/2-1=3n/2-2次比較?！径ɡ怼浚河帽容^算法類(lèi)中的任一算法，找出n項(xiàng)表中的最大項(xiàng)和最小項(xiàng)，在最壞情況下，至少要比較3n/2-2次。結(jié)論：解決該問(wèn)題的淘汰賽法、分治法，在最壞情況下的比較次數(shù)都是3n/2-2

。故它們?cè)谧顗那闆r下都是最優(yōu)的。

測(cè)試

算法設(shè)計(jì)與分析分治法-基本思想信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版尋找假幣和金塊問(wèn)題的共同點(diǎn)把問(wèn)題分解為規(guī)模更小的問(wèn)題求解小規(guī)模問(wèn)題得到原問(wèn)題的解

算法策略：分而治之總體思想適用條件代碼框架一二三T(n)將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。對(duì)k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。T(n/m)T(n/m)T(n/m)T(n/m)………………………………邊界和遞歸式T(n)將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。T(n/m)T(n/m)T(n/m)T(n/m)………………………………分治法的思想：將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。分治就是“分而治之”，實(shí)質(zhì)是將原問(wèn)題分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，然后遞歸地解這些子問(wèn)題，最后合并其結(jié)果就得到原問(wèn)題的解。子問(wèn)題求解(conquer)問(wèn)題S問(wèn)題S1……問(wèn)題S2問(wèn)題Sn問(wèn)題SiS1的解……S2的解Sn的解Si的解S的解問(wèn)題的分解(divide)子問(wèn)題解的合并(combine)選擇題分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問(wèn)題分割成規(guī)模較小的子問(wèn)題，分別解決子問(wèn)題，最后將子問(wèn)題的解組合起來(lái)形成原問(wèn)題的解，要求原問(wèn)題和子問(wèn)題的問(wèn)題規(guī)模

，問(wèn)題性質(zhì)

。A：相同，相同B：相同，不同C：不同，相同D：不同，不同測(cè)試分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題；利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問(wèn)題

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//遞歸求解各子問(wèn)題

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

//將子問(wèn)題的解合并為原問(wèn)題的解

returnmerge(y1,...,yk);}分治法設(shè)計(jì)的平衡原則：使子問(wèn)題的規(guī)模大致相同測(cè)試：博彩詐騙為什么可以成功背景設(shè)定你是一位足球迷，當(dāng)前正在進(jìn)行某個(gè)足球賽事，你在看球的同時(shí)想娛樂(lè)一下，參與一下博彩事業(yè)，當(dāng)前正在進(jìn)行16進(jìn)8的比賽，你想買(mǎi)張彩票，正在你準(zhǔn)備下注時(shí)，收到了一個(gè)信息。選擇題：1信息中說(shuō)：A隊(duì)肯定會(huì)在這場(chǎng)比賽中獲勝，此時(shí)你會(huì)相信嗎？A：不信 B：信 C：半信半疑無(wú)論你信不信，你買(mǎi)了A隊(duì)勝，此后，當(dāng)A和C比賽時(shí)，你又收到了信息2信息中說(shuō)：C隊(duì)肯定會(huì)在這場(chǎng)比賽中獲勝，此時(shí)你會(huì)相信嗎？A：不信 B：信 C：半信半疑無(wú)論你信不信，你買(mǎi)了C隊(duì)勝，此后，當(dāng)C和E比賽時(shí)，你又收到了信息3信息中說(shuō)：C隊(duì)肯定會(huì)在這場(chǎng)比賽中獲勝，此時(shí)你會(huì)相信嗎？A：不信 B：信 C：半信半疑你買(mǎi)了C隊(duì)勝，決賽時(shí)，你又收到了信息4要想知道比賽結(jié)果，需要付費(fèi)查看，此時(shí)你會(huì)付費(fèi)嗎?A：會(huì)

B：不會(huì)選擇：ACB

A學(xué)以致用才是學(xué)習(xí)的最終目的，日常中的各種現(xiàn)象，都可能被解釋?zhuān)饕创蠹业乃季S方式，做任何事我們都要用正確的思維方式。算法設(shè)計(jì)與分析分治—二分搜索信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版問(wèn)題描述：給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。算法思想：比較x和a[mid]，若x==a[mid]，則x在L中的位置就是mid；若x<a[mid]，在a[mid]的前面查找x；若x>a[mid]，在a[mid]的后面查找x。算法思想：x與中間位置的元素進(jìn)行比較，相等則查找成功；否則，如果x較小，繼續(xù)在左邊的有序區(qū)中二分搜索；如果x較大，則繼續(xù)在右邊的有序區(qū)中二分搜索，直到有序區(qū)中沒(méi)有元素。代碼4-2：二分搜索的遞歸實(shí)現(xiàn)defBinarySearch(a,x,h,r):#在數(shù)組a[h]到a[r]中搜索元素xifr>=h:m=(h+r)//2#將數(shù)列二分，并向下取整

ifx==a[m]:#遞歸出口

returnmifx<a[m]:r=m-1#如果右邊一半第一個(gè)元素比x大，只搜索左邊一半，更新右端點(diǎn)

else:h=m+1#如果左邊一半最后一個(gè)元素比x大，只搜索右邊一半，更新左端點(diǎn)

returnBinarySearch(a,x,h,r)#遞歸

else:return-1if__name__=='__main__':n=int(input())x=int(input())a=list(map(int,list(input().split())))#將list中空格去掉并將str類(lèi)型轉(zhuǎn)為int類(lèi)型

print(BinarySearch(a,x,0,n-1))以比較操作為基本操作的算法類(lèi)中，搜索有序表給定元素的問(wèn)題。二分搜索算法在平均、最壞情況下都是最優(yōu)算法。時(shí)間復(fù)雜度分析最好情況

x在中間位置出現(xiàn)，只需要1次比較。最壞情況平均情況

按比較次數(shù)為1、2、3…、1+logn，把2n+1種輸入分類(lèi)。求解得A(n)=Θ(logn)。W(n)=1+W(n/2)W(1)=1利用主定理第二條，求解得W(n)=Θ(logn)測(cè)試選擇題：在二分搜索的遞歸實(shí)現(xiàn)中，最壞情況下的遞推式為（）A：W(n)=1+W(n/2)B：W(n)=1+W(n-1)C：W(n)=n+W(n/2)D：W(n)=n+W(n-1)算法設(shè)計(jì)與分析分治—二分搜索—平均時(shí)間復(fù)雜度分析信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版平均時(shí)間復(fù)雜度分析分析輸入種類(lèi)n+(n+1)=2n+1In+1In+2In+3In+n+1In+n確定每種輸入出現(xiàn)的概率假定每種輸入出現(xiàn)的概率相等（這是平均時(shí)間復(fù)雜度分析的通常做法）I1I2I3I4I5InIn-1……平均時(shí)間復(fù)雜度分析確定不同輸入需要的基本操作次數(shù)1次比較2次比較3次比較4次比較5次比較

5次比較平均時(shí)間復(fù)雜度分析確定不同輸入需要的基本操作次數(shù)

令St為需要比較t次的輸入種類(lèi)，有S1=1，S2=2，S3=4，S4=8，S5=48

平均時(shí)間復(fù)雜度分析根據(jù)公式計(jì)算并化簡(jiǎn)

測(cè)試

算法設(shè)計(jì)與分析分治—快速排序信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版基本思想：在數(shù)組中任選一個(gè)元素作為基準(zhǔn)元素，用它和其他每

個(gè)元素比較，小于基準(zhǔn)的放在它左邊，大于等于基準(zhǔn)

的放在它右邊。分別對(duì)基準(zhǔn)的左右兩個(gè)無(wú)序區(qū)進(jìn)行快速排序，直到無(wú)

序區(qū)只有一個(gè)元素。分治defQuickSort(a,p,r):#對(duì)a[p]到a[r]的快速排序

ifp<r:q=Partition(a,p,r)#劃分函數(shù)，劃分位置

QuickSort(a,p,q-1)#對(duì)左半端快速排序

QuickSort(a,q+1,r)#對(duì)右半段快速排序代碼4-5：快速排序的一次劃分過(guò)程defPartition(a,p,r):i=p#左端的哨兵j=r+1#右端的哨兵x=a[p]#選擇最左端元素為基準(zhǔn)元素whileTrue:i+=1whilea[i]<xandi<=r:i+=1j-=1whilea[j]>x:j-=1ifi>=j:breaka[i],a[j]=a[j],a[i]

a[p]=a[j]a[j]=xreturnj代碼4-5：快速排序的一次劃分過(guò)程defPartition(a,p,r):i=p#左端的哨兵j=r+1#右端的哨兵x=a[p]#選擇最左端元素為基準(zhǔn)元素whileTrue:i+=1whilea[i]<xandi<=r:i+=1j-=1whilea[j]>x:j-=1ifi>=j:breaka[i],a[j]=a[j],a[i]

a[p]=a[j]a[j]=xreturnj時(shí)間復(fù)雜度分析最好情況

T(n)=2T(n/2)+n-1T(2)=1

應(yīng)用主定理第二條，T(n)=Θ(nlogn)最壞情況

W(n)=W(n-1)+n-1W(1)=1W(n)=O(n2)時(shí)間復(fù)雜度分析平均情況

問(wèn)題的n!個(gè)輸入被分成了n個(gè)子類(lèi)：

一類(lèi)是基準(zhǔn)項(xiàng)x在位置1；

一類(lèi)是基準(zhǔn)項(xiàng)x在位置2； ……

一類(lèi)是基準(zhǔn)項(xiàng)x在位置n。假定：i取1,2,…,n的可能性相等

時(shí)間復(fù)雜度分析平均情況

差消迭代法

直接迭代法

lnn=ln2lognA(n)=O(nlogn)以比較操作為基本操作的算法類(lèi)中，求解排序問(wèn)題?？焖倥判蛩惴ㄔ谄骄闆r下是最優(yōu)算法。時(shí)間復(fù)雜度分析最好情況

T(n)=2T(n/2)+n-1T(2)=1T(n)=Θ(nlogn)最壞情況平均情況

W(n)=W(n-1)+n-1W(1)=1W(n)=Θ(n2)A(n)=O(nlogn)最好情況

T(n)=2T(n/2)+n-1T(2)=1T(n)=Θ(nlogn)最壞情況平均情況

測(cè)試

算法設(shè)計(jì)與分析分治—?dú)w并排序信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。voidMergeSort(int*a,intleft,intright){if(left<right){//至少有2個(gè)元素

inti=(left+right)/2;//取中點(diǎn)

mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合并到數(shù)組bcopy(a,b,left,right);//復(fù)制回?cái)?shù)組a}}復(fù)雜度分析T(n)=O(nlogn)漸近意義下的最優(yōu)算法算法mergeSort的遞歸過(guò)程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]基本思想：基本思想：將待排序元素R[0]到R[n-1]看成n個(gè)長(zhǎng)度為1的數(shù)組，把這些數(shù)組兩兩歸并，得到

n/2

個(gè)有序的數(shù)組。然后，再把這

n/2

個(gè)數(shù)組兩兩歸并，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的數(shù)組為止。defMergeSort(R,n):#對(duì)長(zhǎng)度為n的數(shù)組R進(jìn)行排序

length=1R1=[None]R1=R1*nwhilelength<n:MergePass(R,R1,length,n)length*=2MergePass(R1,R,length,n)length*=2#一趟兩兩歸并defMergePass(R,R1,length,n):#length是本趟歸并有序數(shù)組長(zhǎng)度，

i=0whilei+2*length-1<n:#循環(huán)條件為右端點(diǎn)不越界

Merge(R,R1,i,i+length-1,i+2*length-1)i=i+2*length#更新iifi+length-1<n-1:#當(dāng)右端點(diǎn)越界，但是右半段仍有數(shù)需要合并

Merge(R,R1,i,i+length-1,n-1)else:#其他情況

forjinrange(i,n):R1[j]=R[j]MergePass對(duì)數(shù)組元素做一趟合并歸并排序：治、合。Merge:時(shí)間復(fù)雜度分析最壞情況平均情況

W(n)=A(n)=O(nlogn)歸并排序比較操作算法類(lèi)中的最優(yōu)算法測(cè)試

判斷題：對(duì)于歸并排序算法，算法的平均時(shí)間復(fù)雜度A(n)和最壞時(shí)間復(fù)雜度W(n)的關(guān)系是（）A:A(n)>W(n)B:W(n)>A(n)C:A(n)=W(n)算法設(shè)計(jì)與分析分治—棋盤(pán)覆蓋信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版問(wèn)題描述解題思路算法設(shè)計(jì)一二三問(wèn)題描述：在一個(gè)2k×2k個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱(chēng)該方格為特殊方格（藍(lán)色），且稱(chēng)該棋盤(pán)為特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。當(dāng)k>0時(shí)，將2k×2k棋盤(pán)分割為4個(gè)2k-1×2k-1子棋盤(pán)。特殊方格位于某個(gè)較小子棋盤(pán)中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格。為了統(tǒng)一子問(wèn)題，將3個(gè)無(wú)特殊方格的子棋盤(pán)轉(zhuǎn)化為特殊棋盤(pán)，用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤(pán)的會(huì)合處，將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤(pán)覆蓋問(wèn)題。遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)1×1。2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1數(shù)據(jù)結(jié)構(gòu)：棋盤(pán)：2k×2k,大小用size(初始為k)表示特殊方格：左上角所在坐標(biāo)(dr,dc)，棋盤(pán)左上角坐標(biāo)為(0,0)L型骨牌：每個(gè)L型骨牌有一個(gè)唯一編號(hào)，從1開(kāi)始2k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1算法思路：判斷特殊方格所在位置，如果1）在左上區(qū)域，直接遞歸求解；否則，覆蓋右下角方格，再遞歸求解2）在右上區(qū)域，直接遞歸求解；否則，覆蓋左下角方格，再遞歸求解3）在左下區(qū)域，直接遞歸求解；否則，覆蓋右上角方格，再遞歸求解4）在右下區(qū)域，直接遞歸求解；否則，覆蓋左上角方格，再遞歸求解defchessBoard(tr,tc,dr,dc,size):ifsize==1:returnglobaltile,boardt=tile#L型骨牌號(hào)

tile+=1s=size//2#分割棋盤(pán)

#覆蓋左上角子棋盤(pán)

ifdr<tr+sanddc<tc+s:#特殊方格在此棋盤(pán)中

chessBoard(tr,tc,dr,dc,s)else:#此棋盤(pán)中無(wú)特殊方格

board[tr+s-1][tc+s-1]=t#用t號(hào)L型骨牌覆蓋右下角

chessBoard(tr,tc,tr+s-1,tc+s-1,s)#覆蓋其余方格

#覆蓋右上角子棋盤(pán)

ifdr<tr+sanddc>=tc+s:chessBoard(tr,tc+s,dr,dc,s)else:board[tr+s-1][tc+s]=t#用t號(hào)L型骨牌覆蓋左下角

chessBoard(tr,tc+s,tr+s-1,tc+s,s)#覆蓋左下角子棋盤(pán)

ifdr>=tr+sanddc<tc+s:chessBoard(tr+s,tc,dr,dc,s)else:board[tr+s][tc+s-1]=t#用t號(hào)L型骨牌覆蓋右上角

chessBoard(tr+s,tc,tr+s,tc+s-1,s)#覆蓋右下角子棋盤(pán)

ifdr>=tr+sanddc>=tc+s:chessBoard(tr+s,tc+s,dr,dc,s)else:board[tr+s][tc+s]=t#用t號(hào)L型骨牌覆蓋左上角

chessBoard(tr+s,tc+s,tr+s,tc+s,s)復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法測(cè)試選擇題：對(duì)于一個(gè)4*4的特殊棋盤(pán)而言，利用分治法進(jìn)行棋盤(pán)覆蓋，第2個(gè)被覆蓋的方格的坐標(biāo)為（）。（坐標(biāo)用方格最坐上角的位置表示，(0,0)則表示最左上角的方格）A:(0,0)B:(1,2)C:(1,0)D:(1,1)不同角度看問(wèn)題棋盤(pán)覆蓋問(wèn)題展現(xiàn)出兩個(gè)方面的信息：一方面說(shuō)明了并