啟發(fā)式規(guī)則分治法遞歸漢諾塔排序算法

第4章分治法4.1概

述

4.2遞

歸4.3排序問(wèn)題中的分治法4.4組合問(wèn)題中的分治法4.5幾何問(wèn)題中的分治法14.1概

述

4.1.1分治法的設(shè)計(jì)思想4.1.2分治法的求解過(guò)程2

將一個(gè)難以直接解決的大問(wèn)題，劃分成一些規(guī)模較小的子問(wèn)題，以便各個(gè)擊破，分而治之。更一般地說(shuō)，將要求解的原問(wèn)題劃分成k個(gè)較小規(guī)模的子問(wèn)題，對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再將每個(gè)子問(wèn)題劃分為k個(gè)規(guī)模更小的子問(wèn)題，如此分解下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止，再將子問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原問(wèn)題的解。4.1.1分治法的設(shè)計(jì)思想32.獨(dú)立子問(wèn)題：各子問(wèn)題之間相互獨(dú)立，這涉及到分治法的效率，如果各子問(wèn)題不是獨(dú)立的，則分治法需要重復(fù)地解公共的子問(wèn)題。1.平衡子問(wèn)題：最好使子問(wèn)題的規(guī)模大致相同。也就是將一個(gè)問(wèn)題劃分成大小相等的k個(gè)子問(wèn)題（通常k＝2），這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡（Balancing）子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。啟發(fā)式規(guī)則：4子問(wèn)題1的規(guī)模是n/2子問(wèn)題1的解子問(wèn)題2的解子問(wèn)題2的規(guī)模是n/2原問(wèn)題的解原問(wèn)題的規(guī)模是n分治法的典型情況54.1.2分治法的求解過(guò)程

