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

五年級下冊數(shù)學(xué)專項訓(xùn)練奧數(shù)第十四講遞推方法全

國版(含答案)

遞推要領(lǐng)是人們從開始明白數(shù)量干系時就很自然地產(chǎn)生的一種推理

思想.比方自然數(shù)中最小的數(shù)是1,比1大1的數(shù)是2,接下來比2大1的

數(shù)是3,…由此得到了自然數(shù)數(shù)列：1,2,3,4,5,….在這里實際上就

有了一個遞推公式，假設(shè)第n個數(shù)為a，則

4尸&+1

即由自然數(shù)中第n個數(shù)加上1,便是第n+1個數(shù)。由此可得

&+2=4+1+1,

這樣就可以得到自然數(shù)數(shù)列中任何一個數(shù)

再看一個例子：

例1平面上5條直線最多能把圓的內(nèi)部分成幾部分？平面上100條直線

最多能把圓的內(nèi)部分成幾部分？

解：

假設(shè)用還表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?shù).這里k=D,l,

2,….如圖可見。

須=1

a尸&,+1=2

a；：=ai+2=4

a3=a;4-3=7

a4=a3+4=11

概括出遞推公式a+=a、+n.(1)

即畫第n+1條直線時，最多增加n部分.原因是這樣的：第一條直線

最多把圓分成兩部分，故&=2.當(dāng)畫第二條直線時要想把圓內(nèi)部破裂為部

分盡可能多，就應(yīng)和第一條直線在圓內(nèi)相交，交點(diǎn)把第二條直線在圓內(nèi)部

分分成兩條線段，而每條線段又把原來的一個地區(qū)劃分成兩個地區(qū)，因而

增加的地區(qū)數(shù)是2,正好即是第二條直線的序號.同理，當(dāng)畫第三條直線時,

要想把圓內(nèi)部破裂的部分?jǐn)?shù)盡可能多，它就應(yīng)和前兩條直線在圓內(nèi)各有一

個交點(diǎn).兩個交點(diǎn)把第三條線在圓內(nèi)部分成三條線段.向每條線段又把原來

一個地區(qū)劃分成兩個地區(qū).因而增加的地區(qū)部分?jǐn)?shù)是3,正好即是第三條直

線的序號，….這個原理適用于恣意多條直線的環(huán)境.所以遞推公式(1)是

正確的.這樣就易求得5條直線最多把圓內(nèi)分成：

a5=a4+5=ll=5=16(部分)。

要想求出100條直線最多能把圓內(nèi)分成幾多地區(qū)，不能直接用上面公

式了，可把上面的遞推公式變形：

Va=a,rl+n=n?2+(n-1)+n

=a-3+(n-2)+(n-n)+n

公式(2)也稱為數(shù)列1,2,4,7,11,16,…的通項公式.

一般來說，要是一個與自然數(shù)有關(guān)的數(shù)列中的任一項可以由它火線

的k(Wn-1)項議決運(yùn)算或其他要領(lǐng)表示出來，我們就稱相鄰項之間有遞

歸干系，并稱這個數(shù)列為遞歸數(shù)列.要是這種推算要領(lǐng)能用公式表示出來,

就稱這種公式為遞推公式或遞推干系式.議決尋求遞歸干系來辦理標(biāo)題的

要領(lǐng)就稱為遞推要領(lǐng).許多與自然數(shù)有關(guān)的數(shù)學(xué)標(biāo)題都常常具有遞推干

系，可以用遞推公式來表達(dá)它的數(shù)量干系.怎樣尋求這個遞推公式是辦理

這類標(biāo)題的要害之一，常用的要領(lǐng)是“退”到標(biāo)題最簡略環(huán)境開始查看.

逐步概括并猜測一般的速推公式.在小學(xué)生階段，我們僅要修業(yè)生能撥開

標(biāo)題的一些表面現(xiàn)象由簡到繁地概括出標(biāo)題的遞推公式就行了，不要求嚴(yán)

