數(shù)據(jù)結(jié)構(gòu)與算法c(4)(編輯修改稿)
2025-11-14 15:42 本頁面
【文章內(nèi)容簡介】 只是“近似解”，并不代表子問題的解（常常沒有明確的子問題） 例：求 a的平方根 float Sqrt(float a) { float precision=。 //定義解的精度 float x, x0。 x=1。 do { x0=x。 x = 1+(a1)/(x+1)。 }while (xx0precision || x0xprecision)。 //當(dāng)最近兩個近似解的差的絕對值小于給定精度時結(jié)束 return x。 } 遞歸 遞歸與遞歸程序的概念 遞歸 (Recursion)是一種描述與解決問題的基本方法，用來解決一類可歸納描述的問題，或說可分解為結(jié)構(gòu)自相似的問題。所謂結(jié)構(gòu)自相似，是指構(gòu)成問題的部分與問題本身在結(jié)構(gòu)上相似。這類問題具有的特點是：整個問題的解決，可以分為兩大部分： 第一部分 ：是一些特殊（基礎(chǔ)）情況，有直接的解法，即始基； 第二部分 ：這部分與原問題“相似”，可用類似（與整個問題的解法類似）的方法解決（即遞歸），但比原問題的規(guī)模小 這類問題在數(shù)學(xué)中很常見。例如，計算階乘： F(0)=0 F(n)=n*F(n1) 當(dāng) n0 在該式中， f(n1)的計算與原問題 f(n)的計算“相似”，只是規(guī)模較小。在看算術(shù)求和： 也有許多非算術(shù)計算問題可用遞歸方法解決。例如，設(shè)一維數(shù)組 A的元素 A[k1]~A[k2]中存放整數(shù)，現(xiàn)要求出它們中最大者，遞歸求法為： a) 若 k1=k2，則 A[k1]即為所求； b) 若 k1k2，則先按類似的方法，求出A[k1+1]~A[k2]中最大者，設(shè)其為 m，然后，比較 A[k1]和 m，二者中最大者即為所求。 例如，關(guān)于階乘的計算，可通過下列的遞歸程序： long Fact(int n) { if (n=0) return 1。 //第一部份，始基 else return n*Fact(n1)。 //第二部份，用實參 n1遞歸調(diào)用 } 再如，在一維數(shù)組中求最大值的程序為： int GetMax(int a[], int k1, int k2) { int m。 if ( k1 == k2) return a[k1]。 m = GetMax(a, k1+1, k2)。 if (a[k1] m) return a[k1]。 else return m。 } 遞歸程序設(shè)計要點 ? 劃分問題、尋找遞歸：許多問題，并沒有明顯的遞歸解法，這就需要尋找遞歸方案。首先要試著看能否把問題的處理分為兩大類情況。一類情況是可以直接解決（不需要遞歸，為基本情況），另一類情況可按與原問題的解法（即現(xiàn)在正使用的解法）類似的解法進(jìn)行（稱為遞歸情況）。 ? 設(shè)計函數(shù)、確定參數(shù)：使用遞歸，必須設(shè)計為子程序（函數(shù)或過程）的形式。子程序的參數(shù)尤為重要，決定著遞歸的實現(xiàn)。遞歸子程序中的參數(shù)，除了應(yīng)具有一般子程序所需要的參數(shù)外，還需要遞歸參數(shù)。 ? 設(shè)置邊界、控制遞歸：遞歸中，第一類情況（非遞歸的情況）就起到循環(huán)條件的作用，這是因為，滿足第一類情況時，就不遞歸調(diào)用了，本次調(diào)用即可結(jié)束。把第一類情況的判別條件稱為遞歸控制條件。 遞歸程序執(zhí)行機(jī)理 一、一般子程序的執(zhí)行方式 ?對大多數(shù)的程序設(shè)計語言，子程序的調(diào)用執(zhí)行都基于先進(jìn)后出存儲設(shè)備 棧。程序運行時，設(shè)置一個棧，稱為運行棧。每調(diào)用一次子程序，就要為被調(diào)程序的各實在參數(shù)和臨時變量分配存儲空間。這種存儲空間一般是分配在運行棧中的。子程序結(jié)束后，進(jìn)行相應(yīng)的退棧，釋放本次調(diào)用所分配的?？臻g。 一 遞歸子程序的執(zhí)行方式 二、遞歸子程序的執(zhí)行方式 遞歸子程序的執(zhí)行（調(diào)用），仍然遵循一般子程序的執(zhí)行方式，需要注意的是，將每次遞歸調(diào)用都視為不同子程序的調(diào)用，即每次遞歸調(diào)用，都將遞歸子程序的實在參數(shù)和各臨時變量進(jìn)棧，做為棧中的新的一項。據(jù)此可知下面的子程序是個不能終止的過程（相當(dāng)于無限循環(huán)），且會無休止地進(jìn)棧，直至可用內(nèi)存耗盡 Hanoi塔問題出現(xiàn)在 19世紀(jì)的歐洲，用來比喻世界的壽命。問題是這樣的，設(shè)有三根鉆石桿，分別編為 A號 、 B號和 C號，在 A號桿上堆疊 64個金盤，每個盤大小（半徑）不同，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1