第遞歸與分治策略馮

會計學1第遞歸與分治策略馮2023/1/192本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第1頁/共97頁2023/1/1935.1.1分治法的設計思想

5.1.2分治法的求解過程概述第2頁/共97頁2023/1/194

將一個難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，以各個擊破，分而治之。更一般地說，將要求解的原問題劃分成k個較小規(guī)模的子問題，對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再將每個子問題劃分為k個規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原問題的解。分治法的設計思想：

概述-分治法思想第3頁/共97頁2023/1/1952.獨立子問題：各子問題之間相互獨立，這涉及到分治法的效率，如果各子問題不是獨立的，則分治法需要重復地解公共的子問題。1.平衡子問題：最好使子問題的規(guī)模大致相同。也就是將一個問題劃分成大小相等的k個子問題（通常k＝2、4,…），這種使子問題規(guī)模大致相等的做法是出自一種平衡（Balancing）子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。啟發(fā)式規(guī)則：概述-分治法思想第4頁/共97頁2023/1/196

子問題1的規(guī)模是n/2

子問題1的解

子問題2的解

子問題2的規(guī)模是n/2

原問題的解

原問題的規(guī)模是n分治法的典型情況概述-分治法思想第5頁/共97頁2023/1/1975.1.1分治法的設計思想5.1.2分治法的求解過程概述第6頁/共97頁2023/1/198

一般來說，分治法的求解過程由以下三個階段組成：（1）劃分：既然是分治，當然要把規(guī)模為n的原問題劃分為k個規(guī)模較小的子問題，并盡量使這

k個子問題的規(guī)模大致相同。（2）求解子問題：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環(huán)來實現。（3）合并：把各個子問題的解合并起來，合并的代價因情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實現。概述-分治法的求解過程第7頁/共97頁2023/1/199概述-分治法的求解過程分治法的一般過程

1DivideConquer(P)//求解規(guī)模為n的問題P2{3if(P的規(guī)模足夠小)

直接求解P;

分解為k個子問題P1,P2,…,Pk;4for(i=1;i<=k;i++)5yi=DivideConquer(P);//解各子問題，通常采用遞歸

6returnMerge(y1,y2,…,yk);//將各子問題的解合并為原問題的解

7}C++描述第8頁/共97頁2023/1/1910

例：計算an，應用分治技術得到如下計算方法3432328131319313193333分解問題求解每個子問題合并子問題的解分析時間性能??éù?íì>′==1122naanaannn如果如果第9頁/共97頁2023/1/1911討論a^n的蠻力法計算復雜度為O(n)，因為：……a=1;For(i=1;i<=n;i++){a=a*a;}……A^n的通用分治遞推式主定理（第一章中），其復雜度為O（nlog2n）概述-分治法的求解過程

結論：不是所有的分治法都比簡單的蠻力法更有效。第10頁/共97頁2023/1/1912本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第11頁/共97頁2023/1/19134.2遞歸

5.2.1遞歸的概念5.2.2遞歸函數的運行軌跡5.2.3遞歸函數的內部執(zhí)行過程第12頁/共97頁2023/1/1914遞歸的概念直接或間接地調用自身的算法稱為遞歸算法（Recursion）。用函數自身給出定義的函數稱為遞歸函數。是一種描述問題和解決問題的基本方法。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。第13頁/共97頁2023/1/1915遞歸的概念分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。遞歸有兩個基本要素：⑴邊界條件：確定遞歸到何時終止；⑵遞歸模式：大問題是如何分解為小問題的。遞歸的幾個實例第14頁/共97頁2023/1/1916例1階乘（Factorial

）函數階乘函數可遞歸地定義為：邊界條件遞歸方程遞歸的概念第15頁/共97頁2023/1/1917Factorial遞歸算法

1publicstaticintfactorial(intn)

2{3if(n==0)return1;4returnn*factorial(n-1);

5}C++描述遞歸的概念第16頁/共97頁2023/1/1918例2Fibonacci斐波納契兔子數列