格證明.固然能證明更好.所謂證明，便是要嚴(yán)格推出你建立的干系式適合

所有的n,有時，只是在火線幾項成立的干系式，不一定當(dāng)n較大時也成

立。

例2平面上10個兩兩相交的圓最多能將平面破裂成幾多個地區(qū)？平面上

1993個圓最多能將平面破裂成幾多個地區(qū)？

解：設(shè)平而上k個圓最多能將平面破裂成如部分.我們先“退”到最

簡略的環(huán)境.如圖可見

a.=2,a：=4=2+2X1,

a3=8=4+2X2,

a4=14=8+2X3,

a,=a.-i+2(n-1).(3)

(3)是這個標(biāo)題的遞推公式.再把它變形為當(dāng)n較大時也能方

便求出終于的公式：

3n=anT+2(n-1)

=a,j+2[(n-2)+(n-1)]

=a“-3+2[(n-3)+(n-2)+(n-I)J

*,

=*=a1+2(1+2+3+…+n-2+n-l)

.,.0=102-10+2=92(個)，

a：993=19932-1993+2=3970058(個)。

關(guān)于這個遞推公式成立的正確性剖析與例1完全類似.比如，

第一個圓顯然將平面分為兩個地區(qū)；當(dāng)畫第二個圓時，應(yīng)與原來的

一個圓有兩個交點(diǎn)，即被第一個圓截成兩段弧，而每一段弧將原來

的每一個地區(qū)分成兩個地區(qū)，故地區(qū)數(shù)增加了2,即增加了原來圓

的個數(shù)的2倍；當(dāng)畫第三個圓時，應(yīng)與原來的兩個圓共有4個交點(diǎn),

圓弧被截成4段，而每段弧又將原來的每個地區(qū)分成兩個地區(qū)，所

以地區(qū)增加了4,即原來圓的個數(shù)的2倍，…，同理類推，說明遞

推公式應(yīng)該是

ar=a,-l+2(n-1)。

例3在一個圓周上按下面準(zhǔn)則標(biāo)上一些數(shù):第一次先把圓周二平分

在兩個分點(diǎn)旁標(biāo)上:和如圖(a).第二次把兩段半圓弧二等分，在

5/1

分點(diǎn)旁標(biāo)上相鄰兩分點(diǎn)旁所標(biāo)兩數(shù)的和，如圖(b),標(biāo)上工■7+彳.第

三次把4段圓弧分別二平分，并在4個分點(diǎn)左右標(biāo)上兩個相鄰分點(diǎn)旁所

標(biāo)數(shù)的和，如圖(0,分別標(biāo)上a和d+4.如此繼續(xù)下

51/0/0V50/

去，當(dāng)?shù)诎舜螛?biāo)完數(shù)以后，圓周上所有己標(biāo)的數(shù)的和是兒多？

解：

解：我們一般地設(shè)第一次所標(biāo)的兩數(shù)分別為a、b,用￡表示

第k次標(biāo)完后各分點(diǎn)所標(biāo)數(shù)的和.如圖可見

S尸a+b,S2=Si+2S.=3S：=3(a+b)。

原因是這樣的：S2是兩類分點(diǎn)旁的標(biāo)數(shù)和，一類是原來分點(diǎn)

所標(biāo)數(shù)的和S”另一類是新增分點(diǎn)所標(biāo)數(shù)的和，它正好是由原來各

簡略發(fā)覺遞推公式是

Un=U.-l+U,2O

現(xiàn)在說明這個遞推公式是正確的.因為第n個月時的兔子對分

兩類，一類是第n-l個月時的兔子對，另一類是當(dāng)月新生的兔子對,

而這些小兔對數(shù)恰恰是第n-2個月時的兔子對數(shù)u.,.o

有了上面的遞推公式就可以寫出｛□?）的第12項為144對.這

正是本題要求的滿一年時的小兔總對數(shù)。數(shù)列｛uJ稱為斐波那契

