數(shù)據(jù)結(jié)構(gòu)第06章-在線瀏覽
2024-09-04 09:08本頁面
【正文】 設(shè)計主函數(shù)如下 void main(void) { long int fn。 } 主函數(shù)用實參 n= 3調(diào)用了遞歸算法 Fact(3)，而Fact(3)要通過調(diào)用 Fact(2)、 Fact(2)要通過調(diào)用 Fact(1)、Fact(1)要通過調(diào)用 Fact(0)來得出計算結(jié)果。 9 圖 62 Fact(3)的遞歸調(diào)用執(zhí)行過程 10 例 62 給出在有序數(shù)組 a中查找數(shù)據(jù)元素 x是否存在的遞歸算法，并給出如圖 61所示實際數(shù)據(jù)的遞歸算法的執(zhí)行過程。 if(low high) return 1。 if(x == a[mid]) return mid。 //在下半?yún)^(qū)查找 else return BSearch(a, x, mid+1, high)。 int x = 17。 bn = BSearch(a, x, 0,7)。 else printf(x在數(shù)組 a的下標(biāo) %d中 , bn)。 圖 63 BSearch(a, x, 0,7)的遞歸調(diào)用過程 14 15 遞歸算法既是一種有效的算法設(shè)計方法 ， 也是一種有效的分析問題的方法 。 16 適宜于用遞歸算法求解的問題的 充分必要條件是： （ 1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)； （ 2）某一有限步的子問題（也稱作本原問題）有直接的解存在。 （ 2）設(shè)計遞歸出口。 漢諾塔問題的描述是：設(shè)有 3根標(biāo)號為 A， B， C的柱子 ， 在 A柱上放著 n個盤子 ，每一個都比下面的略小一點 ， 要求把 A柱上的盤子全部移到 C柱上 ， 移動的規(guī)則 是： （ 1） 一次只能移動一個盤子； （ 2） 移動過程中大盤子不能放在小盤子上面； （ 3） 在移動過程中盤子可以放在 A， B， C的任意一個柱子上 。 基本思想 ： 1個盤子的漢諾塔問題可直接移動。 4個盤子漢諾塔問題的遞歸求解示意圖如圖 64所示。 return。 //把圓盤 n由 fromPeg直接移至 toPeg printf(%s%d%s%c%s%c\n, move disk , n, from peg , fromPeg, to peg , toPeg)。 } 22 測試主函數(shù)如下： include void main(void) { Towers(4, 39。, 39。, 39。)。 25 對于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要 保存 以下兩類 信息 ： （ 1）調(diào)用函數(shù)的返回地址； （ 2）調(diào)用函數(shù)的局部變量值。 26 遞歸函數(shù)被調(diào)用時，系統(tǒng)要作的工作和非遞歸函數(shù)被調(diào)用時系統(tǒng)要作的工作在 形式上類同 ，但 保存信息的方法不同 。每一層遞歸調(diào)用所需保存的信息構(gòu)成運行時棧的一個工作記錄，在每進入下一層遞歸調(diào)用時，系統(tǒng)就建立一個新的 工作記錄 ，并把這個工作記錄進棧成為運行時棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個工作記錄。 27 斐波那契數(shù)列 Fib(n)的遞推定義是： 求第 n項斐波那契數(shù)列的 遞歸函數(shù) 如下： long Fib(int n) { if(n == 0 || n == 1) return n。 //遞歸調(diào)用 } 28
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1