無窮數列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數可遞歸地計算如下：publicstaticintfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}遞歸的概念第17頁/共97頁2023/1/1919前2例中的函數都可以找到相應的非遞歸方式定義：遞歸的概念第18頁/共97頁2023/1/1920例3整數劃分問題將正整數n表示成一系列正整數之和：n=n1+n2+…+nk，

其中：n1≥n2≥…≥nk≥1，k≥1正整數n的這種表示稱為正整數n的劃分。求正整數n的不同劃分個數。例如正整數6有如下11種不同的劃分：

6；

5+1；

4+2；4+1+1；

3+3；3+2+1；3+1+1+1；

2+2+2；2+2+1+1；2+1+1+1+1；

1+1+1+1+1+1所以，6的劃分數記為：p(6)=11遞歸的概念第19頁/共97頁2023/1/1921(2)q(n,m)=q(n,n),mn;最大加數n1實際上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;當最大加數n1不大于1時，任何正整數n只有一種劃分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數n的最大加數n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數n的劃分由n1=n的劃分和n1≤n-1的劃分組成。前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數直接求解。在本例中，如果設p(n)為正整數n的劃分數，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數n1不大于m的劃分個數記作q(n,m)?？梢越(n,m)的如下遞歸關系。遞歸的概念第20頁/共97頁2023/1/1922例5整數劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數直接求解。在本例中，如果設p(n)為正整數n的劃分數，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數n1不大于m的劃分個數記作q(n,m)。可以建立q(n,m)的如下遞歸關系。正整數n的劃分數p(n)=q(n,n)。遞歸的概念第21頁/共97頁2023/1/1923

遞歸算法結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此，它為設計算法和調試程序帶來很大方便，是算法設計中的一種強有力的工具。但是，因為遞歸算法是一種自身調用自身的算法，隨著遞歸深度的增加，工作棧所需要的空間增大，遞歸調用時的輔助操作增多，因此，遞歸算法的運行效率較低。

遞歸小結第22頁/共97頁2023/1/1924遞歸小結優(yōu)點：

結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。缺點：

遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。第23頁/共97頁2023/1/1925遞歸小結-分治法適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。第24頁/共97頁2023/1/1926遞歸小結-分治法基本步驟divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問題

returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解

}

人們從大量實踐中發(fā)現，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。第25頁/共97頁2023/1/1927本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第26頁/共97頁2023/1/1928排序問題中的分治法5.3.1歸并排序5.3.2快速排序第27頁/共97頁2023/1/1929歸并排序

二路歸并排序的分治策略是：（1）劃分：將待排序序列r1,r2,…,rn劃分為兩個長度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子問題：分別對這兩個子序列進行排序，得到兩個有序子序列；（3）合并：將這兩個有序子序列合并成一個有序序列。排序問題中的分治法第28頁/共97頁2023/1/1930

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

合并解

排序問題中的分治法第29頁/共97頁2023/1/1931

算法5.3——歸并排序

voidMergeSort(intr[],intr1[],ints,intt)//r[]—原序列數組，r1[]—歸并后序列數組

{if(s==t)r1[s]=r[s];else{m=(s+t)/2;Mergesort(r,r1,s,m);//歸并排序前半個子序列

Mergesort(r,r1,m+1,t);//歸并排序后半個子序列

Merge(r1,r,s,m,t);//合并兩個已排序的子序列

}}C++描述排序問題中的分治法ijr[s],…,r[m]r[m+1],…,r[t]第30頁/共97頁2023/1/1932算法5.4——合并有序子序列

voidMerge(intr[],intr1[],ints,intm,intt)

{//i,j分別指向兩個待合并的有序子序列，k指向最終有序序列的當前記錄

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)

//若第一個子序列沒處理完，則進行收尾處理

r1[k++]=r[i++];elsewhile(j<=t)

//若第二個子序列沒處理完，則進行收尾處理