數(shù)列（Fibonacci,1170-1250,是意大利數(shù)學(xué)家）,由于數(shù)列｛5｝

具有許多重要的獨(dú)特性質(zhì).因而受到數(shù)學(xué)家們的極大存眷，并把數(shù)

列｛』｝取名為斐波那契數(shù)列.

例5傳說在印度的釋教圣地貝拿勒斯圣廟里布置著個一個黃銅

板，板上插著三根寶石針，在第一根寶石針上，從下到上穿著由大

到小的64片中心有孔的金片.每天都有一個值班僧侶按下面準(zhǔn)則移

動金片：把金片從第一根寶石針移到別的的某根寶石針上.要求一

次只能移動一片，而且小片永遠(yuǎn)要放在大片的上面.當(dāng)時傳說當(dāng)64

片金片都按上面的準(zhǔn)則從第一根寶石針移到另一根寶石針上時，世

界將在一聲轟隆中毀滅.所以有人戲稱這個標(biāo)題叫“世界末日”標(biāo)

題（也稱為“Hanoi塔”標(biāo)題），固然，移金片和世界毀滅并無關(guān)

聯(lián)，這只是一個傳說罷了，但說明這是一個需要移動很多很多次才

華辦到的事情.解這個標(biāo)題的要領(lǐng)在算法剖析中也常用到.結(jié)局發(fā)上

述準(zhǔn)則移動完成64片金片需要移動幾多次呢？解：設(shè)有n片金片，

把從第一片金片至第k片金片按標(biāo)題要求由第I根寶石針移到另一

根寶石針共需移動小次。

先對4片金片的簡略環(huán)境用下列的幾組圖來表示移動歷程中

的各種狀態(tài)，并計數(shù)，概括出遞歸干系式。

這節(jié)的前幾個例子都是“退”到簡略的特殊環(huán)境來概括出一般

紀(jì)律.在這個例子里,我們將先用一般推理得出遞推公式，再以n=64

代入，便可辦理我們這個例題.這種從一般到特殊來辦理標(biāo)題的要

領(lǐng)也是數(shù)學(xué)上的一種常用要領(lǐng)。

我們可以這樣來想：為了移動第n片到第III根寶石針上，我們

必須先把它上面的n-l片按標(biāo)題的準(zhǔn)則采取某種程序移到第II根寶

石針上，這需要移動an-1次.然后才華把最下面第n片（最大的），

稱到第III根寶石針上.最后再議決a1次才華把第II根寶石針上的

n-l片金片按上面準(zhǔn)則采取同樣程序移到第III根寶石針上.因此把n

片金片按題中的準(zhǔn)則全部移到另一根寶石針上共應(yīng)移

a=2a?-l+l(次).(5)

這便是遞推公式。為了求得n=64時的值，我們固然不能一

次次地由a=1,&=3,a3=7,…直到算出時.現(xiàn)在我們設(shè)法把遞推公

式(5)變形為可以直接謀略加的形式。

a.=2a,-l+l=2(2a-,2+1)+1=22a,2+2+1

二22(2a“-3+1)+2+1=23a「3+22+2i+l

—2n-lai+2「升2“-3+…+2+1

=1+2+22+―+2心+2「1,

??a,=2a(,-34.

=2(1+2+22+…+2,-1)-(1+2+…+2'T)

=2,-1,

??3ti(=2Ml-1o

刖是一個特殊大的數(shù).要是按每移動一片次需一秒鐘算，把64

片金片從一根寶石針移到另一根寶石針上大抵需要5800億年。

習(xí)題十四

1.請你根據(jù)下列各個數(shù)之間的干系，在括號里填上適當(dāng)?shù)臄?shù)：

①1,5,9,13,17,()o

②0.625,1.25,2.5,5,()。

④198,297,396,495,(),()。

2.將自然數(shù)1,2,3,…，按圖排列，在“2”處轉(zhuǎn)第一個彎，“3”

處轉(zhuǎn)第二個彎，“5”處轉(zhuǎn)