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

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

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

4、7823467求解遞推方程8歸納法驗(yàn)證解n=1代入上述公式得 W(1)=1 log11+1=0， 符合初始條件. 假設(shè)對(duì)于任何小于n的正整數(shù)t，W(t)都是正確的，將結(jié)果代入原遞推方程的右邊得 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) /*排序數(shù)組Ap.r輸入：數(shù)組Ap.r輸出：排好序的數(shù)組A 1. if p r 2. then qPartition(A, p, r) /*以Ap為準(zhǔn)劃分A 3. ApAq /*Ap與Aq交換 4. Q

5、uicksort(A,p,q-1) /*對(duì)子數(shù)組遞歸排序 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個(gè)比Ap大的Ai 9. if i j 10. then A i A j /*交換Aj與Ai 11. else return j 劃分過(guò)程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平均時(shí)間復(fù)雜度T(n)為對(duì)數(shù)組的各種輸入平均做的比較次數(shù) 將輸入按照Ap在排好序后的位置分別為1, 2, , n進(jìn)行分類(lèi). 假設(shè)每類(lèi)輸入出現(xiàn)的概率相等Ap處位置1，劃分后子問(wèn)題規(guī)模分別為0和n-1 Ap處位置n，劃分后子問(wèn)題規(guī)模分別為n-1和0 n 種輸入的平均復(fù)雜度為13遞推方程求解差消法化簡(jiǎn)14迭代15用積分近似.16遞歸樹(shù)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為子問(wèn)題個(gè)數(shù)，n/b為子問(wèn)題規(guī)模，d(n)為分解成子問(wèn)題或組合解的代價(jià)方程的解為：19Case1 d(n