《五年級(jí)下冊(cè)數(shù)學(xué)專項(xiàng)訓(xùn)練 奧數(shù)第十四講遞推方法全國(guó)版(含答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《五年級(jí)下冊(cè)數(shù)學(xué)專項(xiàng)訓(xùn)練 奧數(shù)第十四講遞推方法全國(guó)版(含答案（7頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第十四講 遞推方法 家庭是幼兒語(yǔ)言活動(dòng)的重要環(huán)境，為了與家長(zhǎng)配合做好幼兒閱讀訓(xùn)練工作，孩子一入園就召開家長(zhǎng)會(huì)，給家長(zhǎng)提出早期抓好幼兒閱讀的要求。我把幼兒在園里的閱讀活動(dòng)及閱讀情況及時(shí)傳遞給家長(zhǎng)，要求孩子回家向家長(zhǎng)朗誦兒歌，表演故事。我和家長(zhǎng)共同配合，一道訓(xùn)練，幼兒的閱讀能力提高很快。 　　遞推方法是人們從開始認(rèn)識(shí)數(shù)量關(guān)系時(shí)就很自然地產(chǎn)生的一種推理思想.例如自然數(shù)中最小的數(shù)是1，比1大1的數(shù)是2，接下來比2大1的數(shù)是3，…由此得到了自然數(shù)數(shù)列：1，2，3，4，5，….在這里實(shí)際上就有了一個(gè)遞推公式，假設(shè)第n個(gè)數(shù)為an，則 唐宋或更早之前，針對(duì)“經(jīng)學(xué)”“律學(xué)”“算學(xué)”和“書學(xué)”各科目，其相應(yīng)傳

2、授者稱為“博士”，這與當(dāng)今“博士”含義已經(jīng)相去甚遠(yuǎn)。而對(duì)那些特別講授“武事”或講解“經(jīng)籍”者，又稱“講師”。“教授”和“助教”均原為學(xué)官稱謂。前者始于宋，乃“宗學(xué)”“律學(xué)”“醫(yī)學(xué)”“武學(xué)”等科目的講授者；而后者則于西晉武帝時(shí)代即已設(shè)立了，主要協(xié)助國(guó)子、博士培養(yǎng)生徒?！爸獭痹诠糯粌H要作入流的學(xué)問，其教書育人的職責(zé)也十分明晰。唐代國(guó)子學(xué)、太學(xué)等所設(shè)之“助教”一席，也是當(dāng)朝打眼的學(xué)官。至明清兩代，只設(shè)國(guó)子監(jiān)（國(guó)子學(xué)）一科的“助教”，其身價(jià)不謂顯赫，也稱得上朝廷要員。至此，無論是“博士”“講師”，還是“教授”“助教”，其今日教師應(yīng)具有的基本概念都具有了。 　　an+1=an+1 課本、報(bào)刊雜志中

3、的成語(yǔ)、名言警句等俯首皆是,但學(xué)生寫作文運(yùn)用到文章中的甚少,即使運(yùn)用也很難做到恰如其分。為什么?還是沒有徹底“記死”的緣故。要解決這個(gè)問題,方法很簡(jiǎn)單,每天花3-5分鐘左右的時(shí)間記一條成語(yǔ)、一則名言警句即可?？梢詫懺诤蠛诎宓摹胺e累專欄”上每日一換,可以在每天課前的3分鐘讓學(xué)生輪流講解,也可讓學(xué)生個(gè)人搜集,每天往筆記本上抄寫,教師定期檢查等等。這樣,一年就可記300多條成語(yǔ)、300多則名言警句,日積月累,終究會(huì)成為一筆不小的財(cái)富。這些成語(yǔ)典故“貯藏”在學(xué)生腦中,自然會(huì)出口成章,寫作時(shí)便會(huì)隨心所欲地“提取”出來,使文章增色添輝。 　　即由自然數(shù)中第n個(gè)數(shù)加上1，就是第n+1個(gè)數(shù)。由此可得 　　a

4、n＋2=an＋1＋1， 　　這樣就可以得到自然數(shù)數(shù)列中任何一個(gè)數(shù) 　　再看一個(gè)例子： 例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？ 　　解： 　　假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù).這里k＝0，1，2，….如圖可見。 　　a0＝1 　　a1=a0+1＝2 　　a2=a1＋2=4 　　a3=a2＋3=7 　　a4=a3+4＝11 　　歸納出遞推公式an＋1＝an+n. （1） 　　即畫第n＋1條直線時(shí)，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a1＝2.當(dāng)畫第二條直線時(shí)要想把圓內(nèi)部分割的

5、部分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點(diǎn)把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來的一個(gè)區(qū)域劃分成兩個(gè)區(qū)域，因而增加的區(qū)域數(shù)是2，正好等于第二條直線的序號(hào).同理，當(dāng)畫第三條直線時(shí)，要想把圓內(nèi)部分割的部分?jǐn)?shù)盡可能多，它就應(yīng)和前兩條直線在圓內(nèi)各有一個(gè)交點(diǎn).兩個(gè)交點(diǎn)把第三條線在圓內(nèi)部分成三條線段.而每條線段又把原來一個(gè)區(qū)域劃分成兩個(gè)區(qū)域.因而增加的區(qū)域部分?jǐn)?shù)是3，正好等于第三條直線的序號(hào)，….這個(gè)道理適用于任意多條直線的情形.所以遞推公式（1）是正確的.這樣就易求得5條直線最多把圓內(nèi)分成： 　　a5=a4+5＝11=5＝16（部分）。 　　要想求出100條直線最多能把圓內(nèi)分成多

