計(jì)算理論與算法分析設(shè)計(jì)：CH2 分治法

CH2分治法

2022/11/62of158二分法2022/11/63of158為什么要用二分法用枚舉的方法求解，需要對(duì)所有解都遍歷一次，時(shí)間復(fù)雜度為O(n)用二分法，每進(jìn)行一次運(yùn)算，能將解的范圍縮小一半，時(shí)間復(fù)雜度為O(logn)2022/11/64of158使用二分法的條件解具有遞增（或遞減）的特性對(duì)于某個(gè)值不是問題的解，那么比這個(gè)值大（或?。┑闹稻皇菃栴}的解2022/11/65of158程序的一般形式While(min<max){ mid=(min+max)/2; if(與mid有關(guān)的條件) min=mid+1; elsemax=mid;}2022/11/66of158第一類問題求一個(gè)問題的解:連續(xù)、離散……2022/11/67of158第一類問題:求方程的解（2，3）（2.5，3）（2.5，2.75）（2.5，2.5625）（2.53125，2.5625）（2.53125，2.546875）2.52.752.6252.56252.531252.546875（2.5，2.625）2.5390625-0.0840.5120.2150.066-0.0090.0290.010(精確度為0.01)2022/11/68of158第一類問題:折半查找給定一個(gè)有序的數(shù)列，判斷某個(gè)數(shù)是否在數(shù)列中161522274851556071minmaxmid2022/11/69of158二分查找法（也稱為折半查找法）基本步驟：將給定值與查找范圍中間位置的記錄比較：

給定值＜中間位置：繼續(xù)在前半個(gè)表中查找

=

：查找成功，返回記錄位置

＞：繼續(xù)在后半個(gè)表中查找2022/11/610of158L=(3,12,24,37,45,53,61,78,90,100)，查找Key=24的記錄

12345678910

31224374553617890100lowmid

high12345678910

3122437

4553617890100lowmidhigh24＜

45繼續(xù)在前半個(gè)表中用二分查找法查找

12345678910312

2437

4553617890100Lowmidhigh24＞

12繼續(xù)在后半個(gè)表中用二分查找法查找查找成功mid=(low+high)/22022/11/611of158第二類問題求一個(gè)問題的最優(yōu)解：最大、最小……2022/11/612of158第二類問題:分割電纜現(xiàn)給出4根電纜，長(zhǎng)度分別為8.02、7.43、

4.57、

5.39，要你把它們分割成11根等長(zhǎng)的電纜，每根電纜的最大長(zhǎng)度是多少？2022/11/613of158

基本思想：將問題分解成若干個(gè)子問題，然后求解子問題，由此得到原問題的解。即“分而治之”

divide-and-conquer

把輸入分成與原問題類型相同的多個(gè)子問題2022/11/614of158問題分解子問題分解

基本問題

求解

基本問題解

合并子問題解

合并

問題解2022/11/615of158分治法是一個(gè)遞歸地求解問題的過程分治法在每一層遞歸上有三個(gè)步驟分解:通過某種方法,將原問題分解成若干個(gè)規(guī)模較小,相互獨(dú)立,與原問題形式相同的子問題解決:若子問題規(guī)模小到可以直接解決(稱為基本問題),則直接解決,否則把子問題進(jìn)一步分解，遞歸求解合并:通過某種方法,將子問題的解合并為原問題的解2022/11/616of158分治法的抽象過程divide-and-conquer(S){if(small(S))return(adhoc(S));divideSintosmallersubsetS1,S2,…,Si,…Sk;for(i=1;i<=k;i++)yi

←divide-and-conquer(Si);returnmerge(y1,y2,…,yi,…,yk);}2022/11/617of158分治法的適用條件適合用分治法解決的問題的一些特征:1問題規(guī)?？s小到一定程度就可以容易解決2問題可以分解為若干個(gè)規(guī)模小，和原問題形式相同的子問題3利用子問題的解可以合并出原問題的解4分解出的子問題是相互獨(dú)立的,即子問題之間不包含公共的子子問題2022/11/618of158例1用分治法求n個(gè)元素集合S中的最大、最小元素。假設(shè)n=2m。要求每次平分成2個(gè)子集。voidmaxmin(intA[],int&e_max,int&e_min,intlow,inthigh)2.{3.intmid,x1,y1,x2,y2;4.if((high-low<=1)){5.if(A[high]>A[low]){6.e_max=A[high];7.e_min=A[low];8.}

特征1：

小到容易求解9.else{10.e_max=A[low];11.e_min=A[high];12.}13.}2022/11/619of15814.else{15.mid=(low+high)/2;16.maxmin(A,x1,y1,low,mid);17.maxmin(A,x2,y2,mid+1,high);18.e_max=max(x1,x2);19.e_min=min(y1,y2);20.}21.}特征2：