r1[k++]=r[j++];}C++描述排序問題中的分治法ijr[s],…,r[m]r[m+1],…,r[t]kr1[s],…,r1[m],r1[m+1],…,r1[t]第31頁/共97頁2023/1/1933

二路歸并排序的合并步的時間復雜性為O(n)，所以，二路歸并排序算法存在如下遞推式：根據1.2.4節(jié)的主定理，二路歸并排序的時間代價是O(nlog2n)。?íì>+==2)2(221)(nnnTnnT排序問題中的分治法第32頁/共97頁2023/1/1934（2）求解子問題：分別對劃分后的每一個子序列遞歸處理；（3）合并：由于對子序列r1…ri-1和ri+1…rn的排序是就地進行的，所以合并不需要執(zhí)行任何操作?？焖倥判虻姆种尾呗裕?）劃分：選定一個記錄作為軸值，以軸值為基準將整個序列劃分為兩個子序列r1…ri-1和ri+1…rn，前一個子序列中記錄的值均小于或等于軸值，后一個子序列中記錄的值均大于或等于軸值；排序問題中的分治法第33頁/共97頁2023/1/1935[r1……

ri-1]

ri[ri+1……

rn]

均≤ri

軸值均≥ri

位于最終位置

兩種排序的區(qū)別：歸并排序按照記錄在序列中的位置對序列進行劃分，快速排序按照記錄的值對序列進行劃分排序問題中的分治法第34頁/共97頁2023/1/1936以第一個記錄作為軸值，對待排序序列進行劃分的過程：（1）初始化：取第一個記錄作為基準，設置兩個參數i，j分別用來指示將要與基準記錄進行比較的左側記錄位置和右側記錄位置，也就是本次劃分的區(qū)間；（2）右側掃描過程：將基準記錄與j指向的記錄進行比較，如果j指向記錄的關鍵碼大，則j--,即前移一個記錄位置。重復右側掃描過程，直到右側的記錄?。捶葱颍?，若i＜j，則將基準記錄與j指向的記錄進行交換；（3）左側掃描過程：將基準記錄與i指向的記錄進行比較，如果i指向記錄的關鍵碼小，則i++，即后移一個記錄位置。重復左側掃描過程，直到左側的記錄大（即反序），若i＜j，則將基準記錄與i指向的記錄交換；排序問題中的分治法第35頁/共97頁2023/1/1937（4）重復（2）（3）步，直到i與j指向同一位置，即基準記錄最終的位置。排序問題中的分治法一次劃分示例:

（1）i=1,j=7，r[1]為基準記錄;

（2）r[1]>r[j]?r[1]<r[j],j—，否則交換（3）r[i]<r[j]?r[i]<r[j],i++,否則交換（4）i=j?Ifi=j,then第一次劃分基準記錄位置找到第36頁/共97頁2023/1/193813652750384955jijj13652750384955jiii13652750384955ijjj一次劃分示例第37頁/共97頁2023/1/1939算法5.5——一次劃分

intPartition(intr[],intfirst,intend){i=first;j=end;//初始化

while(i<j){

while(i<j&&r[i]<=r[j])

j--；//右側掃描

if(i<j){r[i]←→r[j];//將較小記錄交換到前面

i++;}while(i<j&&r[i]<=r[j])i++；//左側掃描

if(i<j){r[j]←→r[i];//將較大記錄交換到后面

j--;}}retutni;//i為軸值記錄的最終位置}C++描述排序問題中的分治法第38頁/共97頁2023/1/1940

以軸值(如此處為軸值：38)為基準將待排序序列劃分為兩個子序列后，對每一個子序列分別遞歸進行排序。132750384955jiij1365275038495565排序問題中的分治法第39頁/共97頁2023/1/1941算法5.6——快速排序

voidQuickSort(intr[],intfirst,intend){if(first<end){

pivot=Partition(r,first,end);

//問題分解，pivot是軸值在序列中的位置

QuickSort(r,first,pivot-1);

//遞歸地對左側子序列進行快速排序

QuickSort(r,pivot+1,end);//遞歸地對右側子序列進行快速排序

}}C++描述排序問題中的分治法第40頁/共97頁2023/1/1942T(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)

因此，時間復雜度為O(nlog2n)。最好情況：每次劃分對一個記錄定位后，該記錄的左側子序列與右側子序列的長度相同。在具有n個記錄的序列中，一次劃分需要對整個待劃分序列掃描一遍，則所需時間為O(n)。設T(n)是對n個記錄的序列進行排序的時間，每次劃分后，正好把待劃分區(qū)間劃分為長度相等的兩個子序列，則有：排序問題中的分治法第41頁/共97頁2023/1/1943因此，時間復雜度為O(n2)。最壞情況：待排序記錄序列正序或逆序，每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空）。此時，必須經過n-1次遞歸調用才能把所有記錄定位，而且第i趟劃分需要經過n-i次關鍵碼的比較才能找到第i個記錄的基準位置，因此，總的比較次數為：排序問題中的分治法第42頁/共97頁2023/1/1944在平均情況下，設基準記錄的關鍵碼第k?。?≤k≤n），則有：

這是快速排序的平均時間性能，可以用歸納法證明，其數量級也為O(nlog2n)。

排序問題中的分治法第43頁/共97頁2023/1/1945本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第44頁/共97頁2023/1/1946組合問題中的分治法

5.4.1最大子段和問題

5.4.2棋盤覆蓋問題5.4.3循環(huán)賽日程安排問題

第45頁/共97頁2023/1/1947

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

最大子段和問題

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

…,an)，則會出現以下三種情況：

第46頁/共97頁2023/1/1948①

a1,…,an的最大子段和＝a1,…,a的最大子段和；②

a1,…,an的最大子段和＝a＋1,

…,an的最大子段和；③

a1,…,an的最大子段和＝，且（2）求解子問題：對于劃分階段的情況①和②可遞歸求解，情況③需要分別計算:

則s1+s2為情況③的最大子段和。最大子段和問題

第47頁/共97頁2023/1/1949a1……ai…amid

amid+1…aj……an劃分leftsum

rightsum

遞歸處理a1……ai…amid

amid+1…aj……an最大子段和橫跨兩個子序列sum不能遞歸處理max{leftsum,sum,rightsum}合并解最大子段和問題

（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問題的解。第48頁/共97頁2023/1/1950算法5.7——最大子段和問題

intMaxSum(inta[],intleft,intright){sum=0;if(left==right){ //如果序列長度為1，直接求解

if(a[left]>0)sum=a[left];elsesum=0;}else{

center=(left+right)/2; //劃分

leftsum=MaxSum(a,left,center); //對應情況①，遞歸求解

rightsum=MaxSum(a,center+1,right);//對應情況②，遞歸求解C++描述最大子段和問題

第49頁/共97頁2023/1/1951s1=0;lefts=0;

//以下對應情況③，先求解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; //計算情況③的最大子段和

if(sum<leftsum)sum=leftsum;//合并，在sum、leftsum和rightsum中取較大者

if(sum<rightsum)sum=rightsum;}returnsum;}最大子段和問題

第50頁/共97頁2023/1/1952

分析算法5.7的時間性能，對應劃分得到的情況①和②，需要分別遞歸求解，對應情況③，兩個并列for循環(huán)的時間復雜性是O(n)，所以，存在如下遞推式：根據1.2.4節(jié)主定理，算法4.7的時間復雜性為O(nlog2n)。

最大子段和問題

第51頁/共97頁2023/1/1953組合問題中的分治法

5.4.1最大子段和問題

5.4.2棋盤覆蓋問題5.4.3循環(huán)賽日程安排問題

第52頁/共97頁2023/1/1954棋盤覆蓋問題

在一個2k×2k

（k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。特殊方格在棋盤中出現的位置有4^k種情形，因而有4^k中不同的棋盤，(a)圖是其中的一個。棋盤覆蓋問題？要求用圖4.11（b）所示的4種不同形狀的L型骨牌覆蓋給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。(a)k=2時的一種棋盤(b)4種不同形狀的L型骨牌第53頁/共97頁2023/1/1955

分治法求解棋盤覆蓋問題的技巧在于劃分棋盤，使劃分后的子棋盤的大小相同，并且每個子棋盤均包含一個特殊方格，從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。

k>0時，可將2k×2k的棋盤劃分為4個2k-1×2k-1的子棋盤，這樣劃分后，由于原棋盤只有一個特殊方格，所以，這4個子棋盤中只有一個子棋盤包含該特殊方格，其余3個子棋盤中沒有特殊方格。為了將這3個沒有特殊方格的子棋盤轉化為特殊棋盤，以便采用遞歸方法求解，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1×1的子棋盤。

棋盤覆蓋問題

第54頁/共97頁2023/1/19562k-1×2k-12k-1×2k-12k-1×2k-12k-1×2k-1(a)棋盤分割(b)構造相同子問題棋盤覆蓋問題

第55頁/共97頁2023/1/1957下面討論棋盤覆蓋問題中數據結構的設計。（1）棋盤：可以用一個二維數組board[size][size]表示一個棋盤，其中，size=2k。為了在遞歸處理的過程中使用同一個棋盤，將數組board設為全局變量；（2）子棋盤：整個棋盤用二維數組board[size][size]表示，其中的子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示；（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是該特殊方格在二維數組board中的下標;（4）L型骨牌：一個2k×2k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數為(4k-1)/3，將所有L型骨牌從1

開始連續(xù)編號，用一個全局變量

t表示。棋盤覆蓋問題

第56頁/共97頁2023/1/1958dcdrtrtcsize棋盤覆蓋問題中的數據結構棋盤覆蓋問題

第57頁/共97頁2023/1/1959算法5.8——棋盤覆蓋voidChessBoard(inttr,inttc,intdr,intdc,intsize)//tr和tc是子棋盤左上角的下標，dr和dc是特殊方格的下標，//size是棋盤的大小，t是骨牌編號，已初始化為0{

if(size==1)return;//棋盤只有一個方格且是特殊方格

t++; //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);}C++描述棋盤覆蓋問題

第58頁/共97頁2023/1/1960

//覆蓋右上角子棋盤

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);}棋盤覆蓋問題