6、少區(qū)域，不能直接用上面公式了，可把上面的遞推公式變形： 　　∵an=an-1+n=nn-2＋（n-1）＋n 　　=an-3+（n-2）＋（n-n）+n 　　公式（2）也稱為數(shù)列1，2，4，7，11，16，…的通項(xiàng)公式. 　　一般來說，如果一個(gè)與自然數(shù)有關(guān)的數(shù)列中的任一項(xiàng)an可以由它前面的k（≤n-1）項(xiàng)經(jīng)過運(yùn)算或其他方法表示出來，我們就稱相鄰項(xiàng)之間有遞歸關(guān)系，并稱這個(gè)數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關(guān)系式.通過尋求遞歸關(guān)系來解決問題的方法就稱為遞推方法.許多與自然數(shù)有關(guān)的數(shù)學(xué)問題都常常具有遞推關(guān)系，可以用遞推公式來表達(dá)它的數(shù)量關(guān)系.如何尋求

7、這個(gè)遞推公式是解決這類問題的關(guān)鍵之一，常用的方法是“退”到問題最簡(jiǎn)單情況開始觀察.逐步歸納并猜想一般的速推公式.在小學(xué)生階段，我們僅要求學(xué)生能撥開問題的一些表面現(xiàn)象由簡(jiǎn)到繁地歸納出問題的遞推公式就行了，不要求嚴(yán)格證明.當(dāng)然能證明更好.所謂證明，就是要嚴(yán)格推出你建立的關(guān)系式適合所有的n，有時(shí)，僅僅在前面幾項(xiàng)成立的關(guān)系式，不一定當(dāng)n較大時(shí)也成立。 例2 平面上10個(gè)兩兩相交的圓最多能將平面分割成多少個(gè)區(qū)域？平面上1993個(gè)圓最多能將平面分割成多少個(gè)區(qū)域？ 　　解：設(shè)平面上k個(gè)圓最多能將平面分割成ak部分.我們先“退”到最簡(jiǎn)單的情形.如圖可見 　　a1=2，a2=4＝2＋2×1， 　　a3＝

8、8=4＋2×2， 　　a4=14=8+2×3， 　　an=an-1+2（n-1）.（3） 　?。?）是這個(gè)問題的遞推公式.再把它變形為當(dāng)n較大時(shí)也能方便求出結(jié)果的公式： 　　an＝an-1+2（n-1） 　?。絘n-2+2[（n-2）+（n-1）] 　?。絘n-3＋2[（n-3）+（n-2）+（n-1）] 　?。健?a1+2（1+2+3+…+n-2+n-1） 　　∴a10=102-10+2=92（個(gè)）， 　　a1993=19932-1993＋2=3970058（個(gè)）。 　　關(guān)于這個(gè)遞推公式成立的正確性分析與例1完全類似.比如，第一個(gè)圓顯然將平面分為兩個(gè)區(qū)域；當(dāng)畫第二個(gè)圓時(shí)，

