【正文】 骨牌覆蓋左上角 board[tr + s][tc + s] = t。 // 覆蓋其余方格 chessBoard(tr+s, tc, tr+s, tc+s1, s)。} // 覆蓋左下角子棋盤 if (dr = tr + s dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s)。 else {// 此棋盤中無特殊方格 // 用 t 號(hào) L型骨牌覆蓋左下角 board[tr + s 1][tc + s] = t。 // 覆蓋其余方格 chessBoard(tr, tc, tr+s1, tc+s1, s)。 // 分割棋盤 // 覆蓋左上角子棋盤 if (dr tr + s dc tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s)。 } } void chessBoard(int tr, int tc,int dr, int dc,int size) { —— 《算法分析與設(shè)計(jì)》 55 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return。 else { 在左上角放一小方塊 。 覆蓋左下角 。 } // 覆蓋左下角子棋盤 if ( 特殊方塊在左下角 ) 覆蓋左下角 。 else { 在左下角放一小方塊 。 覆蓋左上角 。 // 覆蓋左上角子棋盤 if ( 特殊方塊在左上角 ) 覆蓋左上角 。遞歸地使用這種分割，直至棋盤 簡化為棋盤 ,即 k=0,1 1。特殊方格必位于 4個(gè)較小子棋盤之一中，其余 3個(gè) 子棋盤中無特殊方格。 ? 當(dāng)殘缺棋盤的規(guī)模降為 2*2時(shí)，這時(shí)棋盤不再分解，遞歸終 止，因?yàn)檫@時(shí)殘缺棋盤只要放臵一個(gè)三格板就可以鋪滿。如果把這個(gè)三格板看成三個(gè)殘缺格，原來的殘缺棋盤就可以分成 4個(gè)殘缺棋盤。 在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個(gè)L型骨牌不得重疊覆蓋。 } 結(jié)論：較少乘法次數(shù)是 優(yōu)化算法的重要途徑。 C = AB可以寫為： 可以得出： —— 《算法分析與設(shè)計(jì)》 47 降低時(shí)間復(fù)雜性的思路：減少乘法的次數(shù)。 k++) C[i][j] += A[i][k]*B[k][j]。 for (int k = 0。 j n。 i n。因此，在最壞 情況下， while循環(huán)被執(zhí)行了 O(lgn) 次。 } return 1。 if (x a[middle]) left = middle + 1。 while (left = right) { int middle = (left + right)/2。 分治算法舉例 1：二分搜索技術(shù) 分析： —— 《算法分析與設(shè)計(jì)》 41 templat class T int binarySearch(T a[], int x, int n) { int left = 0。分析： ?搜索范圍越小，越容易確定解； ?該問題可以分解為若干個(gè)規(guī)模較小的相同問題 。 結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。 ?我們初始化數(shù)組 p[1..n]的值為 0，對(duì)于元素 n，可以依次把它 放到數(shù)組的 p[1],p[2],….,p[n] 位臵，在 n放定一個(gè)位臵后 p[K] 后，剩下的 n1個(gè)元素可以放在那些值為 0的數(shù)組元素 p[1..k1] 和 p[k+1..n]上。否則，將有某 些元素找不到位臵。 perm(p,n)。 p[i] = 0。 i++) { if (p[i] == 0) { p[i] = n。 } else { for (int i = 1。 i++) { // 輸出結(jié)果 coutp[i]。 ② 將 n放在 p[2]位臵上，并用 p[1]和 p[3..n]產(chǎn)生 n1個(gè)元素的全排列； —— 《算法分析與設(shè)計(jì)》 35 321, 312, 231, 132, 213, 123 —— 《算法分析與設(shè)計(jì)》 36 void perm2(int p[], int n) { // n = NUM1 // p[1]~p[n]放臵元素，初始為 0， // n為當(dāng)前參與排列的元素?cái)?shù)量 , 1,2,3,……, n if (參與排列的數(shù)據(jù)數(shù)量為 0) { 輸出結(jié)果 } else { 依次將 n放在每個(gè)位臵， 并采用同樣的方法求解另外 n1元素的全排列； } } —— 《算法分析與設(shè)計(jì)》 37 void perm2(int p[], int n) { if (n == 0) { // 元素集合為空 for (int i = 1。 // 交換 r[i]與 r[j] } } } (1 ) 1()( 1 ) (1 ) 1OnTnnT n O n??? ?? ? ??—— 《算法分析與設(shè)計(jì)》 34 ③ 將 n放在 p[3]位臵上，并用 p[1..2]和 p[4..n]產(chǎn)生 n1個(gè)元素的全排列； 方法 2：固定元素找位臵 元素放置位置： p[1]~p[n] 直到將 n放在 p[n]位臵上，并用 p[1..n1]產(chǎn)生 n1個(gè) 元素的全排列。 // 交換 r[i]與 r[j] perm(r, i + 1, n)。 j = n。 } coutendl。 j = n。 P[m]，如果能夠求出剩余元 P[m+1] 、 P[m+2] 、 … ， P[n] 的所有排列，我們只需將 P[m]放到每個(gè)排列的開頭。 P[m+3]， …,P[n] 。 舉例， 0~3共 4個(gè)數(shù)值的全排列 思路？ —— 《算法分析與設(shè)計(jì)》 30 假設(shè) : 要求 P[m] 、 P[m+1] 、 … P[n] 的全排列 : ，將 P[m]和某個(gè) P[k]交換，求出剩余元素的所有排列后，為 了避免重復(fù)，發(fā)生混亂，必須將 P[m] 和 P[k]交換回去，然后才能繼續(xù) P[m] 和 P[K+1]的交換。 (ri)perm(Ri)表示在全排列 perm(Ri)的每一個(gè)排列的第一 個(gè)位臵加前綴 ri得到的排列。 解題基本方法： （ 1）固定位臵放元素 （ 2）固定元素找位臵 —— 《算法分析與設(shè)計(jì)》 26 假設(shè) R={r1,r2,…,r n}是待排列的 n個(gè)元素， Ri=R{ri}。 m=0時(shí)， A(n,0)=n+2 m=1時(shí)， A(n,1)=A(A(n1,1),0)=A(n1,1)+2， A(1,1)=2 可以得出 A(n,1)=2*n —— 《算法分析與設(shè)計(jì)》 25 遞歸應(yīng)用舉例 3: 排列問題 求解 n個(gè)元素 {r1,r2,…,r n}的全排列。遞歸定義為： —— 《算法分析與設(shè)計(jì)》 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è)計(jì)》 24 m=2時(shí)， 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è)計(jì)》 22 遞歸應(yīng)用舉例 1: Fibonacci數(shù)列 10( ) 1 1( 1 ) ( 2) 1nF n nF n F n n??????? ? ? ? ??邊界條件 遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二要素。 在定義函數(shù)時(shí)調(diào)用到函數(shù)自身稱為 遞歸函數(shù) 。 從定理中可以看出，公式法只要記住三種情形， 就可以很容易地確定許多遞歸方程的解。分別遞歸地解決 a個(gè)子問題，解每個(gè)子問題所需時(shí)間為 T(n/b)。 —— 《算法分析與設(shè)計(jì)》 16 其中， a≥1 ， b1是常數(shù)， f(n)是一個(gè)漸進(jìn)函 數(shù)，描述劃分問題與合并解的時(shí)間復(fù)雜性。 14 ?遞歸樹總共有多少層？當(dāng)遞歸樹展開一層，其規(guī)模為 n/4，當(dāng)遞歸樹展開到第 2層時(shí)，其規(guī)模為n/16=n/42，依次類推，當(dāng)展開到第 k層時(shí)，其規(guī)模為 n/4k=1時(shí)，不再展開，由此可以求得遞歸樹的層數(shù)為 k=log4n。 ① 利用遞歸樹推測出一個(gè)解 ② 利用替換方法進(jìn)行證明 —— 《算法分析與設(shè)計(jì)》 12 例： T(n)=3T(n/4)+2 T(n) → —— 《算法分析與設(shè)計(jì)》 13 log4n+1 nlog4 3 O(nlog4 3 ) —— 《算法分析與設(shè)計(jì)》 ? 現(xiàn)在，我們來計(jì)算一下，有多少個(gè)葉節(jié)點(diǎn)。 數(shù)學(xué)歸納法： v 猜測出解為 T(n)=O(nlgn) v 證明存在某個(gè)常數(shù) c，使得 T(n) ≤lgn —— 《算法分析與設(shè)計(jì)》 11 遞歸樹方法 ?