第59頁/共97頁2023/1/1961

//覆蓋右下角子棋盤

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);}}棋盤覆蓋問題

第60頁/共97頁2023/1/1962

設T(k)是覆蓋一個2k×2k棋盤所需時間，從算法的劃分策略可知，T(k)滿足如下遞推式：

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

棋盤覆蓋問題

第61頁/共97頁2023/1/1963組合問題中的分治法

5.4.1最大子段和問題

5.4.2棋盤覆蓋問題5.4.3循環(huán)賽日程安排問題

第62頁/共97頁2023/1/1964本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第63頁/共97頁2023/1/19655.5幾何問題中的分治法5.5.1最近對問題

5.5.2凸包問題第64頁/共97頁2023/1/1966最近對問題

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

第65頁/共97頁2023/1/1967

用分治法解決最近對問題，很自然的想法就是將集合S

分成兩個子集S1和S2，每個子集中有n/2個點。然后在每個子集中遞歸地求其最接近的點對，在求出每個子集的最接近點對后，在合并步中，如果集合S中最接近的兩個點都在子集S1或S2中，則問題很容易解決，如果這兩個點分別在S1和S2中，問題就比較復雜了。最近對問題

第66頁/共97頁2023/1/1968為了使問題易于理解，先考慮一維的情形。此時，S中的點退化為x軸上的n個點x1,x2,…,xn。用x軸上的某個點

