[理學(xué)]第08章遞歸與搜索上(已修改)
2025-10-23 21:20 本頁面
【正文】 信息學(xué)院信息技術(shù)教研室 程序設(shè)計方法及在線實踐 第 8章 遞歸與搜索 (上 ) 2 第 8章 遞歸與搜索 167。 遞歸是一種重要的算法思想。 167。 遞歸既可以實現(xiàn) 遞推過程 ，也可以實現(xiàn)求解諸多問題的通用思路 ― 搜索 。 3 遞歸的基本思想 什么是遞歸 在數(shù)學(xué)上，求 n的階乘，有兩種表示方法： ① n！ = n (n1) (n2) … 2 1 ② n！ = n (n1)！ 這兩種表示方法實際上對應(yīng)到兩種不同的算法思想。 第①種表示方法中，求 n！ 要反復(fù)把 … 、 (n2)、 (n1)、n累乘起來，是循環(huán)的思想，要用 循環(huán)結(jié)構(gòu) 來實現(xiàn)，代碼如下： int n, F=1。 scanf( %d, amp。n )。 for( i=1。 i=n。 i++ ) F = F*i。 printf( %d的階乘為 %d, n, F )。 4 第②種表示方法，求 n！ 時需要用到 (n1)！。 如果有一個函數(shù)Factorial( int n )能實現(xiàn)求 n的階乘，則該函數(shù)在求 n！ 時要使用到表達(dá)式： n*Factorial(n1)， Factorial(n1)表示調(diào)用 Factorial( )函數(shù)去求(n1)！。 具體代碼例 。 例 遞歸求階乘 include int Factorial( int n ) { if( n0 ) return 1。 else if( n==0 || n==1 ) return 1。 else return n*Factorial(n1)。 //遞歸調(diào)用 Factorial函數(shù) } int main( ) { int A。 scanf( %d, amp。A )。 printf( %d!=%d\n, A, Factorial(A) )。 return 0。 } 該程序的運(yùn)行示例如下： 4↙ 4!=24 5 int Factorial( int n ) { if( n0 ) return 1。 else if( n==0 || n==1 ) return 1。 else return n*Factorial(n1)。 } Factorial( )函數(shù)有一個特點，它在執(zhí)行過程中又調(diào)用了 Factorial( )函數(shù)，這種函數(shù)稱為 遞歸函數(shù) 。 具體來說，在執(zhí)行一個函數(shù)過程中，又 直接或間接地調(diào)用該函數(shù)本身，如圖 ，這種函數(shù)調(diào)用稱為 遞歸調(diào)用 ；包含遞歸調(diào)用的函數(shù)稱為 遞歸函數(shù) 。 6 假設(shè)要求 3!，其完整的執(zhí)行過程如圖 ，具體過程為： ①執(zhí)行 main函數(shù)的開頭部分； ②當(dāng)執(zhí)行到 Factorial函數(shù)調(diào)用“ Factorial(3)”時，流程轉(zhuǎn)而去執(zhí)行Factorial(3)函數(shù)，并將實參 3傳遞給形參 n； ③ 執(zhí)行 Factorial(3)函數(shù)的開頭部分； ④當(dāng)執(zhí)行到遞歸調(diào)用 Factorial(n1)函數(shù)時，此時 n1=2， 所以要轉(zhuǎn)而去執(zhí)行 Factorial(2)函數(shù)； ⑤執(zhí)行 Factorial(2)函數(shù)的開頭部分； ⑥當(dāng)執(zhí)行到遞歸調(diào)用 Factorial(n1)函數(shù)時，此時 n1=1， 所以要轉(zhuǎn)而去執(zhí)行 Factorial(1)函數(shù)； 7 ⑦執(zhí)行 Factorial(1)函數(shù)，此時因為 n的值為 1，所以返回 1，而不是再遞歸調(diào)用下去，即， Factorial(1)函數(shù)執(zhí)行完畢，返回到上一層，即返回Factorial(2)函數(shù)中； ⑧執(zhí)行完 Factorial(2)函數(shù)的剩余語句，返回到 Factorial(3)函數(shù)中； ⑨執(zhí)行完 Factorial(3)函數(shù)的剩余語句，返回到 main函數(shù)中； ⑩繼續(xù)執(zhí)行 main函數(shù)的剩余部分直到整個程序執(zhí)行完畢。 8 遞歸例題解析 例 猴子吃桃問題 。猴子第 1天摘下若干個桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個。第 2天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半另加一個。到第 10天早上想再吃時，就只剩下一個桃子了。求第 1天共摘了多少個桃子。 分析： 假設(shè) Ai為第 i天吃完后剩下的桃子的個數(shù)， A0表示第一天共摘下的桃子 ，本題要求的是 A0。 有以下遞推式子： A0 = 2 (A1+1) A1： 第 1天吃完后剩下的桃子數(shù) A1 = 2 (A2+1) A2： 第 2天吃完后剩下的桃子數(shù) …… A8 = 2 (A9+1) A9： 第 9天吃完后剩下的桃子數(shù) A9 = 1 以上遞推過程可分別用 循環(huán)結(jié)構(gòu) 和 遞歸函數(shù) 實現(xiàn)。 9 用循環(huán)結(jié)構(gòu)實現(xiàn)： 如果 x1， x2表示前后兩天吃完后剩下的桃子數(shù)，則有遞推關(guān)系： x1 = (x2+1)*2。 從第 9天剩下 1個桃子，反復(fù)遞推 9次，則可求第 1天共摘下的桃子數(shù)。這里包含了反復(fù)的思想，可以用循環(huán)結(jié)構(gòu)來實現(xiàn)，代碼如下： include int main( ) { int day, x1, x2。 day = 9。 x2 = 1。 while( day0 ) { x1 = (x2+1)*2。 // 第 1天的桃子數(shù)是第 2天桃子數(shù)加 1后的 2倍 x2 = x1。 day。 } printf( total=%d\n, x1 )。 return 0。 } 該程序的輸出結(jié)果： total=1534 10 用遞歸思想實現(xiàn)： 前面所述的遞推關(guān)系也可以采用下面的方式描述。假設(shè)第 n天吃完后剩下的桃子數(shù)為 A(n)， 第 n+1天吃完后剩下的桃子數(shù)為A(n+1)， 則存在的推關(guān)系： A(n) = ( A(n+1) + 1 ) * 2。這種遞推關(guān)系可以用遞歸函數(shù)實現(xiàn)，代碼如下： include int A(int n) { if(n=9) return 1。 else return(2*(A(n+1)+1))。 } int main( ) { printf( total=%d\n, A(0) )。 return 0。 } 該程序的輸出結(jié)果： total=1534 思考： 以上遞推關(guān)系式存在什么特點，為什么可以用遞歸函數(shù)實現(xiàn)？ 11 例 采用遞歸思想遞推 Fibonacci數(shù)列中的每一項，并輸出前20項的值。 分析： Fibonacci數(shù)列各項的遞推關(guān)系是： F(n) = F(n1) + F(n2)， 這種遞推關(guān)系式很 適合 用 遞歸函數(shù) 實現(xiàn)。代
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1