一般來(lái)說(shuō)，分治法的求解過(guò)程由以下三個(gè)階段組成：（1）劃分：既然是分治，當(dāng)然需要把規(guī)模為n的原問(wèn)題劃分為k個(gè)規(guī)模較小的子問(wèn)題，并盡量使這k個(gè)子問(wèn)題的規(guī)模大致相同。（2）求解子問(wèn)題：各子問(wèn)題的解法與原問(wèn)題的解法通常是相同的，可以用遞歸的方法求解各個(gè)子問(wèn)題，有時(shí)遞歸處理也可以用循環(huán)來(lái)實(shí)現(xiàn)。（3）合并：把各個(gè)子問(wèn)題的解合并起來(lái)，合并的代價(jià)因情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實(shí)現(xiàn)。6例：計(jì)算an，應(yīng)用分治技術(shù)得到如下計(jì)算方法：3432328131319313193333分解問(wèn)題求解每個(gè)子問(wèn)題合并子問(wèn)題的解不是所有的分治法都比簡(jiǎn)單的蠻力法更有效。分析時(shí)間性能??éù?íì>′==1122naanaannn如果如果7通用分治遞推式問(wèn)題規(guī)模為n的實(shí)例被劃分為b個(gè)規(guī)模為n/b的實(shí)例,其中a個(gè)實(shí)例需要求解,假設(shè)n是b的冪T(n)=aT(n/b)+f(n)8主定理如果在遞推式中f(n)∈(nd），其中d≥0當(dāng)a<bd時(shí)當(dāng)a=bd時(shí)當(dāng)a>bd時(shí)94.2遞

歸

4.2.1遞歸的定義

4.2.2遞歸函數(shù)的運(yùn)行軌跡4.2.3遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程104.2.1遞歸的定義

遞歸（Recursion）就是子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。遞歸有兩個(gè)基本要素：⑴邊界條件：確定遞歸到何時(shí)終止；⑵遞歸模式：大問(wèn)題是如何分解為小問(wèn)題的。11遞歸函數(shù)的經(jīng)典問(wèn)題——漢諾塔問(wèn)題在世界剛被創(chuàng)建的時(shí)候有一座鉆石寶塔（塔A），其上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動(dòng)到塔C上去，其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。

12漢諾塔問(wèn)題可以通過(guò)以下三個(gè)步驟實(shí)現(xiàn)：（1）將塔A上的n-1個(gè)碟子借助塔C先移到塔B上。（2）把塔A上剩下的一個(gè)碟子移到塔C上。（3）將n-1個(gè)碟子從塔B借助塔A移到塔C上。顯然，這是一個(gè)遞歸求解的過(guò)程1314算法4.2——漢諾塔算法

1voidHanoi(intn,charA,charB,charC)

//第一列為語(yǔ)句行號(hào)2{3if(n==1)Move(A,C);//Move是一個(gè)抽象操作，表示將碟子從A移到C上4else{5Hanoi(n-1,A,C,B);6Move(A,C);7Hanoi(n-1,B,A,C);8}9}C++描述154.2.2遞歸函數(shù)的運(yùn)行軌跡

在遞歸函數(shù)中，調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，需要注意的是遞歸函數(shù)的調(diào)用層次，如果把調(diào)用遞歸函數(shù)的主函數(shù)稱為第0層，進(jìn)入函數(shù)后，首次遞歸調(diào)用自身稱為第1層調(diào)用；從第i層遞歸調(diào)用自身稱為第i+1層。反之，退出第i+1層調(diào)用應(yīng)該返回第i層。采用圖示方法描述遞歸函數(shù)的運(yùn)行軌跡，從中可較直觀地了解到各調(diào)用層次及其執(zhí)行情況。16Hanio(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,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)結(jié)束174.2.3遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程

一個(gè)遞歸函數(shù)的調(diào)用過(guò)程類似于多個(gè)函數(shù)的嵌套調(diào)用，只不過(guò)調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)工作棧。具體地說(shuō)，遞歸調(diào)用的內(nèi)部執(zhí)行過(guò)程如下：（1）運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；（2）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。18漢諾塔算法在執(zhí)行過(guò)程中，工作棧的變化下圖所示，其中棧元素的結(jié)構(gòu)為（返回地址，n值，A值，B值，C值），返回地址對(duì)應(yīng)算法中語(yǔ)句的行號(hào)。⑾⑿⒀⒁⑹⑺⑻⑼⑽⑴⑵⑶⑷⑸5,3,A,B,C5,2,A,C,B5,3,A,B,C5,1,A,B,C5,2,A,C,B5,3,A,B,C5,2,A,C,B5,3,A,B,C7,1,C,A,B5,2,A,C,B5,3,A,B,C5,2,A,C,B5,3,A,B,C5,3,A,B,C7,2,B,A,C5,3,A,B,C5,1,B,C,A7,2,B,A,C5,3,A,B,C7,2,B,A,C5,3,A,B,C7,1,A,B,C7,2,B,A,C5,3,A,B,C7,2,B,A,C5,3,A,B,C5,3,A,B,C19遞歸算法結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此，它為設(shè)計(jì)算法和調(diào)試程序帶來(lái)很大方便，是算法設(shè)計(jì)中的一種強(qiáng)有力的工具。但是，因?yàn)檫f歸算法是一種自身調(diào)用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調(diào)用時(shí)的輔助操作增多，因此，遞歸算法的運(yùn)行效率較低。

204.3排序問(wèn)題中的分治法4.3.1歸并排序4.3.2快速排序214.3.1歸并排序

二路歸并排序的分治策略是：（1）劃分：將待排序序列r1,r2,…,rn劃分為兩個(gè)長(zhǎng)度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子問(wèn)題：分別對(duì)這兩個(gè)子序列進(jìn)行排序，得到兩個(gè)有序子序列；（3）合并：將這兩個(gè)有序子序列合并成一個(gè)有序序列。22

r1……rn/2

rn/2＋1……rn劃分r‘1<……<r’n/2r’n/2＋1<……<r’n遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n合并解

23

算法4.3——?dú)w并排序