可分解特征4：

子問題獨(dú)立特征3：

可合并T(n)=1n=2n>22T(n/2)+22022/11/620of158方法二:迭代法T(n)=2T(n/2)+2=2[2T(n/22)+2]+2=22T(n/22)+2(1+2)=23T(n/23)+2(1+2+22)=…=2m-1T(2)+2(1+2+…n=2m+2m-2)=2m-1+2[1(1-2m-1)/(1-2)]=2m-1+2m-2=3n/2-22022/11/621of158課堂練習(xí)T(n)=3T(n/2)T(1)=1n=2m

T(n)=3log2n2022/11/622of158答案T(n)=3T(n/2)T(n)=1=3T(2k-1)=32T(2k-2)=…=3kT(2k-k)n=2k=3kT(1)=3kk=log2n2022/11/623of158課堂練習(xí)

用分治法求n個(gè)元素集合S中的最大、最小元素。寫出算法，并分析時(shí)間復(fù)雜性（比較次數(shù)）。假設(shè)n=3m。要求每次平分成3個(gè)子集。T(n)=n=3n>33T(n/3)+43T(n)=5n/3-2平分成2個(gè)子集T(n)

=3n/2-22022/11/624of158思考題

不用（遞歸的）分治法求n個(gè)元素集合S中的最大、最小元素，使得

T(n)仍為3n/2-2。這里假設(shè)n=2m。2022/11/625of158歸并排序前言歸并---合并兩個(gè)有序的序列假設(shè)有兩個(gè)已排序好的序列A（長(zhǎng)度為n1），B（長(zhǎng)度為n2），將它們合并為一個(gè)有序的序列C（長(zhǎng)度為n=n1+n2)把A，B兩個(gè)序列的最小元素進(jìn)行比較，把其中較小的元素作為C的第一個(gè)元素；在A，B剩余的元素中繼續(xù)挑最小的元素進(jìn)行比較，確定C的第二個(gè)元素，依次類推，就可以完成對(duì)A和B的歸并，其復(fù)雜度為bn，即O(n)。2022/11/626of158歸并排序前言歸并---合并兩個(gè)有序的序列A:138911B:2571013C:1

2

3

5

7

8

9

10

11

132022/11/627of158歸并排序前言voidmerge(TA[],intAlen,TB[],intBlen,TC[]){inti=0,j=0,k=0;while(i<Alen&&j<Blen){if(A[i]<B[j]) C[k++]=A[i++]; else C[k++]=B[j++];} while(i<Alen) C[k++]=A[i++]; while(j<Blen) C[k++]=B[j++];}2022/11/628of158歸并排序（MergeSort)歸并排序是一個(gè)分治遞歸算法遞歸基礎(chǔ)：若序列只有一個(gè)元素，則它是有序的，不執(zhí)行任何操作遞歸步驟：先把序列劃分成長(zhǎng)度基本相等的兩個(gè)序列對(duì)每個(gè)子序列遞歸排序把排好序的子序列歸并成最后的結(jié)果2022/11/629of158歸并排序（MergeSort)歸并排序初始序列：[8，4，5，6，2，1，7，3]分解：[8][4][5][6][2][1][7][3]歸并：[4，8][5，6][1，2][3，7]歸并：[4，5，6，8][1，2，3，7]歸并：[1，2，3，4，5，6，7，8]分解：[8，4，5，6][2，1，7，3]分解：[8，4][5，6][2，1][7，3]2022/11/630of158歸并排序（MergeSort)voidMergeSort(intA[],intB[],intl,inth){ if(l==h) return; intm=(l+h)/2; MergeSort(A,B,l,m); MergeSort(A,B,m+1,h); Merge(A,B,l,m,h);}T(n)=n=2n>22T(n/2)+cn12022/11/631of158方法三:主定理

設(shè)a≥1和b>1為常數(shù),設(shè)f(n)為函數(shù),T(n)由遞歸式

T(n)

=

aT(n/b)

+f(n)

