【正文】 下角子棋盤 if (dr = tr + s dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s)。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。 } } void chessBoard(int tr, int tc,int dr, int dc,int size) { —— 《算法分析與設(shè)計》 55 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return。 覆蓋左下角 。 else { 在左下角放一小方塊 。 // 覆蓋左上角子棋盤 if ( 特殊方塊在左上角 ) 覆蓋左上角 。特殊方格必位于 4個較小子棋盤之一中，其余 3個 子棋盤中無特殊方格。如果把這個三格板看成三個殘缺格，原來的殘缺棋盤就可以分成 4個殘缺棋盤。 } 結(jié)論：較少乘法次數(shù)是 優(yōu)化算法的重要途徑。 k++) C[i][j] += A[i][k]*B[k][j]。 j n。因此，在最壞 情況下， while循環(huán)被執(zhí)行了 O(lgn) 次。 if (x a[middle]) left = middle + 1。 分治算法舉例 1：二分搜索技術(shù) 分析： —— 《算法分析與設(shè)計》 41 templat class T int binarySearch(T a[], int x, int n) { int left = 0。 結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。否則，將有某 些元素找不到位臵。 p[i] = 0。 } else { for (int i = 1。 ② 將 n放在 p[2]位臵上，并用 p[1]和 p[3..n]產(chǎn)生 n1個元素的全排列； —— 《算法分析與設(shè)計》 35 321, 312, 231, 132, 213, 123 —— 《算法分析與設(shè)計》 36 void perm2(int p[], int n) { // n = NUM1 // p[1]~p[n]放臵元素，初始為 0， // n為當前參與排列的元素數(shù)量 , 1,2,3,……, n if (參與排列的數(shù)據(jù)數(shù)量為 0) { 輸出結(jié)果 } else { 依次將 n放在每個位臵， 并采用同樣的方法求解另外 n1元素的全排列； } } —— 《算法分析與設(shè)計》 37 void perm2(int p[], int n) { if (n == 0) { // 元素集合為空 for (int i = 1。 // 交換 r[i]與 r[j] perm(r, i + 1, n)。 } coutendl。 P[m]，如果能夠求出剩余元 P[m+1] 、 P[m+2] 、 … ， P[n] 的所有排列，我們只需將 P[m]放到每個排列的開頭。 舉例， 0~3共 4個數(shù)值的全排列 思路？ —— 《算法分析與設(shè)計》 30 假設(shè) : 要求 P[m] 、 P[m+1] 、 … P[n] 的全排列 : ，將 P[m]和某個 P[k]交換，求出剩余元素的所有排列后，為 了避免重復(fù)，發(fā)生混亂，必須將 P[m] 和 P[k]交換回去，然后才能繼續(xù) P[m] 和 P[K+1]的交換。 解題基本方法： （ 1）固定位臵放元素 （ 2）固定元素找位臵 —— 《算法分析與設(shè)計》 26 假設(shè) R={r1,r2,…,r n}是待排列的 n個元素， Ri=R{ri}。遞歸定義為： —— 《算法分析與設(shè)計》 23 A(1,0) = 2 A(0,m) = 1 m≥0 A(n,0) = n + 2 n≥2 A(n,m) = A(A(n1,m),m1) n,m≥1 遞歸應(yīng)用舉例 2: Ackerman函數(shù) —— 《算法分析與設(shè)計》 24 m=2時， A(n,2)=A(A(n1,2),1)=2A(n1,2)， A(1,2)=A(A(0,2),1)=A(1,1)=2 可以得出 A(n,2)= 2n 。 在定義函數(shù)時調(diào)用到函數(shù)自身稱為 遞歸函數(shù) 。分別遞歸地解決 a個子問題，解每個子問題所需時間為 T(n/b)。 14 ?遞歸樹總共有多少層？當遞歸樹展開一層，其規(guī)模為 n/4，當遞歸樹展開到第 2層時，其規(guī)模為n/16=n/42，依次類推，當展開到第 k層時，其規(guī)模為 n/4k=1時，不再展開，由此可以求得遞歸樹的層數(shù)為 k=log4n。 數(shù)學歸納法： v 猜測出解為 T(n)=O(nlgn) v 證明存在某個常數(shù) c，使得 T(n) ≤lgn —— 《算法分析與設(shè)計》 11 遞歸樹方法 ? 構(gòu)造遞歸樹的方法就是展開遞歸方程，然后將樹中每層的時間求和，最終獲得算法的時間復(fù)雜性。用 T(n)表示該分治算法解規(guī)模為 |P|=n的問題所需的計算時間，則有下列遞歸方程： ( 1 ) 1()( ) ( ) 1OnTnaT n b f n n???? ???通過求解遞歸方程得到遞歸算法的時間復(fù)雜性。//遞歸的 求解 各子問題 return merge(y1,...,ya)。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解 。—— 《算法分析與設(shè)計》 1 第 2講分治與遞歸策略 ? 分治算法的基本思想 ? 遞歸概念 ? 典型分治算法舉例 —— 《算法分析與設(shè)計》 2 算法總體思想 將一個難以直接解決的規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，并 各個擊破，分而治之 。 —— 《算法分析與設(shè)計》 4 分治算法的基本思想 分治算法的基本思想是將一個規(guī)模為 n的問題分解為 a個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。 //解決規(guī)模小的問題 //將問題 P 分解 為子問題 P1,P2,...,Pa； for (i=1,i=a,i++) yi=divideandconquer(Pi)。再設(shè)將原問題分解為 a個子問題以及用 merge將 a個子問題的解合并為原問題的解需用 f(n)個單位時間。 ① 猜測出遞歸解的形式 ② 用數(shù)學歸納法找出使解真正有效的常數(shù) ? 替換方法解遞歸方程的基本步驟： —— 《算法分析與設(shè)計》 10 例： T(n)=2T(n/2)+n （ 2路歸并 ) 假設(shè)解對 n/2成立，即 T(n/2) ≤c(n/2)lg(n/2) 將其對遞歸方程進行替換，得： T(n)= 2T(n/2)+n ≤2(c(n/2)lg(n/2))+n ≤lg(n/2)+n ≤lgn lg2+n = lgn+n 當 c≥1 時，顯然 lgn+n ≤lgn 根據(jù) O符號定義，證明猜測正確。第 1層有 3個節(jié)點，第 2層有 32個節(jié)點，依次類推，第 k層有3k個節(jié)點，當 k=log4n，即為葉節(jié)點，因此，葉節(jié)點的個數(shù)為 ，而每個葉節(jié)點需要的時間為 T(1),因此，整個葉節(jié)點的時間為 。 n/b可以是 ，也可以是 ( 1 ) 1()( ) ( ) 1OnTnaT n b f n n???? ???? ?bn/? ?bn/公式法 上述方程描述了如下算法的運行時間：將一個規(guī)模為 n的問題劃分為 a個規(guī)模為 n/b的子問題，其中 a和 b為正常數(shù)。 n ablogablogn ablog—— 《算法分析與設(shè)計》 19 例 1： T(n)=9T(n/3)+n 由上式可知， a = 9， b = 3， f(n) = n, 且 又因為對于 有 滿足定理（ 1），因此， )( 229loglog 3 nOnnn ab ???1?? )()( 9log 3nOnf ??? )()( 2nnT ??—— 《算法分析與設(shè)計》 20 例 2： T(n) = T(2n/3)+1 由上式可知 a=1, b=3/2, f(n)=1， 且 又因為 滿足定理（ 2），因此 )(lg)( nnT ??—— 《算法分析與設(shè)計》 21 遞歸概念 分治算法 遞歸技術(shù) 直接或間接地調(diào)用自身的算法稱為 遞歸算法 。 無窮 2階數(shù)列 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， … ，被稱為 Fibonacci數(shù)列。 n個元素的全排列有 n!種可能。 當 n=1時， perm(R)=(r) 其中 r是集合 R中唯一的元素； 當 n1時， perm(R)的全排列為： (r1)perm(R1)， (r2)perm(R2)， … ， (rn)perm(Rn) 方法 1：固定位臵找元素 —— 《算法分析與設(shè)計》 27 遞歸公式 —— 《算法分析與設(shè)計》 28 —— 《算法分析與設(shè)計》 29 將每個元素交換 到固定位臵上， 并求解其余位臵 元素的全排列。 P[m+1]，通過交換 P[m]和 P[m+1]，這樣我