voidMergeSort(intr[],intr1[],ints,intt){if(s==t)r1[s]=r[s];else{m=(s+t)/2;Mergesort(r,r1,s,m);//歸并排序前半個(gè)子序列Mergesort(r,r1,m+1,t);//歸并排序后半個(gè)子序列Merge(r1,r,s,m,t);//合并兩個(gè)已排序的子序列}}C++描述24算法4.4——合并有序子序列voidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中較小者放入r1[k]elser1[k++]=r[j++];}if(i<=m)while(i<=m)

//若第一個(gè)子序列沒(méi)處理完，則進(jìn)行收尾處理r1[k++]=r[i++];elsewhile(j<=t)

//若第二個(gè)子序列沒(méi)處理完，則進(jìn)行收尾處理r1[k++]=r[j++];}C++描述25

二路歸并排序的合并步的時(shí)間復(fù)雜性為O(n)，所以，二路歸并排序算法存在如下遞推式：根據(jù)1.2.4節(jié)的主定理，二路歸并排序的時(shí)間代價(jià)是O(nlog2n)。二路歸并排序在合并過(guò)程中需要與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此其空間復(fù)雜性為O(n)。

?íì>+==1)2(211)(nnnTnnT264.3.2快速排序

（2）求解子問(wèn)題：分別對(duì)劃分后的每一個(gè)子序列遞歸處理；（3）合并：由于對(duì)子序列r1…ri-1和ri+1…rn的排序是就地進(jìn)行的，所以合并不需要執(zhí)行任何操作?？焖倥判虻姆种尾呗允牵海?）劃分：選定一個(gè)記錄作為軸值，以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列r1…ri-1和ri+1…rn，前一個(gè)子序列中記錄的值均小于或等于軸值，后一個(gè)子序列中記錄的值均大于或等于軸值；27[r1……

ri-1]

ri[ri+1……

rn]

均≤ri軸值均≥ri

位于最終位置

歸并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分，快速排序按照記錄的值對(duì)序列進(jìn)行劃分。28以第一個(gè)記錄作為軸值，對(duì)待排序序列進(jìn)行劃分的過(guò)程為：（1）初始化：取第一個(gè)記錄作為基準(zhǔn)，設(shè)置兩個(gè)參數(shù)i，j分別用來(lái)指示將要與基準(zhǔn)記錄進(jìn)行比較的左側(cè)記錄位置和右側(cè)記錄位置，也就是本次劃分的區(qū)間；（2）右側(cè)掃描過(guò)程：將基準(zhǔn)記錄與j指向的記錄進(jìn)行比較，如果j指向記錄的關(guān)鍵碼大，則j前移一個(gè)記錄位置。重復(fù)右側(cè)掃描過(guò)程，直到右側(cè)的記錄小（即反序），若i＜j，則將基準(zhǔn)記錄與j指向的記錄進(jìn)行交換；（3）左側(cè)掃描過(guò)程：將基準(zhǔn)記錄與i指向的記錄進(jìn)行比較，如果i指向記錄的關(guān)鍵碼小，則i后移一個(gè)記錄位置。重復(fù)左側(cè)掃描過(guò)程，直到左側(cè)的記錄大（即反序），若i＜j，則將基準(zhǔn)記錄與i指向的記錄交換；（4）重復(fù)（2）（3）步，直到i與j指向同一位置，即基準(zhǔn)記錄最終的位置。2913652750384955jijj13652750384955jiii13652750384955ijjj一次劃分示例30算法4.5——一次劃分intPartition(intr[],intfirst,intend){i=first;j=end;//初始化while(i<j){

while(i<j&&r[i]<=r[j])j--；//右側(cè)掃描if(i<j){r[i]←→r[j];//將較小記錄交換到前面i++;}while(i<j&&r[i]<=r[j])i++；//左側(cè)掃描if(i<j){r[j]←→r[i];//將較大記錄交換到后面j--;}}retutni;//i為軸值記錄的最終位置}C++描述31以軸值為基準(zhǔn)將待排序序列劃分為兩個(gè)子序列后，對(duì)每一個(gè)子序列分別遞歸進(jìn)行排序。132750384955jiij136527503849556532算法4.6——快速排序

voidQuickSort(intr[],intfirst,intend){if(first<end){pivot=Partition(r,first,end);//問(wèn)題分解，pivot是軸值在序列中的位置QuickSort(r,first,pivot-1);//遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序QuickSort(r,pivot+1,end);//遞歸地對(duì)右側(cè)子序列進(jìn)行快速排序}}C++描述33T(n)≤2T(n/2)＋n≤2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n≤4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………

≤nT(1)＋nlog2n＝O(nlog2n)

因此，時(shí)間復(fù)雜度為O(nlog2n)。

在最好情況下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同。在具有n個(gè)記錄的序列中，一次劃分需要對(duì)整個(gè)待劃分序列掃描一遍，則所需時(shí)間為O(n)。設(shè)T(n)是對(duì)n個(gè)記錄的序列進(jìn)行排序的時(shí)間，每次劃分后，正好把待劃分區(qū)間劃分為長(zhǎng)度相等的兩個(gè)子序列，則有：34因此，時(shí)間復(fù)雜度為O(n2)。

在最壞情況下，待排序記錄序列正序或逆序，每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空）。此時(shí)，必須經(jīng)過(guò)n-1次遞歸調(diào)用才能把所有記錄定位，而且第i趟劃分需要經(jīng)過(guò)n-i次關(guān)鍵碼的比較才能找到第i個(gè)記錄的基準(zhǔn)位置，因此，總的比較次數(shù)為：35在平均情況下，設(shè)基準(zhǔn)記錄的關(guān)鍵碼第k?。?≤k≤n），則有：這是快速排序的平均時(shí)間性能，可以用歸納法證明，其數(shù)量級(jí)也為O(nlog2n)。

364.4組合問(wèn)題中的分治法

4.4.1最大子段和問(wèn)題

4.4.2棋盤(pán)覆蓋問(wèn)題4.4.3循環(huán)賽日程安排問(wèn)題

37給定由n個(gè)整數(shù)組成的序列(a1,a2,…,an)，最大子段和問(wèn)題要求該序列形如的最大值（1≤i≤j≤n），當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。例如，序列(-20,11,-4,13,-5,-2)的最大子段和為：

4.4.1最大子段和問(wèn)題

最大子段和問(wèn)題的分治策略是：（1）劃分：按照平衡子問(wèn)題的原則，將序列(a1,a2,…,an)劃分成長(zhǎng)度相同的兩個(gè)子序列(a1,…,a)和(a＋1,

…,an)，則會(huì)出現(xiàn)以下三種情況：

38①a1,…,an的最大子段和＝a1,…,a的最大子段和；②a1,…,an的最大子段和＝a＋1,

…,an的最大子段和；③a1,…,an的最大子段和＝，且（2）求解子問(wèn)題：對(duì)于劃分階段的情況①和②可遞歸求解，情況③需要分別計(jì)算，

，則s1+s2為情況③的最大子段和。（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問(wèn)題的解。39a1……ai…amid

amid+1…aj……an劃分leftsum

rightsum遞歸處理a1……ai…amid

amid+1…aj……an最大子段和橫跨兩個(gè)子序列sum不能遞歸處理max{leftsum,sum,rightsum}合并解40算法4.7——最大子段和問(wèn)題intMaxSum(inta[],intleft,intright){sum=0;if(left==right){//如果序列長(zhǎng)度為1，直接求解if(a[left]>0)sum=a[left];elsesum=0;}else{center=(left+right)/2;//劃分leftsum=MaxSum(a,left,center);//對(duì)應(yīng)情況①，遞歸求解rightsum=MaxSum(a,center+1,right);//對(duì)應(yīng)情況②，遞歸求解C++描述41s1=0;lefts=0;

//以下對(duì)應(yīng)情況③，先求解s1for(i=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;//再求解s2for(j=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}sum=s1+s2;//計(jì)算情況③的最大子段和if(sum<leftsum)sum=leftsum;//合并，在sum、leftsum和rightsum中取較大者if(sum<rightsum)sum=rightsum;}returnsum;}42分析算法4.7的時(shí)間性能，對(duì)應(yīng)劃分得到的情況①和②，需要分別遞歸求解，對(duì)應(yīng)情況③，兩個(gè)并列for循環(huán)的時(shí)間復(fù)雜性是O(n)，所以，存在如下遞推式：根據(jù)1.2.4節(jié)主定理，算法4.7的時(shí)間復(fù)雜性為O(nlog2n)。

434.4.2棋盤(pán)覆蓋問(wèn)題

在一個(gè)2k×2k（k≥0）個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其他方格不同，稱該方格為特殊方格。棋盤(pán)覆蓋問(wèn)題要求用圖4.11（b）所示的4種不同形狀的L型骨牌覆蓋給定棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。(a)k=2時(shí)的一種棋盤(pán)(b)4種不同形狀的L型骨牌44分治法求解棋盤(pán)覆蓋問(wèn)題的技巧在于劃分棋盤(pán)，使劃分后的子棋盤(pán)的大小相同，并且每個(gè)子棋盤(pán)均包含一個(gè)特殊方格，從而將原問(wèn)題分解為規(guī)模較小的棋盤(pán)覆蓋問(wèn)題。k>0時(shí)，可將2k×2k的棋盤(pán)劃分為4個(gè)2k-1×2k-1的子棋盤(pán)，這樣劃分后，由于原棋盤(pán)只有一個(gè)特殊方格，所以，這4個(gè)子棋盤(pán)中只有一個(gè)子棋盤(pán)包含該特殊方格，其余3個(gè)子棋盤(pán)中沒(méi)有特殊方格。為了將這3個(gè)沒(méi)有特殊方格的子棋盤(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)分割為1×1的子棋盤(pán)。

452k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盤(pán)分割(b)構(gòu)造相同子問(wèn)題46下面討論棋盤(pán)覆蓋問(wèn)題中數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。（1）棋盤(pán)：可以用一個(gè)二維數(shù)組board[size][size]表示一個(gè)棋盤(pán)，其中，size=2k。為了在遞歸處理的過(guò)程中使用同一個(gè)棋盤(pán)，將數(shù)組board設(shè)為全局變量；（2）子棋盤(pán)：整個(gè)棋盤(pán)用二維數(shù)組board[size][size]表示，其中的子棋盤(pán)由棋盤(pán)左上角的下標(biāo)tr、tc和棋盤(pán)大小s表示；（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是該特殊方格在二維數(shù)組board中的下標(biāo);（4）L型骨牌：一個(gè)2k×2k的棋盤(pán)中有一個(gè)特殊方格，所以，用到L型骨牌的個(gè)數(shù)為(4k-1)/3，將所有L型骨牌從1開(kāi)始連續(xù)編號(hào)，用一個(gè)全局變量t表示。47dcdrtrtcsize棋盤(pán)覆蓋問(wèn)題中的數(shù)據(jù)結(jié)構(gòu)48算法4.8——棋盤(pán)覆蓋voidChessBoard(inttr,inttc,intdr,intdc,intsize)//tr和tc是棋盤(pán)左上角的下標(biāo)，dr和dc是特殊方格的下標(biāo)，//size是棋盤(pán)的大小，t已初始化為0{if(size==1)return;//棋盤(pán)只有一個(gè)方格且是特殊方格t++;//L型骨牌號(hào)s=size/2;//劃分棋盤(pán)//覆蓋左上角子棋盤(pán)if(dr<tr+s&&dc<tc+s)//特殊方格在左上角子棋盤(pán)中ChessBoard(tr,tc,dr,dc,s);//遞歸處理子棋盤(pán)else{//用t號(hào)L型骨牌覆蓋右下角，再遞歸處理子棋盤(pán)board[tr+s-1][tc+s-1]=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}

C++描述49//覆蓋右上角子棋盤(pán)if(dr<tr+s&&dc>=tc+s)//特殊方格在右上角子棋盤(pán)中ChessBoard(tr,tc+s,dr,dc,s);//遞歸處理子棋盤(pán)else{//用t號(hào)L型骨牌覆蓋左下角，再遞歸處理子棋盤(pán)board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤(pán)if(dr>=tr+s&&dc<tc+s)//特殊方格在左下角子棋盤(pán)中ChessBoard(tr+s,tc,dr,dc,s);//遞歸處理子棋盤(pán)else{//用t號(hào)L型骨牌覆蓋右上角，再遞歸處理子棋盤(pán)board[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤(pán)if(dr>=tr+s&&dc>=tc+s)//特殊方格在右下角子棋盤(pán)中ChessBoard(tr+s,tc+s,dr,dc,s);//遞歸處理子棋盤(pán)else{//用t號(hào)L型骨牌覆蓋左上角，再遞歸處理子棋盤(pán)board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}50設(shè)T(k)是覆蓋一個(gè)2k×2k棋盤(pán)所需時(shí)間，從算法的劃分策略可知，T(k)滿足如下遞推式：

解此遞推式可得T(k)=O(4k)。由于覆蓋一個(gè)2k×2k棋盤(pán)所需的骨牌個(gè)數(shù)為(4k-1)/3，所以，算法4.8是一個(gè)在漸進(jìn)意義下的最優(yōu)算法。

514.4.3循環(huán)賽日程安排問(wèn)題

設(shè)有n=2k個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次；（2）每個(gè)選手一天只能賽一次。按此要求，可將比賽日程表設(shè)計(jì)成一個(gè)n行n-1列的二維表，其中，第i行第j列表示和第i個(gè)選手在第j天比賽的選手。52按照分治的策略，可將所有參賽的選手分為兩部分，n＝2k個(gè)選手的比賽日程表就可以通過(guò)為n/2＝2k-1個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地執(zhí)行這種分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單：只要讓這2個(gè)選手進(jìn)行比賽就可以了。53顯然，這個(gè)求解過(guò)程是自底向上的迭代過(guò)程，其中左上角和左下角分別為選手1至選手4以及選手5至選手8前3天的比賽日程，據(jù)此，將左上角部分的所有數(shù)字按其對(duì)應(yīng)位置抄到右下角，將左下角的所有數(shù)字按其對(duì)應(yīng)位置抄到右上角，這樣，就分別安排好了選手1至選手4以及選手5至選手8在后4天的比賽日程，如圖(c)所示。具有多個(gè)選手的情況可以依此類推。

(b)2k(k=2)個(gè)選手比賽(c)2k(k=3)個(gè)選手比賽加4加2(a)2k(k=1)個(gè)選手比賽12211221344334431221123421433412432156786587785687655678658778568765123421433412432154這種解法是把求解2k個(gè)選手比賽日程問(wèn)題劃分成依次求解21、22、…、2k個(gè)選手的比賽日程問(wèn)題，換言之，2k個(gè)選手的比賽日程是在2k-1個(gè)選手的比賽日程的基礎(chǔ)上通過(guò)迭代的方法求得的。在每次迭代中，將問(wèn)題劃分為4部分：（1）左上角：左上角為2k-1個(gè)選手在前半程的比賽日程；（2）左下角：左下角為另2k-1個(gè)選手在前半程的比賽日程，由左上角加2k-1得到，例如22個(gè)選手比賽，左下角由左上角直接加2得到，23個(gè)選手比賽，左下角由左上角直接加4得到；（3）右上角：將左下角直接抄到右上角得到另2k-1個(gè)選手在后半程的比賽日程；（4）右下角：將左上角直接抄到右下角得到2k-1個(gè)選手在后半程的比賽日程；算法設(shè)計(jì)的關(guān)鍵在于尋找這4部分元素之間的對(duì)應(yīng)關(guān)系。55算法4.9——循環(huán)賽日程表voidGameTable(intk,inta[][]){//n=2k(k≥1)個(gè)選手參加比賽，//二維數(shù)組a表示日程安排，數(shù)組下標(biāo)從1開(kāi)始n=2;//k=0，2個(gè)選手比賽日程可直接求得//求解2個(gè)選手比賽日程，得到左上角元素a[1][1]=1;a[1][2]=2;a[2][1]=2;a[2][2]=1;for(t=1;t<k;t++)//迭代處理，依次處理22,…,2k個(gè)選手比賽日程{

C++描述56temp=n;n=n*2;//填左下角元素for(i=temp+1;i<=n;i++)for(j=1;j<=temp;j++)a[i][j]=a[i-temp][j]+temp;//左下角元素和左上角元素的對(duì)應(yīng)關(guān)系//填右上角元素for(i=1;i<=temp;i++)for(j=temp+1;j<=n;j++)a[i][j]=a[i+temp][(j+temp)%n];//填右下角元素for(i=temp+1;i<=n;i++)for(j=temp+1;j<=n;j++)a[i][j]=a[i-temp][j-temp];}}57分析算法4.9的時(shí)間性能，迭代處理的循環(huán)體內(nèi)部有3個(gè)循環(huán)語(yǔ)句，每個(gè)循環(huán)語(yǔ)句都是一個(gè)嵌套的for循環(huán)，且他們的執(zhí)行次數(shù)相同，基本語(yǔ)句是最內(nèi)層循環(huán)體的賦值語(yǔ)句，即填寫(xiě)比賽日程表中的元素。基本語(yǔ)句的執(zhí)行次數(shù)是：所以，算法4.9的其時(shí)間復(fù)雜性為O(4k)。584.5幾何問(wèn)題中的分治法4.5.1最近對(duì)問(wèn)題

594.5.1最近對(duì)問(wèn)題

設(shè)p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，最近對(duì)問(wèn)題就是找出集合S中距離最近的點(diǎn)對(duì)。嚴(yán)格地講，最接近點(diǎn)對(duì)可能多于一對(duì)，簡(jiǎn)單起見(jiàn)，只找出其中的一對(duì)作為問(wèn)題的解。

60