《算法設(shè)計基本方法》ppt課件-文庫吧
2025-04-27 12:54 本頁面
【正文】 50)1(1110 7 7 3 5 1 7 3 20)1(1210 7 1 7 7 9 2 1 40)1(1310 6 6 8 7 0 2 2 00)1(1410 6 3 8 1 6 9 1 80)1(1510 4 2 7 4 6 2 3 3016116121*1*0*2*1*11*10*12*11*13*12*14*13*15*14*15.II.II.II.II.II.II.II.eI????????????????????????????????取 We just got lucky? 考察反推一步的誤差： ||1)1(1)1(1|| *1 NNNN ENININE ??????以此類推，對 n N 有： ||)1(...)1( 1|| Nn EnNNE ???誤差逐步遞減 , 這樣的算法稱為 穩(wěn)定的算法 /* stable algorithm */ 類似例子見教材 p8 算法設(shè)計基本方法（ 4） ? 遞歸 ? 將一個復(fù)雜的問題歸結(jié)為若干個較簡單的問題，然后將這些較簡單的每一個問再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止。 例： 計算階乘 : n! = n(n?1) ? ? ? 2?1, 0! = 1. int factorial ( int n ) { int i, result。 result =1。 if ( n 0 ) { for ( i = 1。 i = n。 i++ ) result = result * i 。 } /* end if */ return result。 } int factorial ( int n ) { if ( n 0 ) return n * factorial ( n ? 1 )。 else return 1。 } 例 :斐波那契 (Fibonacci)序列： F0 = F1 = 1 Fi = Fi1 + Fi2 （ i1) 算法 求斐波那契數(shù) int F(n) { //返回第 n個斐波那契數(shù) // int n。 if (n= 1) return(1)。 else return F(n1) + F(n2)。 } 算法效率：對 F(n1) 、 F(n2)存在大量的重復(fù)計算 ? 改 進(jìn)：保存中間結(jié)果 例 :歐幾里得算法 已知兩個非負(fù)整數(shù) a和 b，且 a＞ b≥0 ，求這兩個數(shù)的最大公因數(shù)。 輾轉(zhuǎn)相除法 ：若 b=0，則 a和 b的最大公因數(shù)等于 a；若 b＞ 0，則 a和 b的最大公因數(shù)等于 b和用 b除 a的余數(shù)的最大公因數(shù)。 算法 求最大公因數(shù) GCD(int a,int b) // 約定 ab // { if (b==0) return(a)。 else return (GCD(b,a % b))。 } 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2。 遞歸 特點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，容易用數(shù)學(xué)歸納法證明算法正確性 適用范圍：難以用循環(huán)或遞推直觀描述的復(fù)雜問題 缺點(diǎn)：資源耗費(fèi)多，執(zhí)行效率低，所以在算法優(yōu)化時采用消遞歸策略 算法設(shè)計基本方法（ 5） ? 減半遞推技術(shù)（分治法） ? 所謂 “ 減半 ” ，是指將問題的規(guī)模減半，而問題的性質(zhì)不變。所謂 “ 遞推 ” ，是指重復(fù) “ 減半 ” 的過程。 例：二分法求方程實(shí)根的減半遞推過程（算法及程序見書 p13） 首先取給定區(qū)間的中點(diǎn) c＝ (a＋ b)/2。 然后判斷 f(c)是否為 0。 若 f(c)＝ 0,則說明 c即為所求的根，求解過程結(jié)束； 如果 f(c)≠0,則根據(jù)以下原則將原區(qū)間減半： 若 f(a)f(c)＜ 0，則取原區(qū)間的前半部分； 若 f(b)f(c)＜ 0，則取原區(qū)間的后半部分。 最后判斷減半后的區(qū)間長度是否已經(jīng)很?。? 若 |a－ b|＜ ε，則過程結(jié)束，取 (a＋ b)/2為根的近似值； 若 |a－ b|≥ε，則重復(fù)上述的減半過程。 例 二分檢索 二分檢索：每次選取 中間元素 的下標(biāo) 算法 二分檢索 Int BINSRCH(int A[],int n,int x)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1