9、應(yīng)與原來的一個(gè)圓有兩個(gè)交點(diǎn)，即被第一個(gè)圓截成兩段弧，而每一段弧將原來的每一個(gè)區(qū)域分成兩個(gè)區(qū)域，故區(qū)域數(shù)增加了2，即增加了原來圓的個(gè)數(shù)的2倍；當(dāng)畫第三個(gè)圓時(shí)，應(yīng)與原來的兩個(gè)圓共有4個(gè)交點(diǎn)，圓弧被截成4段，而每段弧又將原來的每個(gè)區(qū)域分成兩個(gè)區(qū)域，所以區(qū)域增加了4，即原來圓的個(gè)數(shù)的2倍，…，同理類推，說明遞推公式應(yīng)該是 　　an=an-1+2（n-1）。 例3在一個(gè)圓周上按下面規(guī)則標(biāo)上一些數(shù):第一次先把圓周二等分 三次把4段圓弧分別二等分，并在4個(gè)分點(diǎn)旁邊標(biāo)上兩個(gè)相鄰分點(diǎn)旁所 去，當(dāng)?shù)诎舜螛?biāo)完數(shù)以后，圓周上所有已標(biāo)的數(shù)的和是多少？ 　　解： 　　解：我們一般地設(shè)第一次所標(biāo)的兩數(shù)分別為a、

10、b，用Sk表示第k次標(biāo)完后各分點(diǎn)所標(biāo)數(shù)的和.如圖可見 　　S1＝a＋b，S2＝S1+2S1＝3S1＝3（a＋b）。 　　原因是這樣的：S2是兩類分點(diǎn)旁的標(biāo)數(shù)和，一類是原來分點(diǎn)所標(biāo)數(shù)的和S1，另一類是新增分點(diǎn)所標(biāo)數(shù)的和，它正好是由原來各分點(diǎn)所標(biāo)的數(shù)向左加一次，又向右加一次的和，故新增分點(diǎn)旁所標(biāo)數(shù)的和恰好是原來所有數(shù)之和的2倍2S1，因此有 　　S2=S1＋2S1=3S1，同理類推 　　S3=S2+2S2＝3S2=32S1， 　　S4＝32S1＋2×32S1＝32S1， 　　Sn=3n-1S1=3n-1（a＋b） （4） 　?。?）式為遞推公式：Sn＝3Sn-1在S1=a＋b時(shí)已解出

11、的表達(dá)式.所謂解出，即Sn直接依賴于n與S1而計(jì)算出.不再是Sn依賴于Sn-1，Sn-1又依賴于Sn-2…這樣的形式。 例4 假設(shè)剛出生的雌雄一對(duì)小兔過兩個(gè)月就能生下雌雄一對(duì)小兔，此后每月生下一對(duì)小兔.如果養(yǎng)了初生的一對(duì)小兔，問滿一年時(shí)共可得多少對(duì)兔子？ 　　解：我們先退到開始的簡(jiǎn)單情況來推算，從中歸納出遞推關(guān)系.如圖： 　　第一個(gè)月：只有1對(duì)小兔。 　　第二個(gè)月：一對(duì)小兔長(zhǎng)成一對(duì)大兔，但尚不會(huì)生殖.仍只有一對(duì)兔子。 　　第三個(gè)月：這對(duì)大兔生了一對(duì)小兔，這時(shí)共2對(duì)兔子。 　　第四個(gè)月：大兔又生了一對(duì)小兔，而上月出生的小兔正在長(zhǎng)大，這時(shí)共3對(duì)兔子。 　　第五個(gè)月：這時(shí)已有兩對(duì)大兔可

12、以生殖（原來的大兔和第三個(gè)月出生的小兔），于是生了兩對(duì)小兔，這時(shí)共有5對(duì)兔子。 　　把推算的結(jié)果列成一張表 　　由表中可見滿一年時(shí)可得144對(duì)兔子。 　　如果要算的時(shí)間長(zhǎng)，這種方法就有困難了，現(xiàn)在我們來找遞推關(guān)系。 　　用｛un｝表示第n個(gè)月時(shí)的兔子對(duì)數(shù)，則 　?。鹵n｝：1，1，2，3，5，8，13，21，34，…。 　　容易發(fā)現(xiàn)遞推公式是 　　un=un-1+un-2。 　　現(xiàn)在說明這個(gè)遞推公式是正確的.因?yàn)榈趎個(gè)月時(shí)的兔子對(duì)分兩類，一類是第n-1個(gè)月時(shí)的兔子對(duì)，另一類是當(dāng)月新生的兔子對(duì)，而這些小兔對(duì)數(shù)恰好是第n-2個(gè)月時(shí)的兔子對(duì)數(shù)un-2。 　　有了上面的遞推公式就可以

13、寫出｛un｝的第12項(xiàng)為144對(duì).這正是本題要求的滿一年時(shí)的小兔總對(duì)數(shù)。數(shù)列｛un｝稱為斐波那契數(shù)列（Fibonacci，1170～1250，是意大利數(shù)學(xué)家）.由于數(shù)列｛un｝具有許多重要的奇特性質(zhì).因而受到數(shù)學(xué)家們的極大關(guān)注，并把數(shù)列｛un｝取名為斐波那契數(shù)列. 例5 傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個(gè)一個(gè)黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片.每天都有一個(gè)值班僧侶按下面規(guī)則移動(dòng)金片：把金片從第一根寶石針移到其余的某根寶石針上.要求一次只能移動(dòng)一片，而且小片永遠(yuǎn)要放在大片的上面.當(dāng)時(shí)傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石針移到另

