電子教案C 語(yǔ)言案例教程第五章4

1、第四節(jié)遞推法 本節(jié)任務(wù) 學(xué)會(huì)用遞推法解決問(wèn)題 學(xué)習(xí)要點(diǎn) 掌握遞推法的一般步驟和注意事項(xiàng)【引例】5_4_1 森林里，猴子發(fā)現(xiàn)了一株桃樹(shù)，樹(shù)上結(jié)滿(mǎn)了桃子。猴子第1天爬上桃樹(shù)，偷吃了一半，貪心不足，還多吃了一個(gè)。第2天又爬上桃樹(shù)，偷吃了一半，貪心再起，又多吃了一個(gè)。以后猴子每天都這樣，上樹(shù)吃掉樹(shù)上現(xiàn)有桃子個(gè)數(shù)的一半多1個(gè)。第10天上樹(shù)一看，真可憐，樹(shù)上僅剩了1個(gè)桃子！問(wèn)，樹(shù)上原來(lái)有多少個(gè)桃子？想一想：這個(gè)問(wèn)題，只有采用倒推法 設(shè)當(dāng)日（第n天）猴子吃桃前，樹(shù)上有桃子x個(gè)，則前一天（第n-1天）樹(shù)上桃子個(gè)數(shù)應(yīng)為2(x+1)個(gè)。根據(jù)這個(gè)數(shù)，我們又能推出更前一天樹(shù)上桃子的個(gè)數(shù)，通過(guò)9次這樣的推導(dǎo)，得到第一天

2、猴子吃桃前，樹(shù)上桃子個(gè)數(shù)，即為所求。定義從初始條件出發(fā)，利用某種規(guī)律，逐步推出所需的結(jié)果，這就是遞推法。遞推法難在找出事物的規(guī)律，并用公式去描述這個(gè)規(guī)律。/* 5_4L1.C */#includeconio.hmain() int x=1,n; clrscr(); for(n=10;n0;n-) printf(n第 %d 天猴子吃桃前樹(shù)上桃子個(gè)數(shù)：%d,n, x); x=2*(x+1); 計(jì)算機(jī)輸出顯示，樹(shù)上原有桃子1534個(gè)。提示：遞推法是推理法的一種形式，平常用得很普遍。用遞推公式打印各種有規(guī)律的平面圖形、已知數(shù)列求和等許多問(wèn)題，都需要用到導(dǎo)出的遞推公式，顯然遞推算法是解決上述問(wèn)題的工作的

3、一部分。遞推分成兩種形式，一種是上例猴子吃桃子這樣的稱(chēng)作逆遞推；還有如下面作業(yè)與練習(xí)第一題那樣的稱(chēng)為順遞推。 遞推法實(shí)現(xiàn)的關(guān)鍵 小結(jié) 認(rèn)真尋找前后項(xiàng)的數(shù)量關(guān)系，歸納出用前項(xiàng)（或后項(xiàng)）表示后項(xiàng)（或前項(xiàng)）的一般公式（遞推式），是求解的這類(lèi)問(wèn)題的關(guān)鍵。然后根據(jù)題目的條件，以給出的初始項(xiàng)的值（或末尾項(xiàng)的值），依次循環(huán)求出所需的解即可。作業(yè)與練習(xí) 以下各題，均要求流程圖、變量表、關(guān)鍵語(yǔ)句注釋。4求分?jǐn)?shù)序列前20項(xiàng)之和。5小球從房頂自由落下，每次落地后反彈高度為原高度的一半。已知房頂高H米，問(wèn)當(dāng)小球停下來(lái)時(shí)，小球共彈跳了多少次？共經(jīng)過(guò)了多少米？6試證明：對(duì)任意自然數(shù)N，如果為偶數(shù)則將其除2，如果為奇數(shù)則將其乘3加1，經(jīng)過(guò)有限步運(yùn)算后，可以達(dá)到1。7求廣義菲波那級(jí)數(shù)的第n項(xiàng)。廣義菲波那級(jí)數(shù)數(shù)列為：0，0，1，1，2，4，7，13，24，即：F(0)=0，F(xiàn)(1)=0，F(xiàn)(1)=1，當(dāng)n2時(shí)，F(xiàn)(n)=F(n-1)+F(n-