【正文】 右下角子棋盤 if (dr = tr + s amp。 else {// 用 t 號 L型骨牌覆蓋右上角 board[tr + s][tc + s 1] = t。amp。 // 覆蓋其余方格 chessBoard(tr, tc+s, tr+s1, tc+s, s)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。} // 覆蓋右上角子棋盤 if (dr tr + s amp。 else {// 此棋盤中無特殊方格 // 用 t 號 L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。amp。 int t = tile++, // L型骨牌號 s = size/2。遞歸地使用這種分割，直至棋盤簡化為棋盤 1 1。 特殊方格必位于 4個較小子棋盤之一中，其余 3個子棋盤中無特殊方格。在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個 L型骨牌不得重疊覆蓋。目前最好的計算時間上界是 O() ?是否能找到 O(n2)的算法？？？目前為止還沒有結果?；蛟S應當研究３ ３或５ ５矩陣的更好算法。 ???????????????????222112112221121122211211BBBBAAAACCCC)( 2212111 BBAM ??2212112 )( BAAM ??1122213 )( BAAM ??)( 1121224 BBAM ??))(( 221122115 BBAAM ???))(( 222122126 BBAAM ???))(( 121121117 BBAAM ???624511 MMMMC ????2112 MMC ??4321 MMC ??731522 MMMMC ????復雜度分析 T(n)=O(nlog7) =O()?較大的改進 ? 22)()2/(8)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經證明 (1971)，計算 2個２ ２矩陣的乘積， 7次乘法是必要的。因此，算出矩陣 C的 個元素所需的計算時間為 O(n3) ?傳統(tǒng)方法 ： O(n3) Strassen矩陣乘法 使用與上例類似的技術，將矩陣 A， B和 C中每一矩陣都分塊成 4個大小相等的子矩陣。 ?是否能找到線性時間的算法？？？目前為止還沒有結果。 ?最終的，這個思想導致了 快速傅利葉變換 (Fast Fourier Transform)的產生。 1. XY = ac 2n + ((ac)(bd)+ac+bd) 2n/2 + bd 2. XY = ac 2n + ((a+c)(b+d)acbd) 2n/2 + bd 復雜度分析 T(n)=O(nlog3) =O()?較大的改進 ? 11)()2/(3)1()(??????? nnnOnTOnT細節(jié)問題 ：兩個 XY的復雜度都是 O(nlog3)，但考慮到 a+c,b+d可能得到 m+1位的結果，使問題的規(guī)模變大，故不選擇第 2種方案。 思考題： 給定 a，用二分法設計出求 an的算法。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。 } return 1。 if (x a[middle]) left = middle + 1。 while (left = right) { int middle = (left + right)/2。 據此容易設計出 二分搜索算法 ： public static int binarySearch(int [] a, int x, int n) { // 在 a[0] = a[1] = ... = a[n1] 中搜索 x // 找到 x時返回其在數組中的位置，否則返回 1 int left = 0。 ? 分解出的子問題的解可以合并為原問題的解； ? 分解出的各個子問題是相互獨立的。 給定已按升序排好序的 n個元素 a[0:n1]，現要在這 n個元素中找出一特定元素 x。這就說明了此問題滿足分治法的第二個和第三個適用條件。因此這個問題滿足分治法的第一個適用條件 分析： 比較 x和 a的中間元素 a[mid]，若 x=a[mid]，則 x在 L中的位置就是 mid；如果 xa[mid]，由于 a是遞增排序的，因此假如 x在 a中的話， x必然排在 a[mid]的前面，所以我們只要在a[mid]的前面查找 x即可；如果 xa[i]，同理我們只要在 a[mid]的后面查找 x即可。通常假定 T(n)是單調上升的，從而當 mi≤nmi+1時， T(mi)≤T(n)T(mi+1)。再設將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。 分治法的復雜性分析 一個分治法將規(guī)模為 n的問題分成 k個規(guī)模為 n／ m的子問題去解。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。 //遞歸的解各子問題 return merge(y1,...,yk)。 分治法的基本步驟 divideandconquer(P) { if ( | P | = n0) adhoc(P)。 這條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮 貪心算法 或 動態(tài)規(guī)劃 。 分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結構性質 ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 Cooper變換、 反演變換能 將一些遞歸轉化為尾遞歸，從而迭代求出結果。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 遞歸小結 解決方法： 在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。 遞歸小結 優(yōu)點： 結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。 hanoi(n1, c, b, a)。 遞歸的概念 例 6 Hanoi塔問題 public static void hanoi(int n, int a, int b, int c) { if (n 0) { hanoi(n1, a, c, b)。 由此可見， n個圓盤的移動問題可分為 2次 n1個圓盤的移動問題，這又可以遞歸地用上述方法來做。 當 n＞ 1時，需要利用塔座 c作為輔助塔座。 當 n=1時，問題比較簡單。在移動圓盤時應遵守以下移動規(guī)則： 規(guī)則 1：每次只能移動 1個圓盤； 規(guī)則 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足移動規(guī)則 1和 2的前提下，可將圓盤移至a,b,c中任一塔座上。開始時，在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小地疊在一起。 正整數 n的劃分數 p(n)=q(n,n)。 在本例中，如果設 p(n)為正整數 n的劃分數，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數 n1不大于 m的劃分個數記作 q(n,m)?？梢越?q(n,m)的如下遞歸關系。 遞歸的概念 例 5 整數劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數直接求解。 (3)