14、一根寶石針上時(shí)，世界將在一聲霹靂中毀滅.所以有人戲稱這個(gè)問題叫“世界末日”問題（也稱為“Hanoi塔”問題），當(dāng)然，移金片和世界毀滅并無聯(lián)系，這只是一個(gè)傳說而已，但說明這是一個(gè)需要移動(dòng)很多很多次才能辦到的事情.解這個(gè)問題的方法在算法分析中也常用到.究竟按上述規(guī)則移動(dòng)完成64片金片需要移動(dòng)多少次呢？解：設(shè)有n片金片，把從第一片金片至第k片金片按題目要求由第I根寶石針移到另一根寶石針共需移動(dòng)ak次。 　　先對(duì)4片金片的簡(jiǎn)單情形用下列的幾組圖來表示移動(dòng)過程中的各種狀態(tài)，并計(jì)數(shù)，歸納出遞歸關(guān)系式。 　　這節(jié)的前幾個(gè)例子都是“退”到簡(jiǎn)單的特殊情況來歸納出一般規(guī)律.在這個(gè)例子里，我們將先用一般推理得出

15、遞推公式，再以n=64代入，便可解決我們這個(gè)例題.這種從一般到特殊來解決問題的方法也是數(shù)學(xué)上的一種常用方法。 　　我們可以這樣來想：為了移動(dòng)第n片到第Ⅲ根寶石針上，我們必須先把它上面的n-1片按題目的規(guī)則采用某種程序移到第Ⅱ根寶石針上，這需要移動(dòng)an-1次.然后才能把最下面第n片（最大的），稱到第Ⅲ根寶石針上.最后再經(jīng)過an-1次才能把第Ⅱ根寶石針上的n-1片金片按上面規(guī)則采用同樣程序移到第Ⅲ根寶石針上.因此把n片金片按題中的規(guī)則全部移到另一根寶石針上共應(yīng)移 　　an=2an-1+1（次）. （5） 　　這就是遞推公式。為了求得n=64時(shí)a64的值，我們當(dāng)然不能一次次地由a1=1，a2=

16、3，a3=7，…直到算出a64.現(xiàn)在我們?cè)O(shè)法把遞推公式（5）變形為可以直接計(jì)算a64的形式。 　　∵an=2an-1+1=2（2an-2＋1）+1=22an-2+2＋1 　　=22（2an-3+1）+2+1＝23an-3＋22+21+1 　　＝2n-1a1＋2n-2+2n-3+…+2＋1 　　=1＋2＋22+…+2n-2＋2n-1， 　　∴an＝2an-an 　　=2（1+2+22＋…+2n-1）-（1+2+…+2n-1） 　　=2n-1， 　　∴a64＝264-1。 　　a64是一個(gè)非常大的數(shù).如果按每移動(dòng)一片次需一秒鐘算，把64片金片從一根寶石針移到另一根寶石針上大約需要

17、5800億年。 習(xí)題十四 　　1. 請(qǐng)你根據(jù)下列各個(gè)數(shù)之間的關(guān)系，在括號(hào)里填上恰當(dāng)?shù)臄?shù)： 　　①1，5，9，13，17，（ ）。 　　②0.625，1.25，2.5，5，（ ）。 　?、?98，297，396，495，（ ），（ ）。 2.將自然數(shù)1，2，3，…，按圖排列，在“2”處轉(zhuǎn)第一個(gè)彎，“3”處轉(zhuǎn)第二個(gè)彎，“5”處轉(zhuǎn)第三個(gè)彎，….問哪個(gè)數(shù)處轉(zhuǎn)第二十個(gè)彎？ 　　3.請(qǐng)用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少種不同站法？ 　　4.上一段12級(jí)樓梯，規(guī)定每一步只能上一級(jí)或兩級(jí).問要登上第12級(jí)樓梯共有多少種不同走法？ 　　5. 有10個(gè)村莊，分別用A1，A2，…，A10表示，某人從A1出發(fā)按箭頭方向繞一圈最后經(jīng)由A10再回到A1，有多少種不同走法？ 　　注：每點(diǎn)（村）至多過一次，兩村之間，可走直線，也可走圓周上弧線，但都必須按箭頭方向走. ? 第 7 頁(yè)