m將S劃分為兩個集合S1和S2，并且S1和S2含有點的個數相同。遞歸地在S1和S2上求出最接近點對(p1,p2)和(q1,q2)，如果集合S中的最接近點對都在子集S1或S2中，則d=min{(p1,p2),(q1,q2)}即為所求，如果集合S中的最接近點對分別在S1和S2中，則一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。S1S2p2p1p3q3q1q2m最近對問題

第67頁/共97頁2023/1/1969

按這種分治策略求解最近對問題的算法效率取決于劃分點m的選取，一個基本的要求是要遵循平衡子問題的原則。如果選取m=(max{S}+min{S})/2，則有可能因集合S中點分布的不均勻而造成子集S1和S2的不平衡，如果用S中各點坐標的中位數（即S的中值）作為分割點，則會得到一個平衡的分割點m，使得子集S1和S2中有個數大致相同的點。最近對問題

第68頁/共97頁2023/1/1970下面考慮二維的情形，此時S中的點為平面上的點。為了將平面上的點集S分割為點的個數大致相同的兩個子集S1和S2，選取垂直線x=m來作為分割線，其中，m為S中各點x坐標的中位數。由此將S分割為S1={p∈S|xp≤m}和S2={q∈S|xq＞m}。遞歸地在S1和S2上求解最近對問題，分別得到S1中的最近距離d1和S2中的最近距離d2，令d=min(d1,d2)，若S的最近對(p,q)之間的距離小于d，則p和q必分屬于S1和S2，不妨設p∈S1，q∈S2，則p和q距直線x=m的距離均小于d，所以，可以將求解限制在以x=m為中心、寬度為2d的垂直帶P1和P2中，垂直帶之外的任何點對之間的距離都一定大于d。