對(duì)自然數(shù)定義,其中n/b指n/b或n/b.則

若對(duì)于某常數(shù)ε>0,有則T(n)

=

若

則T(n)

=

若對(duì)于某常數(shù)ε>0,有且對(duì)常數(shù)c<1與所有足夠大的n,有

af(n/b)≤cf(n),則T(n)

=2022/11/632of158主定理簡(jiǎn)化版T(n)=n=2n>2aT(n/c)+bnxdT(n)=a<cx(nxlogn)(nx)a=cxa>cxT(n)=n=2n>22T(n/2)+cn1歸并排序

(nlogn)T(n)=1n=2n>22T(n/2)+22022/11/633of158T(n)=aT(n/c)+bn(即x=1)一個(gè)問題平分為兩個(gè)子問題T(n)=a<c(nlogn)(n)a=ca>c(nlogn)子問題的大小還是n/2，而子問題的

個(gè)數(shù)是3、4或者8(n2)(n3)2022/11/634of158大整數(shù)乘法在某些情況下，我們要處理很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。若用浮點(diǎn)數(shù)來(lái)表示它，則只能近似地表示它的大小，計(jì)算結(jié)果中的有效數(shù)字也受到限制。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。2022/11/635of158普通遞歸乘法的分析設(shè)X,Y是n位二進(jìn)制整數(shù)，分段表示如下：即X=A2n/2+B,Y=C2n/2+D

則XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD計(jì)算成本：4次n/2位乘法，3次不超過n位加法，2次移位，所有加法和移位共計(jì)O(n)次運(yùn)算。我們有T(n)=O(n2)1n=14T(n/2)+O(n)n>1T(n)=2022/11/636of158改進(jìn)的分治算法(1962年)

由X=A2n/2+B,Y=C2n/2+D則

XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+BC)2n/2+BD=AC2n+((A-B)(D-C)+AC+BD)2n/2+BD計(jì)算成本：3次n/2位乘法，6次不超過n位加減法，2次移位，所有加法和移位共計(jì)O(n)次運(yùn)算。由此可得，T(n)=O(nlog3)=O(n1.59)這種思想同樣可以用于十進(jìn)制數(shù)的乘法中。1n=13T(n/2)+cnn>1T(n)=2022/11/637of158

改進(jìn)的分治算法舉例：十進(jìn)制數(shù)的乘法已知X=2368，y=3925，求XY解：取基d=10,A=23,B=68,C=39,D=25,則①AC=23×39=897②BD=68×25=1700③(A-B)(D-C)+AC+BD=(23-68)(25-39)+897+1700=45×14＋897＋1700=3227

∴XY=1700+3227×102＋897×104＝92944002022/11/638of158Strassen矩陣乘法普通矩陣乘法設(shè)n×n階矩陣A和B，計(jì)算C=A×B求C=AB即對(duì)n2個(gè)元素cij進(jìn)行計(jì)算，故要作n3次乘法。相當(dāng)長(zhǎng)時(shí)間內(nèi)沒有人懷疑過是否可以用少于n3次乘法來(lái)完成。2022/11/639of158以n=2為例的普通矩陣乘法設(shè)則有共需8次乘法2022/11/640of158-將C=A×B寫為2×2的分塊矩陣：-Strassen提出的算法如下：令P=(A11+A22)(B11+B22),Q=(A21+A22)B11R=A11(B12-B22),S=A22(B21-B11)T=(A11+A12)B22,U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)

則

C11=P+S-T+V,C12=R+TC21=Q+S,C22=P+R-Q+U

乘法次數(shù)從8次減為7次。Strassen的分治算法(1969)2022/11/641of158時(shí)間分析：用了7次對(duì)于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運(yùn)算。由此可知，該算法的所需的計(jì)算時(shí)間T(n)滿足如下的遞歸方程:=>T(n)=O(nlog7)≈O(n2.81)-評(píng)注.有人提出了計(jì)算2×2階矩陣乘法的36種不同方法，都要做7次乘法.Hopcroft和Kerr(1971)已經(jīng)證明，7次乘法是必要的；.應(yīng)當(dāng)研究3×3或5×5矩陣的更好算法；.目前最好的計(jì)算時(shí)間上界是O(n2.367)，而最好下界仍是Ω(n2)。2022/11/642of158快排序:介紹快速排序算法是于1962年由英國(guó)的TonyHoare提出的，并于1980年獲得TuringAwards最壞運(yùn)行時(shí)間:(n2)平均運(yùn)行時(shí)間:(nlogn)－實(shí)際運(yùn)行效果最好的排序算法－在(nlogn)中的常數(shù)因子非常小2022/11/643of158快排序（QuickSort)快排序—算法思想取序列的一個(gè)元素作為軸，利用這個(gè)軸把序列分成三段：左段，中段(軸),和右段,使左段中各元素都小于等于軸，右段中各元素都大于等于軸。(這個(gè)過程稱做對(duì)序列的劃分)左段和右段的元素可以獨(dú)立排序,將排好序的三段合并到一起即可上面的過程可以遞歸地執(zhí)行，直到每段的長(zhǎng)度為12022/11/644of158快排序—算法思想

