五年級(jí)下冊(cè)數(shù)學(xué)專項(xiàng)訓(xùn)練奧數(shù)遞推方法全國(guó)版含答案文檔資料

1、第十四講 遞推方法遞推方法是人們從開(kāi)始認(rèn)識(shí)數(shù)量關(guān)系時(shí)就很自然地產(chǎn)生的一種推理思想.例如自然數(shù)中最小的數(shù)是1，比1大1的數(shù)是2，接下來(lái)比2大1的數(shù)是3，由此得到了自然數(shù)數(shù)列：1，2，3，4，5，.在這里實(shí)際上就有了一個(gè)遞推公式，假設(shè)第n個(gè)數(shù)為an，則an+1=an+1即由自然數(shù)中第n個(gè)數(shù)加上1，就是第n+1個(gè)數(shù)。由此可得an2=an11，這樣就可以得到自然數(shù)數(shù)列中任何一個(gè)數(shù)再看一個(gè)例子：例1 平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線最多能把圓的內(nèi)部分成幾部分？解：假設(shè)用ak表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù).這里k0，1，2，.如圖可見(jiàn)。a01a1=a0+12a2=a1

2、2=4a3=a23=7a4=a3+411歸納出遞推公式an1an+n. （1）即畫第n1條直線時(shí)，最多增加n部分.原因是這樣的：第一條直線最多把圓分成兩部分，故a12.當(dāng)畫第二條直線時(shí)要想把圓內(nèi)部分割的部分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點(diǎn)把第二條直線在圓內(nèi)部分分成兩條線段，而每條線段又把原來(lá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)部分成三條線段.而每條線段又把原來(lái)一個(gè)區(qū)域劃分成兩個(gè)區(qū)域.因而增加的區(qū)域部分?jǐn)?shù)是3，正好等于第三條直線的

3、序號(hào)，.這個(gè)道理適用于任意多條直線的情形.所以遞推公式（1）是正確的.這樣就易求得5條直線最多把圓內(nèi)分成：a5=a4+511=516（部分）。要想求出100條直線最多能把圓內(nèi)分成多少區(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)公式.一般來(lái)說(shuō)，如果一個(gè)與自然數(shù)有關(guān)的數(shù)列中的任一項(xiàng)an可以由它前面的k（n-1）項(xiàng)經(jīng)過(guò)運(yùn)算或其他方法表示出來(lái)，我們就稱相鄰項(xiàng)之間有遞歸關(guān)系，并稱這個(gè)數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來(lái)，就稱這種公式為遞推公式或遞推關(guān)系式.

4、通過(guò)尋求遞歸關(guān)系來(lái)解決問(wèn)題的方法就稱為遞推方法.許多與自然數(shù)有關(guān)的數(shù)學(xué)問(wèn)題都常常具有遞推關(guān)系，可以用遞推公式來(lái)表達(dá)它的數(shù)量關(guān)系.如何尋求這個(gè)遞推公式是解決這類問(wèn)題的關(guān)鍵之一，常用的方法是“退”到問(wèn)題最簡(jiǎn)單情況開(kāi)始觀察.逐步歸納并猜想一般的速推公式.在小學(xué)生階段，我們僅要求學(xué)生能撥開(kāi)問(wèn)題的一些表面現(xiàn)象由簡(jiǎn)到繁地歸納出問(wè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è)平面上

5、k個(gè)圓最多能將平面分割成ak部分.我們先“退”到最簡(jiǎn)單的情形.如圖可見(jiàn)a1=2，a2=422×1，a38=42×2，a4=14=8+2×3，an=an-1+2（n-1）.（3）（3）是這個(gè)問(wèn)題的遞推公式.再把它變形為當(dāng)n較大時(shí)也能方便求出結(jié)果的公式：anan-1+2（n-1）an-2+2（n-2）+（n-1）an-32（n-3）+（n-2）+（n-1）=a1+2（1+2+3+n-2+n-1）a10=102-10+2=92（個(gè)），a1993=19932-19932=3970058（個(gè)）。關(guān)于這個(gè)遞推公式成立的正確性分析與例1完全類似.比如，第一個(gè)圓顯然將平面分為兩個(gè)

