五年級下冊數(shù)學專項訓練 奧數(shù)第十四講遞推方法全國版(含答案

《五年級下冊數(shù)學專項訓練 奧數(shù)第十四講遞推方法全國版(含答案》由會員分享，可在線閱讀，更多相關(guān)《五年級下冊數(shù)學專項訓練 奧數(shù)第十四講遞推方法全國版(含答案（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

4、n＋2=an＋1＋1， 　　這樣就可以得到自然數(shù)數(shù)列中任何一個數(shù) 　　再看一個例子： 例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？ 　　解： 　　假設用ak表示k條直線最多能把圓的內(nèi)部分成的部分數(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條直線時，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a1＝2.當畫第二條直線時要想把圓內(nèi)部分割的

5、部分盡可能多，就應和第一條直線在圓內(nèi)相交，交點把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來的一個區(qū)域劃分成兩個區(qū)域，因而增加的區(qū)域數(shù)是2，正好等于第二條直線的序號.同理，當畫第三條直線時，要想把圓內(nèi)部分割的部分數(shù)盡可能多，它就應和前兩條直線在圓內(nèi)各有一個交點.兩個交點把第三條線在圓內(nèi)部分成三條線段.而每條線段又把原來一個區(qū)域劃分成兩個區(qū)域.因而增加的區(qū)域部分數(shù)是3，正好等于第三條直線的序號，….這個道理適用于任意多條直線的情形.所以遞推公式（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，…的通項公式. 　　一般來說，如果一個與自然數(shù)有關(guān)的數(shù)列中的任一項an可以由它前面的k（≤n-1）項經(jīng)過運算或其他方法表示出來，我們就稱相鄰項之間有遞歸關(guān)系，并稱這個數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來，就稱這種公式為遞推公式或遞推關(guān)系式.通過尋求遞歸關(guān)系來解決問題的方法就稱為遞推方法.許多與自然數(shù)有關(guān)的數(shù)學問題都常常具有遞推關(guān)系，可以用遞推公式來表達它的數(shù)量關(guān)系.如何尋求

7、這個遞推公式是解決這類問題的關(guān)鍵之一，常用的方法是“退”到問題最簡單情況開始觀察.逐步歸納并猜想一般的速推公式.在小學生階段，我們僅要求學生能撥開問題的一些表面現(xiàn)象由簡到繁地歸納出問題的遞推公式就行了，不要求嚴格證明.當然能證明更好.所謂證明，就是要嚴格推出你建立的關(guān)系式適合所有的n，有時，僅僅在前面幾項成立的關(guān)系式，不一定當n較大時也成立。 例2 平面上10個兩兩相交的圓最多能將平面分割成多少個區(qū)域？平面上1993個圓最多能將平面分割成多少個區(qū)域？ 　　解：設平面上k個圓最多能將平面分割成ak部分.我們先“退”到最簡單的情形.如圖可見 　　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） 　　（3）是這個問題的遞推公式.再把它變形為當n較大時也能方便求出結(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（個）， 　　a1993=19932-1993＋2=3970058（個）。 　　關(guān)于這個遞推公式成立的正確性分析與例1完全類似.比如，第一個圓顯然將平面分為兩個區(qū)域；當畫第二個圓時，

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

10、b，用Sk表示第k次標完后各分點所標數(shù)的和.如圖可見 　　S1＝a＋b，S2＝S1+2S1＝3S1＝3（a＋b）。 　　原因是這樣的：S2是兩類分點旁的標數(shù)和，一類是原來分點所標數(shù)的和S1，另一類是新增分點所標數(shù)的和，它正好是由原來各分點所標的數(shù)向左加一次，又向右加一次的和，故新增分點旁所標數(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時已解出

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

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

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

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

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

16、3，a3=7，…直到算出a64.現(xiàn)在我們設法把遞推公式（5）變形為可以直接計算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 　?。?n-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是一個非常大的數(shù).如果按每移動一片次需一秒鐘算，把64片金片從一根寶石針移到另一根寶石針上大約需要

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