快速排序?qū)嵗?022/11/645of158快排序---劃分過程快排序是一個(gè)分治算法快排序的關(guān)鍵過程是每次遞歸的劃分過程劃分問題描述：對(duì)一個(gè)序列，取它的一個(gè)元素作為軸，把所有小于軸的元素放在它的左邊，大于它的元素放在它的右邊2022/11/646of158劃分算法：用臨時(shí)變量對(duì)軸備份取兩個(gè)指針low和high，它們的初始值就是序列的兩端下標(biāo)，在整個(gè)過程中保證low不大于high移動(dòng)兩個(gè)指針首先從high所指的位置向左搜索，找到第一個(gè)小于軸的元素,把這個(gè)元素放在low的位置再?gòu)膌ow開始向右，找到第一個(gè)大于軸的元素，把它放在high的位置重復(fù)上述過程，直到low=high，把軸放在low所指的位置2022/11/647of158快排序---劃分過程

3865977613274949lowhighpivot=49

01234567high38659776134927low27389776134965high27389776654913low27381376654997high49=low2022/11/648of158快排序---劃分過程

intPartition(Array[],intlow,inthigh){pivot=Array[low]; while(low<high){

while(low<high&&Array[high]>=pivot) high--;Array[low]=Array[high]; while(low<high&&Array[low]<=pivot) low++;Array[high]=Array[low];}

Array[low]=pivot;returnlow;}2022/11/649of158快排序---算法voidQuickSort(TArray[],intlow,inthigh){ intPivotLocation; if(low<high){ PivotLocation=Partition(Array,low,high);QuickSort(Array,low,PivotLocation-1);QuickSort(Array,PivotLocation+1,high); }}2022/11/650of158算法分析最壞情況：12345671

23456712

3456712

34567當(dāng)需要排序的序列已經(jīng)有序時(shí)，快排序需要做n-1次劃分，每次劃分需要的比較次數(shù)依次為n-1,n-2,…,1.所以在這種情況下，快排序的時(shí)間復(fù)雜度為2022/11/651of158最好情況如果每次劃分過程產(chǎn)生的區(qū)間大小都為n/2，這時(shí)有：T(n)=2T(n/2)+θ(n)

T(1)=0nn/2n/2n/4n/4n/4n/4n/8n/8n/8n/8n/8n/8n/8n/8log2nnBestCaseComplexity

nlognT(n)=O(nlogn)a=c2022/11/652of158算法優(yōu)化

軸的選擇基本快排序算法選擇序列的第一個(gè)元素為軸，當(dāng)軸使每次劃分后的兩個(gè)子序列長(zhǎng)度接近時(shí)，算法效率很高，如果偏向某一邊，則效率偏低為了打破極端偏向某一邊，可以用其他策略選擇軸在序列中隨機(jī)選擇一個(gè)元素作為軸選擇Array[0],Array[n-1],Array[(n-1)/2]三個(gè)數(shù)

的中間值作為軸2022/11/653of158算法優(yōu)化短序列排序：快排序?qū)π蛄虚L(zhǎng)度較大時(shí)很有效，但當(dāng)序列較短時(shí)則效率不高，因?yàn)榭炫判蚴莻€(gè)遞歸算法，需要大量子過程調(diào)用可以做如下改進(jìn)：當(dāng)序列長(zhǎng)度較大時(shí)采用快排序算法。當(dāng)序列長(zhǎng)度被劃分到小到一定長(zhǎng)度時(shí)，采用較直接的算法（如插入排序）2022/11/654of158快排序（QuickSort)算法評(píng)論：對(duì)很長(zhǎng)的序列來(lái)說，快速排序的平均性能最好。因此在很多軟件，比如數(shù)據(jù)庫(kù)系統(tǒng)中經(jīng)常使用2022/11/655of158線性時(shí)間選擇問題:

用線性時(shí)間從n個(gè)不同的元素中選擇出第k個(gè)小的元素2022/11/656of158求最小元素算法intFindMin(Array[],intLen){intMinIndex=1;for(inti=2;i<=Len;i++){if(Array[MinIndex]>Array[i])MaxIndex=i;}returnMinIndex;}2022/11/657of158最小問題問題下界：假設(shè)集合中元素是互不相同的。則n-1個(gè)元素不是最大元素。對(duì)某一個(gè)元素，只有它在某一次比較中失敗了，才能確定它不是最大元素。因此，有n-1個(gè)元素在某次失敗每一次比較只能確定一個(gè)失敗者，確定n-1個(gè)在某次比較中的失敗者需要n-1次比較確定最大元素至少需要n-1次比較，n-1次比較是最大問題的下界前面算法的比較次數(shù)是n-1次，達(dá)到問題

的下界，因此它是最優(yōu)算法2022/11/658of158求第2小的元素一般情況下2n-3次比較第2小元素一定存在于同最小元素比較過的元素之中181363272454112

個(gè)元素同最小元素比較過找第2小的元素共需比較次數(shù)n－1+－12022/11/659of158筆試題在中國(guó)的古代，25匹馬通過賽跑來(lái)決出前3名，每5匹馬一組，問最少需要幾組？5組從快到慢ABCDEDCAEB由快到慢2022/11/660of158求第k小的元素算法的基本思想按某個(gè)元素m將S中的元素劃分成小于m、等于m和大于m的三個(gè)子序列S1，S2和S3。

只要計(jì)算一下這三個(gè)集合的元素個(gè)數(shù)，就能確定第k小元素在哪個(gè)子集中。這樣就把在S中找第k小元素的問題轉(zhuǎn)化成在S的某個(gè)子集中找某個(gè)元素的問題。遞歸地運(yùn)用這一方法，就可找出S中第k小元素。2022/11/661of158求第k小的元素longSelect(k,S){if(|S|≤38){將S中的元素排成非遞減序；

return(S中的第k小元素);}else

{

將S中的元素劃分成長(zhǎng)度等于5的

|S|/5

個(gè)子序列；2022/11/662of158

由各子序列的中值元素組成非遞減序列M；

m←Select(|M|/2

，M);

按m將S中的元素劃分成小于m、等于

m和大于m的三個(gè)子序列S1，S2和S3;if(|S1|≥k)return(Select(k,S1));elseif(|S1|+|S2|≥k)return(m);elsereturn(Select(k-|S1|-|S2|,S3));}}2022/11/663of158按遞增順序，找出下面29個(gè)元素的第18小元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29。前面25個(gè)元素劃分為5組：(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7)，其余4個(gè)元素暫不處理；

提取每一組的中值元素，構(gòu)成集合：（31,49,13,25,16）；m＝25；

{8,17,4,11,3,13,6,19,16,5,7,23,22}，13

{25}，1

{31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}；

152022/11/664of158求第k個(gè)小的元素（選擇問題）m中值序列M

從小到大已知小于或者等于m的元素已知大于或者等于m的元素按m將S中的元素劃分成小于m、等于m和大于m的三個(gè)子序列S1，S2和S3;從小到大2022/11/665of158定理：算法Select在O(n)時(shí)間內(nèi)找出n個(gè)元素序列中的第k小的元素。cn≤38T(n/5)+T(3n/4)+cnn>38T(n)≤T(n)=O(n)2022/11/666of158遞歸樹:例1T(n)=n=2n>22T(n/2)+cn(1)2022/11/667of158遞歸樹

歸并排序(nlgn)T(n)=n=2n>22T(n/2)+cn(1)2022/11/668of158遞歸樹:例2T(n)=3T(n/4)+cn2

2022/11/669of158遞歸樹T(n)=3T(n/4)+cn2

2022/11/670of158遞歸樹T(n)=3T(n/4)+cn2