6、區(qū)域；當(dāng)畫第二個(gè)圓時(shí)，應(yīng)與原來(lái)的一個(gè)圓有兩個(gè)交點(diǎn)，即被第一個(gè)圓截成兩段弧，而每一段弧將原來(lái)的每一個(gè)區(qū)域分成兩個(gè)區(qū)域，故區(qū)域數(shù)增加了2，即增加了原來(lái)圓的個(gè)數(shù)的2倍；當(dāng)畫第三個(gè)圓時(shí)，應(yīng)與原來(lái)的兩個(gè)圓共有4個(gè)交點(diǎn)，圓弧被截成4段，而每段弧又將原來(lái)的每個(gè)區(qū)域分成兩個(gè)區(qū)域，所以區(qū)域增加了4，即原來(lái)圓的個(gè)數(shù)的2倍，同理類推，說(shuō)明遞推公式應(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、b，用Sk表示第k

7、次標(biāo)完后各分點(diǎn)所標(biāo)數(shù)的和.如圖可見(jiàn)S1ab，S2S1+2S13S13（ab）。原因是這樣的：S2是兩類分點(diǎn)旁的標(biāo)數(shù)和，一類是原來(lái)分點(diǎn)所標(biāo)數(shù)的和S1，另一類是新增分點(diǎn)所標(biāo)數(shù)的和，它正好是由原來(lái)各分點(diǎn)所標(biāo)的數(shù)向左加一次，又向右加一次的和，故新增分點(diǎn)旁所標(biāo)數(shù)的和恰好是原來(lái)所有數(shù)之和的2倍2S1，因此有S2=S12S1=3S1，同理類推S3=S2+2S23S2=32S1，S432S12×32S132S1，Sn=3n-1S1=3n-1（ab） （4）（4）式為遞推公式：Sn3Sn-1在S1=ab時(shí)已解出的表達(dá)式.所謂解出，即Sn直接依賴于n與S1而計(jì)算出.不再是Sn依賴于Sn-1，Sn-1又依

8、賴于Sn-2這樣的形式。例4 假設(shè)剛出生的雌雄一對(duì)小兔過(guò)兩個(gè)月就能生下雌雄一對(duì)小兔，此后每月生下一對(duì)小兔.如果養(yǎng)了初生的一對(duì)小兔，問(wèn)滿一年時(shí)共可得多少對(duì)兔子？解：我們先退到開(kāi)始的簡(jiǎn)單情況來(lái)推算，從中歸納出遞推關(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ì)大兔可以生殖（原來(lái)的大兔和第三個(gè)月出生的小兔），于是生了兩對(duì)小兔，這時(shí)共有5對(duì)兔子。把推算的結(jié)果列成一張表由表中可見(jiàn)滿一年時(shí)可得144對(duì)兔子。如果要算的

9、時(shí)間長(zhǎng)，這種方法就有困難了，現(xiàn)在我們來(lái)找遞推關(guān)系。用un表示第n個(gè)月時(shí)的兔子對(duì)數(shù)，則un：1，1，2，3，5，8，13，21，34，。容易發(fā)現(xiàn)遞推公式是un=un-1+un-2。現(xiàn)在說(shuō)明這個(gè)遞推公式是正確的.因?yàn)榈趎個(gè)月時(shí)的兔子對(duì)分兩類，一類是第n-1個(gè)月時(shí)的兔子對(duì)，另一類是當(dāng)月新生的兔子對(duì)，而這些小兔對(duì)數(shù)恰好是第n-2個(gè)月時(shí)的兔子對(duì)數(shù)un-2。有了上面的遞推公式就可以寫出un的第12項(xiàng)為144對(duì).這正是本題要求的滿一年時(shí)的小兔總對(duì)數(shù)。數(shù)列un稱為斐波那契數(shù)列（Fibonacci，11701250，是意大利數(shù)學(xué)家）.由于數(shù)列un具有許多重要的奇特性質(zhì).因而受到數(shù)學(xué)家們的極大關(guān)注，并把數(shù)列un取

