離散完整ppt課件10.3

1、110.3 遞推方程的求解與應用遞推方程的求解與應用nhanoi 塔問題塔問題n遞推方程的定義遞推方程的定義n二分歸并排序算法的分析二分歸并排序算法的分析n快速排序算法的分析快速排序算法的分析n遞歸樹遞歸樹n分治算法分析的一般公式分治算法分析的一般公式2hanoihanoi塔問題塔問題hanoi塔問題：塔問題：從從a柱將這些圓盤移到柱將這些圓盤移到c柱上去柱上去. 如果把一個圓盤從如果把一個圓盤從一個柱子移到另一個柱子稱作一個柱子移到另一個柱子稱作 1 次移動，在移動和放置次移動，在移動和放置時允許使用時允許使用b柱，但不允許大圓盤放到小圓盤的上面柱，但不允許大圓盤放到小圓盤的上面. 問問把所

2、有的圓盤的從把所有的圓盤的從a移到移到c總計需要多少次移動？總計需要多少次移動？3算法設計與分析算法設計與分析算法算法 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) ，得到遞推方程，得到遞推方程 t(n) = 2t(n 1) +1. t(1)=1. 可以求得可以求得 t(n)=2n 11秒鐘移動秒鐘移動1次，次，64個盤子大約需要個盤子大約需要5000億年億年4（等比級數求和）（等比

3、級數求和）代入初值代入初值的項替換的項替換被含被含的項替換的項替換被含被含12)(12.22212.22)1(2.122)3(2)3()2(12 1)3(2212)2(2)2()1(1 1)2(2 21)1(2)(3213212322 nnnnnnntntntntntntntntntntnt5遞推方程的定義遞推方程的定義定義定義10.5 設序列設序列a0, a1, , an, , 簡記為簡記為an, 一一個把個把an與某些個與某些個ai（in）聯系起來的等式叫做關）聯系起來的等式叫做關于序列于序列an的的遞推方程遞推方程. 實例：實例： fibonacci數列：數列： fn=fn-1+fn-2

4、, 初值初值 f0=1, f1=1 階乘數列階乘數列an，an=n!：an=nan-1, a1=1 求解方法：迭代法求解方法：迭代法 0)1(2),()(2)(11tnnoitnntni6二分歸并排序算法二分歸并排序算法算法算法mergesort(a,s,t) /*排序數組排序數組as.t1. m(t-s)/22. amergesort(a,s,m) /*排序前半數組排序前半數組3. bmergesort(a,s+1,t) /*排序后半數組排序后半數組4. merge(a,b) /*將排好序的將排好序的a,b歸并歸并假設假設n=2k，比較次數至多為，比較次數至多為w(n) w(n)=2w(n/

5、2)+n 1歸并兩個歸并兩個n/2大小數組的比較次數為大小數組的比較次數為n 17實例實例 輸入輸入：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 歸并過程歸并過程157823468求解遞推方程求解遞推方程1log122)12.22(2(1)2.1222

6、22)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkwwwwwwnwkkkkkkkkkkkkkkkkkkkkkk9歸納法驗證解歸納法驗證解nn=1代入上述公式得代入上述公式得 w(1)=1 log1 1+1=0， 符合初始條件符合初始條件. n假設對于任何小于假設對于任何小于n的正整數的正整數t，w(t)都是正確的，都是正確的，將結果代入原遞推方程的右邊得將結果代入原遞推方程的右邊得 2w(n/2)+n 1 =2(2k 1 log2k 1 2k 1+1)+2k 1 =2k(k 1) 2k+2+2k 1=k2k 2k

7、+1 = nlogn n+1=w(n) 10快速排序算法快速排序算法算法算法 q 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. quicksort(a,p,q-1) /*對子數組遞歸排序對子數組遞歸排序 5. quicksort(a,q+1,r)11partition(a,p,r) 1. x ap 2. i p 3. j r+1 4. while true

8、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 劃分過程劃分過程1227 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 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 902713平

9、均時間復雜度平均時間復雜度nt(n)為對數組的各種輸入平均做的比較次數為對數組的各種輸入平均做的比較次數 將輸入按照將輸入按照ap在排好序后的位置分別為在排好序后的位置分別為1, 2, , n進行分類進行分類. 假設每類輸入出現的概率相等假設每類輸入出現的概率相等nap處位置處位置1，劃分后子問題規(guī)模分別為，劃分后子問題規(guī)模分別為0和和n-1 ap處位置處位置n，劃分后子問題規(guī)模分別為，劃分后子問題規(guī)模分別為n-1和和0 nn 種輸入的平均復雜度為種輸入的平均復雜度為)()(2)()0()1(.)2()1()1()0(1)(11noitnnotntnttnttnntni 14遞推方程求解遞推方

10、程求解 0)1(2),()(2)(11tnnoitnntni 2122111)()(21)()1()(2)(ninincitntnccnitnnt為為某某個個常常數數差消法化簡差消法化簡)()1(21)()1()(nontntnnnt )()1()1()(nontnnnt 15迭代迭代 31.1112)1(31.11111)2(1)1(1)(nnctnncncncnntcncnntnnt為為某某個個常常數數16用積分近似用積分近似)(log2ln)1ln(ln131.1111212nonxdxxnnnn )log()(nnont .17遞歸樹遞歸樹 0 (1)2 , 1 ) /2 (2 )(w

11、nnnwnwkw(n)w(n/2)w(n/2)n 1n/2-1w(n/4)n 1n/2-1w(n/4).18n-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-2k 11log)12()2.21()2(.)2()1(11 nnnnknknnnkkk19分治算法的常用遞推公式分治算法的常用遞推公式 1)1()()/()(tbnndbnatntk其中其中a為子問題個數，為子問題個數，n/b為子問題規(guī)模，為子問題規(guī)模，d(n)為分解成為分解成子問題或組合解的代價子問題或組合解的代價方程的解為：方程的解為： banobannobanontcnndanoanontcndaabb)()log()()(:)(1)(log1)()(:)(loglog20)/()()/(.)/()/()/(.)()/()/()(10221122ikiikkkkkkkbndaandbnadbnabndabntandbnadbntant ankbbnaaloglog case1 d(n)=c 1)(log1)()(11)(loganokcaanoaoaacantkakkkb迭代迭代21case2 d(n)=cn banobabacababacnabannocnknbanobabacnnbacnabcnaantakkkkkkakiikik