2022/11/671of158遞歸樹:例3T(n)=T(n/3)+T(2n/3)+O(n)=T(n/3)+T(2n/3)+cn2022/11/672of158選擇問題的應(yīng)用之一用選擇算法找中位數(shù)作為劃分標(biāo)準(zhǔn)，保證快速排序算法的子問題均衡,使得快速排序算法最壞情況復(fù)雜性為O(nlogn)。2022/11/673of158線性時(shí)間選擇:中位數(shù)引例某公司有五個(gè)分公司依次設(shè)置在同一條鐵路線的沿線A、B、C、D、E站?，F(xiàn)在該公司希望在該鐵路沿線設(shè)立一個(gè)倉(cāng)庫(kù)，要求該倉(cāng)庫(kù)離這五個(gè)站的火車行駛距離之和最小。如用數(shù)軸表示該鐵路線，A、B、C、D、E各站的坐標(biāo)依次為a、b、c、d、e（a<b<c<d<e），則經(jīng)過數(shù)學(xué)計(jì)算，該倉(cāng)庫(kù)大致應(yīng)設(shè)置在坐標(biāo)

（1）處。（1）A.cB.(a+b+c+d+e)/5C.(a+2b+3c+2d+e)/9

D.(a+4b+6c+4d+e)/162022/11/674of158【例】殘缺棋盤殘缺棋盤是一個(gè)有2k×2k

（k≥1）個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。圖中給出k=1時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。

稱作“三格板”，殘缺棋盤問題就是要用這四種三格板覆蓋更大的殘缺棋盤。①號(hào)②號(hào)③號(hào)④號(hào)2022/11/675of158在此覆蓋中要求：1）兩個(gè)三格板不能重疊2）三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格在這種限制條件下，所需要的三格板總數(shù)為(2k×2k-1)/3。2022/11/676of158問題分解過程：以k=2時(shí)的問題為例，用二分法進(jìn)行分解，得到如下圖，用雙線劃分的四個(gè)k=1的棋盤。①號(hào)②號(hào)③號(hào)④號(hào)2022/11/677of1582022/11/678of158棋盤的識(shí)別棋盤的規(guī)模是一個(gè)必要的信息，有了這個(gè)信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個(gè)棋盤了，殘缺方格或“偽”殘缺方格直接用行、列號(hào)記錄。?tr棋盤中左上角方格所在行。?tc棋盤中左上角方格所在列。?dr殘缺方塊所在行。?dl殘缺方塊所在列。?size棋盤的行數(shù)或列數(shù)。2022/11/679of158數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：用二維數(shù)組board[][]，模擬棋盤。覆蓋殘缺棋盤所需要的三格板數(shù)目為：(size2-1)/3將這些三格板編號(hào)為1到(size2-1)/3。則將殘缺棋盤三格板編號(hào)的存儲(chǔ)在數(shù)組board[][]的對(duì)應(yīng)位置中，這樣輸出數(shù)組內(nèi)容就是問題的解。2022/11/680of158Cover(inttr,inttc,intdr,intdc,intsize){if(size<2)return;intt=amount++,//三格板的數(shù)目

s=size/2;

//子問題棋盤大小

if(dr<tr+s&&dc<tc+s)//殘缺方格位于左上棋盤｛Cover(tr,tc,dr,dc,s);Board[tr+s-1][tc+s]=t;

//覆蓋１號(hào)三格板

Board[tr+s][tc+s-1]=t;Board[tr+s][tc+s]=t;Cover(tr,tc+s,tr+s-1,tc+s,s);//覆蓋其余部分

Cover(tr+s,tc,tr+s,tc+s-1,s);Cover(tr+s,tc+s,tr+s,tc+s,s);｝復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法2022/11/681of158循環(huán)賽日程表n=2k個(gè)選手設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。2022/11/682of158循環(huán)賽日程表加4加2(a)2k(k=1)個(gè)選手比賽122112213443344312211234214334124321567865877856876556786587785687651234214334124321(b)2k(k=2)個(gè)選手比賽(c)2k(k=3)個(gè)選手比賽2022/11/683of158循環(huán)賽日程表12345678214365873412785643218765567812346587214378563412876543212022/11/684of158循環(huán)賽日程表的推廣設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)n為偶數(shù)時(shí)，循環(huán)賽一共進(jìn)行n-1天。

n為奇數(shù)時(shí)，循環(huán)賽一共進(jìn)行n天。1234第1天第2天第3天2022/11/685of1581234第1天第2天第3天123第1天第2天第3天2022/11/686of158123第1天21-第2天3-1第3天-32123456第1天第2天第3天第4天第5天2022/11/687of15812345第1天21-54第2天351-2第3天4321-第4天5-431第5天-45232022/11/688of15812345678910第1天21854763109第2天35192810647第3天43211098765第4天57431102986第5天64523191078第6天78910651234第7天89106745123第8天91067834512第9天106789234512022/11/689of158最大子段和例如，(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)