10、名為斐波那契數(shù)列.例5 傳說(shuō)在印度的佛教圣地貝拿勒斯圣廟里安放著個(gè)一個(gè)黃銅板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心有孔的金片.每天都有一個(gè)值班僧侶按下面規(guī)則移動(dòng)金片：把金片從第一根寶石針移到其余的某根寶石針上.要求一次只能移動(dòng)一片，而且小片永遠(yuǎn)要放在大片的上面.當(dāng)時(shí)傳說(shuō)當(dāng)64片金片都按上面的規(guī)則從第一根寶石針移到另一根寶石針上時(shí)，世界將在一聲霹靂中毀滅.所以有人戲稱這個(gè)問(wèn)題叫“世界末日”問(wèn)題（也稱為“Hanoi塔”問(wèn)題），當(dāng)然，移金片和世界毀滅并無(wú)聯(lián)系，這只是一個(gè)傳說(shuō)而已，但說(shuō)明這是一個(gè)需要移動(dòng)很多很多次才能辦到的事情.解這個(gè)問(wèn)題的方法在算法分析中也常用到.究

11、竟按上述規(guī)則移動(dòng)完成64片金片需要移動(dòng)多少次呢？解：設(shè)有n片金片，把從第一片金片至第k片金片按題目要求由第I根寶石針移到另一根寶石針共需移動(dòng)ak次。先對(duì)4片金片的簡(jiǎn)單情形用下列的幾組圖來(lái)表示移動(dòng)過(guò)程中的各種狀態(tài)，并計(jì)數(shù)，歸納出遞歸關(guān)系式。這節(jié)的前幾個(gè)例子都是“退”到簡(jiǎn)單的特殊情況來(lái)歸納出一般規(guī)律.在這個(gè)例子里，我們將先用一般推理得出遞推公式，再以n=64代入，便可解決我們這個(gè)例題.這種從一般到特殊來(lái)解決問(wèn)題的方法也是數(shù)學(xué)上的一種常用方法。我們可以這樣來(lái)想：為了移動(dòng)第n片到第根寶石針上，我們必須先把它上面的n-1片按題目的規(guī)則采用某種程序移到第根寶石針上，這需要移動(dòng)an-1次.然后才能把最下面第

12、n片（最大的），稱到第根寶石針上.最后再經(jīng)過(guò)an-1次才能把第根寶石針上的n-1片金片按上面規(guī)則采用同樣程序移到第根寶石針上.因此把n片金片按題中的規(guī)則全部移到另一根寶石針上共應(yīng)移an=2an-1+1（次）. （5）這就是遞推公式。為了求得n=64時(shí)a64的值，我們當(dāng)然不能一次次地由a1=1，a2=3，a3=7，直到算出a64.現(xiàn)在我們?cè)O(shè)法把遞推公式（5）變形為可以直接計(jì)算a64的形式。an=2an-1+1=2（2an-21）+1=22an-2+21=22（2an-3+1）+2+123an-322+21+12n-1a12n-2+2n-3+21=1222+2n-22n-1，an2an-an=2（1+2+22+2n-1）-（1+2+2n-1）=2n-1，a64264-1。a64是一個(gè)非常大的數(shù).如果按每移動(dòng)一片次需一秒鐘算，把64片金片從一根寶石針移到另一根寶石針上大約需要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，（ ）。198，297，396，495，（ ），（ ）。2.將自然數(shù)1，2，3，按圖排列，在“2”處轉(zhuǎn)第一個(gè)彎，“3”處轉(zhuǎn)第二個(gè)彎，“5”處轉(zhuǎn)第三個(gè)彎，.問(wèn)哪