1、10.3 遞推方程的求解與應用Hanoi 塔問題遞推方程的定義二分歸并排序算法的分析快速排序算法的分析遞歸樹分治算法分析的一般公式1Hanoi塔問題Hanoi塔問題：從A柱將這些圓盤移到C柱上去. 如果把一個圓盤從一個柱子移到另一個柱子稱作 1 次移動，在移動和放置時允許使用B柱，但不允許大圓盤放到小圓盤的上面. 問把所有的圓盤的從A移到C總計需要多少次移動？2算法設計與分析算法 Hanoi (A,C,n) /*把n個盤子從A移到C1. Hanoi (A,B,n-1) 2. move (A,C) /*把1個盤子從A移到C3. Hanoi (B,C,n-1) 移動n個盤子的總次數為T(n) ，得

2、到遞推方程 T(n) = 2T(n1) +1. T(1)=1. 可以求得 T(n)=2n 11秒鐘移動1次，64個盤子大約需要5000億年34遞推方程的定義定義10.5 設序列a0, a1, , an, , 簡記為an, 一個把an與某些個ai（in）聯系起來的等式叫做關于序列an的遞推方程. 實例： Fibonacci數列： fn=fn-1+fn-2, 初值 f0=1, f1=1 階乘數列an，an=n!：an=nan-1, a1=1 求解方法：迭代法 5二分歸并排序算法算法Mergesort(A,s,t) /*排序數組As.t1. m(t-s)/22. AMergesort(A,s,m)

3、/*排序前半數組3. BMergesort(A,s+1,t) /*排序后半數組4. Merge(A,B) /*將排好序的A,B歸并假設n=2k，比較次數至多為W(n) W(n)=2W(n/2)+n1歸并兩個n/2大小數組的比較次數為n16實例 輸入：5, 1, 7, 8, 2, 4, 6, 3 劃分：5, 1, 7, 8, 2, 4, 6, 3 遞歸排序前半個數組: 5, 1, 7, 8 1, 5, 7, 8 遞歸排序后半個數組: 2 ,4, 6, 3 2, 3, 4, 6 歸并: 1, 5, 7, 8 和 2, 3, 4, 6 輸出：1, 2, 3, 4, 5, 6, 7, 8 歸并過程15

4、7823467求解遞推方程8歸納法驗證解n=1代入上述公式得 W(1)=1 log11+1=0， 符合初始條件. 假設對于任何小于n的正整數t，W(t)都是正確的，將結果代入原遞推方程的右邊得 2W(n/2)+n1 =2(2k1 log2k12k1+1)+2k1 =2k(k1)2k+2+2k1=k2k2k+1 = nlognn+1=W(n) 9快速排序算法算法 Quicksort(A,p,r) /*排序數組Ap.r輸入：數組Ap.r輸出：排好序的數組A 1. if p r 2. then qPartition(A, p, r) /*以Ap為準劃分A 3. ApAq /*Ap與Aq交換 4. Q

5、uicksort(A,p,q-1) /*對子數組遞歸排序 5. Quicksort(A,q+1,r)10Partition(A,p,r) 1. x Ap 2. i p 3. j r+1 4. while true do 5. repeat j j 1 6. until A j x /*左邊第1個比Ap大的Ai 9. if i j 10. then A i A j /*交換Aj與Ai 11. else return j 劃分過程1127 99 0 8 13 64 86 16 7 10 88 25 9027 25 0 8 13 64 86 16 7 10 88 99 9027 25 0 8 13

6、10 86 16 7 64 88 99 9027 25 0 8 13 10 7 16 86 64 88 99 9016 25 0 8 13 10 786 64 88 99 902712平均時間復雜度T(n)為對數組的各種輸入平均做的比較次數 將輸入按照Ap在排好序后的位置分別為1, 2, , n進行分類. 假設每類輸入出現的概率相等Ap處位置1，劃分后子問題規模分別為0和n-1 Ap處位置n，劃分后子問題規模分別為n-1和0 n 種輸入的平均復雜度為13遞推方程求解差消法化簡14迭代15用積分近似.16遞歸樹W(n)W(n/2)W(n/2)n1n/2-1W(n/4)n1n/2-1W(n/4).17n-1n/2-1n/2-1n/4-1n/4-1n/4-1n/4-1.1 1 1 1 1 1 1 1 1 1n-1n-2n-4n-2k118分治算法的常用遞推公式其中a為子問題個數，n/b為子問題規模，d(n)為分解成子問題或組合解的代價方程的解為：19Case1 d(n