最大子段和為給定整數(shù)序列a1,a2,…,an，求形如的子段和的最大值。規(guī)定子段和為負(fù)整數(shù)時(shí)，定義其最大子段和為0，即2022/11/690of1581可以把所有的子段和計(jì)算出來(lái)，找到最小的2找到所有子段算法：每個(gè)子段有一個(gè)起點(diǎn)i和一個(gè)終點(diǎn)j

把起點(diǎn)位置i從左到右進(jìn)行掃描確定起點(diǎn)后，把終點(diǎn)位置j，左到右進(jìn)行掃描，確定起點(diǎn)終點(diǎn)后，把這個(gè)子段中所元素相加（i,i+1,…,j),2022/11/691of158intMaxSubSum1(intn,inta[],int&besti,int&bestj){//數(shù)組a[]存儲(chǔ)ai，返回最大子段和，保存起止位置到Besti,Bbestj中

intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(intk=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}算法：T(n)=O(n3);

2022/11/692of158intMaxSubSum2(intn,inta[],int&besti,int&bestj){//數(shù)組a[]存儲(chǔ)ai，返回最大子段和，保存起止位置到Besti,Bbestj中

intsum=0;for(inti=1;i<=n;i++){ intthissum=0;for(intj=i;j<=n;j++){ thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}改進(jìn)算法：T(n)=O(n2);

2022/11/693of158最大子段和:分治算法基本思想將A[1..n]分為a[1..n/2]和a[n/2+1..n]，分別對(duì)兩區(qū)段求最大子段和，這時(shí)有三種情形：Case1：a[1..n]的最大子段和的子段落在a[1..n/2]；Case2：a[1..n]的最大子段和的子段落在a[n/2..n]；Case3：a[1..n]的最大子段和的子段跨在a[1..n/2]和a[n/2..n]之間；2022/11/694of158對(duì)Case1和Case2可遞歸求解；對(duì)Case3，可知a[n/2]和a[n/2+1]一定在最大和的子段中，因此在a[1..n/2]中計(jì)算：在a[n/2..n]中計(jì)算：易知：S1+S2是Case3的最大值2022/11/695of158intMaxSubSum3(inta[],intleft,intright){//返回最大子段和

intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum3(a,left,center);intrightsum=MaxSubSum3(a,center+1,right);ints1=0;intleftmidsum=0;for(inti=center;i>=left;i--){leftmidsum+=a[i];if(leftmidsum>s1)s1=leftmidsum;}2022/11/696of158ints2=0;intrightmidsum=0;for(inti=center+1;i<=right;i++){rightminsum+=a[i];if(rightmidsum>s2)s2=rightmidsum;}intsum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}//endifreturnsum;}//end2022/11/697of158Haveyoueverplayedquoitinaplayground?Quoitisagameinwhichflatringsarepitchedatsometoys,withallthetoysencircledawarded.

InthefieldofCyberground,thepositionofeachtoyisfixed,andtheringiscarefullydesignedsoitcanonlyencircleonetoyatatime.Ontheotherhand,tomakethegamelookmoreattractive,theringisdesignedtohavethelargestradius.Givenaconfigurationofthefield,youaresupposedtofindtheradiusofsucharing.

Assumethatallthetoysarepointsonaplane.Apointisencircledbytheringifthedistancebetweenthepointandthecenteroftheringisstrictlylessthantheradiusofthering.Iftwotoysareplacedatthesamepoint,theradiusoftheringisconsideredtobe0.2022/11/698of158最接近點(diǎn)對(duì)問題給定平面上n個(gè)點(diǎn)的集合，在這n個(gè)點(diǎn)組成的點(diǎn)對(duì)中，尋找距離最近的點(diǎn)對(duì)問題。假設(shè)兩點(diǎn)p1=(x1,y1)以及p2=(x2,y2)

，則之間的距離定義為：n個(gè)點(diǎn)可以組成n(n-1)/2個(gè)點(diǎn)對(duì)，所以需要花費(fèi)O(n2)。2022/11/699of158最接近點(diǎn)對(duì)問題為易于理解和分析，先考慮一維的情形。此時(shí)，S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)