最近對問題

第69頁/共97頁2023/1/1971x=mddd2d1S1S2pq

最近對問題的分治思想P1P2S1={p∈S|xp≤m}S2={q∈S|xq＞m}最近對問題

第70頁/共97頁2023/1/1972x=mddp(a)包含點q的d×2d的矩形區(qū)域(b)最壞情況下需要檢查的6個點P1P22dx=mddpP1P22d

對于點p∈P1，需要考察P2中的各個點和點p之間的距離是否小于d，顯然，P2中這樣點的y軸坐標一定位于區(qū)間[y-d,y+d]之間，而且，這樣的點不會超過6個。

第71頁/共97頁2023/1/1973

應用分治法求解含有n個點的最近對問題，其時間復雜性可由下面的遞推式表示：合并子問題的解的時間f(n)＝O(1)，根據1.2.4節(jié)的主定理，可得T(n)=O(nlog2n)。最近對問題

第72頁/共97頁2023/1/19744.5幾何問題中的分治法5.5.1最近對問題

5.5.2凸包問題第73頁/共97頁2023/1/1975凸包問題

設p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個點構成的集合S，并且這些點按照x軸坐標升序排列。幾何學中有這樣一個明顯的事實：最左邊的點p1和最右邊的點pn一定是該集合的凸包頂點（即極點）。設p1pn是從p1到pn的直線，這條直線把集合S分成兩個子集：S1是位于直線左側和直線上的點構成的集合，S2是位于直線右側和直線上的點構成的集合。S1的凸包由下列線段構成：以p1和pn為端點的線段構成的下邊界，以及由多條線段構成的上邊界，這條上邊界稱為上包。類似地，S2中的多條線段構成的下邊界稱為下包。整個集合S的凸包是由上包和下包構成的。

第74頁/共97頁2023/1/1976p1pn

點集合S的上包和下包S1S2凸包問題

pmax第75頁/共97頁2023/1/1977p1pmaxpn快包的思想是：首先找到S1中的頂點pmax，它是距離直線p1pn最遠的頂點，則三角形pmaxp1pn的面積最大。S1中所有在直線p1pmax左側的點構成集合S1,1，S1中所有在直線pnpmax右側的點構成集合S1,2，包含在三角形pmaxp1pn之中的點可以不考慮了。遞歸地繼續(xù)構造集合S1,1的上包和集合S1,2的上包，然后將求解過程中得到的所有最遠距離的點連接起來，就可以得到集合S1的上包。凸包問題

S1,1S1,2第76頁/共97頁2023/1/1978

接下來的問題是如何判斷一個點是否在給定直線的左側（或右側）？幾何學中有這樣一個定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三個點，則三角形p1p2p3的面積等于下面這個行列式的絕對值的一半：

當且僅當點p3=(x3,y3)位于直線p1p2的左側時，該式的符號為正?？梢栽谝粋€常數時間內檢查一個點是否位于兩個點確定的直線的左側，并且可以求得這個點到該直線的距離。311223321321332211111yxyxyxyxyxyxyxyxyx---++=凸包問題

第77頁/共97頁2023/1/1979復雜度的討論平均情況：O(nlog2n)最壞情況：O（n^2）蠻力法：O（n^3）凸包問題

第78頁/共97頁2023/1/1980本章要點5.1概

述

5.2遞

歸5.3排序問題中的分治法5.4組合問題中的分治法5.5幾何問題中的分治法5.6實驗項目——最近對問題第79頁/共97頁2023/1/19815.6實驗項目——最近對問題

1.實驗題目設p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個點構成的集合S，設計算法找出集合S中距離最近的點對。

2.實驗目的（1）進一步掌握遞歸算法的設計思想以及遞歸程序的調試技術；（2）理解這樣一個觀點：分治與遞歸經常同時應用在算法設計之中。3.實驗要求（1）分別用蠻力法和分治法求解最近對問題；（2）分析算法的時間性能，設計實驗程序驗證分析結論。

第80頁/共97頁2023/1/19825.6實驗項目——最近對問題

算法5.10——最近對問題

intClosePoint(S)//S為平面上n個點的坐標組成的集合

{1.if(n<2)return無大；

2.m=S中各點x坐標的中位數;3.構造S1和S2，使得S1中點的x坐標小于m，S2中點的x坐標大于m;4.d1=ClosePoints(S1);d2=ClosePoints(S2);5.d=min(d1,d2);6.構造P1和P2，使得P1是S1中點的x坐標與m的距離小于d的點集，P2是S2中點的x坐標與m的距離小于d的點集;7.將P1和P2中的點按y坐標升序排列;8.對P1中的每一個點P，在P2中查找與點p的y坐標小于d的點，并求出其中的最小距離d’;9.returnmind(d,d’);}C++描述第81頁/共97頁2023/1/1983大整數的乘法

請設計一個有效的算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2)效率太低分治法:abcd復雜度分析T(n)=O(n2)沒有改進X=Y=X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd第82頁/共97頁2023/1/1984大整數的乘法

請設計一個有效的算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd

為了降低時間復雜度，必須減少乘法的次數。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd復雜度分析T(n)=O(nlog3)=O(n1.59)較大的改進細節(jié)問題：兩個XY的復雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結果，使問題的規(guī)模變大，故不選擇第2種方案。第83頁/共97頁2023/1/1985大整數的乘法

請設計一個有效的算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2)效率太低分治法:O(n1.59)較大的改進更快的方法??如果將大整數分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導致了快速傅利葉變換(FastFourierTransform)的產生。該方法也可以看作是一個復雜的分治算法，對于大整數乘法，它能在O(nlogn)時間內解決。是否能找到線性時間的算法？？？目前為止還沒有結果。第84頁/共97頁2023/1/1986Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個元素所需的計算時間為O(n3)傳統(tǒng)方法：O(n3)第85頁/共97頁2023/1/1987Strassen矩陣乘法使用與上例類似的技術，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：傳統(tǒng)方法：O(n3)分治法:由此可得：第86頁/共97頁2023/1/1988復雜度分析T(n)=O(n3)沒有改進第87頁/共97頁2023/1/1989Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時間復雜度，必須減少乘法的次數。第88頁/共97頁2023/1/1990復雜度分析T(n)=O(nlog7)=O(n2.81)較大的改進第89頁/共97頁2023/1/1991Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81