2022-2023學年奧數(shù)專家點撥小學五年級下冊《遞推方法》試題附答案

狀元必讀專家點緩

小學五年級下冊數(shù)學奧數(shù)知識點講解第13課《遞推方法》試題附答案

第十四講遞推方法

遞推方法是人們從開始認識數(shù)量關系時就很自然地產(chǎn)生的一種推理思想.例

如自然數(shù)中最小的數(shù)是1,比1大1的數(shù)是2,接下來比2大1的數(shù)是3,…由此得

到了自然數(shù)數(shù)列：1,2,3,4,5,….在這里實際上就有了一個遞推公式，假

設第n個數(shù)為5則

an-l=an+1

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

4+2=4+I+1，

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

再看一個例子：

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

囪的內(nèi)部分成幾部分？

例2平面上10個兩兩相交的圓最多能將平面分割成多少個區(qū)域？平面上1993個

圓最多能將平面分割成多少個區(qū)域？

例3在一個圓周上按下面規(guī)則標上一些數(shù)：第一次先把圓周二等分，

在兩個分點旁標上q和右如圖（a）.第二次把兩段半圓弧二等分，在

分點旁標上相鄰兩分點旁所標兩數(shù)的和，如圖（b）,標上亮［;+g）第

三次把4段圓弧分別二等分，并在4個分點旁邊標上兩個相鄰分點旁所

標數(shù)的和，如圖G）,分別標上中f斜出3|）.如此繼續(xù)下

去，當?shù)诎舜螛送陻?shù)以后，圓周上所有己標的數(shù)的和是多少?

例5傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個一個黃銅板，板上插

著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心

有孔的金片.每天都有一個值班僧侶按下面規(guī)則移動金片：把金片從第一

根寶石針移到其余的某根寶石針上.要求一次只能移動一片，而且小片永

遠要放在大片的上面.當時傳說當64片金片都按上面的規(guī)則從第一根寶石

針移到另一根寶石針上時，世界將在一聲霹靂中毀滅.所以有人戲稱這個

問題叫“世界末日”問題（也稱為“Han。諧”問題），當然,移金片和

世界毀滅并無聯(lián)系，這只是一個傳說而己，但說明這是一個需要移動很

多很多次才能辦到的事情解這個問題的方法在算法分析中也常用到.究竟

按上述規(guī)則移動完成64片金片需要移動多少次呢？解：設有n片金片，把

從第一片金片至第k片金片按題目要求由第4艮寶石針移到另一根寶石針共

需移動4次。

先對4片金片的簡單情形用下列的幾組圖來表示移動過程中的各種狀

態(tài)，并計數(shù)，歸納出遞歸關系式。

答案

笫十四講遞推方法

遞推方法是人們從開始認識數(shù)量關系時就很自然地產(chǎn)生的一種推理思想.例

如自然數(shù)中最小的數(shù)是1,比1大1的數(shù)是2,接下來比2大1的數(shù)是3,…由此得

到了自然數(shù)數(shù)列：1,2,3,4,5,….在這里實際上就有了一個遞推公式，假

設第n個數(shù)為4則

an，l=an+1

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

4.+2=4+i+1,

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

再看一個例子：

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

圓的內(nèi)部分成幾部分？

解:

假設用與表示k條直線最多能把圓的內(nèi)部分成的部分數(shù).這里k=0,1,2,

…一如圖可見。

,=]

4=3c+1=2

,二己工+2=4

a3=a-+3=7

a4=a3+4=11

歸納出遞推公式4+1=4rI.（1）

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

圓分成兩部分，故a,=2.當畫第二條直線時要想把圓內(nèi)部分割的部分盡可能

多，就應和第一條直線在圓內(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)分成多少區(qū)域，不能直接用上面公式

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

+=

aJ.=a,-liinI1_-+（n-1）+n

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

=???=1+1+2+…+n=l+n'n：D(2)

2

100X101…八、

..a100=H------------=5051(部分)o

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

一般來說，如果一個與自然數(shù)有關的數(shù)列中的任一項與可以由它前面的k

?n-l）項經(jīng)過運算或其他方法表示出來，我們就稱相鄰項之間有遞歸關系，

并稱這個數(shù)列為遞歸數(shù)列.如果這種推算方法能用公式表示出來，就稱這種公式

為遞推公式或遞推關系式.通過尋求遞歸關系來解決問題的方法就稱為遞推方

法.許多與自然數(shù)有關的數(shù)學問題都常常具有遞推關系，可以用遞推公式來表達

它的數(shù)量關系.如何尋求這個遞推公式是解決這類問題的關鍵之一，常用的方法

是“退”到問題最簡單情況開始觀察.逐步歸納并猜想一般的速推公式.在小學

生階段，我們僅要求學生能撥開問題的一些表面現(xiàn)象由簡到繁地歸納出問題的

遞推公式就行了，不要求嚴格證明一當然能證明更好.所謂證明，就是要嚴格推

出你建立的關系式適合所有的n,有時，僅僅在前面幾項成立的關系式，不一定

當n較大時也成立。

例2平面上10個兩兩相交的圓最多能將平面分割成多少個區(qū)域？平面上1993個

圓最多能將平面分割成多少個區(qū)域？

解：設平面上k個圓最多能將平面分割成a,部分.我們先“退”到最簡單的

情形如圖可見

ax=2,a:=4=2+2X1,

a3=8=4+2X2,

a4=14=8+2X3,

ar=ar-l+2(n-1).(3)

(3)是這個問題的遞推公式再把它變形為當蹶大時也能方便求出

結果的公式：

4=3sT+2(n-1)

=an..+2[(n-2)+(n-1)]

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

=???=a1+2(1+2+3+,,-+n-2-hi-1)

_n(n-1),

—2o+2oXy——----=n2-n+2o

2

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

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

關于這個遞推公式成立的正確性分析與例1完全類似.比如，第一個圓

顯然將平面分為兩個區(qū)域；當畫第二個圓時，應與原來的一個圓有兩個

交點，即被第一個圓截成兩段弧，而每一段弧將原來的每一個區(qū)域分成

兩個區(qū)域，故區(qū)域數(shù)增加了2,即增加了原來圓的個數(shù)的2倍；當畫第三

個圓時，應與原來的兩個圓共有4個交點，圓弧被截成4段，而每段弧又

將原來的每個區(qū)域分成兩個區(qū)域，所以區(qū)域增加了4,即原來圓的個數(shù)的

2倍，…，同理類推，說明遞推公式應該是

Wl+2(n-1)。

例3在一個圓周上按下面規(guī)則標上一些數(shù)：第一次先把圓周二等分，

在兩個分點旁標上［和提如圖(a),第二次把兩段半圓弧二等分，在

分點旁標上相鄰兩分點旁所標兩數(shù)的和，如圖(b),標上.(=；+§,第

三次把4段圓弧分別二等分，并在4個分點旁邊標上兩個相鄰分點旁所

標數(shù)的和，如圖G),分別標上中［+W和4fl).如此繼續(xù)下

去，當?shù)诎舜螛送陻?shù)以后，圓周上所有己標的數(shù)的和是多少?

解:

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

完后各分點所標數(shù)的和.如圖可見

Si=a+b,S2=S1+2S1=3S1=3(a+b)。

原因是這樣的：S2是兩類分點旁的標數(shù)和，一類是原來分點所標數(shù)

的和S1，另一類是新增分點所標數(shù)的和，它正好是由原來各分點所標的數(shù)

向左加一次，又向右加一次的和，故新增分點旁所標數(shù)的和恰好是原來

所有數(shù)之和的2倍2S1，因此有

S2=S1+2S1=3SJ同理類推

S3=S2+2S2=3s2=32S],

S4=32S1+2X32SI=32S],

Sr311Tsi=3_1（a+b）（4）

（4）式為遞推公式：在S1=a+b時己解出的表達式.所謂解

出，即S.直接依賴于n與S,而計算出.不再是$￡依賴于Sr-1,S門又依賴于

Si…這樣的形式。

例5傳說在印度的佛教圣地貝拿勒斯圣廟里安放著個一個黃銅板，板上插

著三根寶石針，在第一根寶石針上，從下到上穿著由大到小的64片中心

有孔的金片每天都有一個值班僧侶按下面規(guī)則移動金片：把金片從第一

根寶石針移到其余的某根寶石針上.要求一次只能移動一片，而且小片永

遠要放在大片的上面.當時傳說當64片金片都按上面的規(guī)則從第一根寶石

針移到另一根寶石針上時，世界將在一聲霹靂中毀滅.所以有人戲稱這個

問題叫“世界末日”問題（也稱為“Han。諧”問題），當然，移金片和

世界毀滅并無聯(lián)系，這只是一個傳說而己，但說明這是一個需要移動很

多很多次才能辦到的事情解這個問題的方法在算法分析中也常用到.究竟

按上述規(guī)則移動完成64片金片需要移動多少次呢？解：設有n片金片，把

從第一片金片至第k片金片按題目要求由第4艮寶石針移到另一根寶石針共

需移動4次。

先對4片金片的簡單情形用下列的幾組圖來表示移動過程中的各種狀

態(tài)，并計數(shù)，歸納出遞歸關系式。

W=4n［簾一片壯到JL

初始狀壬幣=i

第!/；,皿第一片移到HL

卷到皿（第1、2片格

到D［充成）

a

a2=2zi+1

二3（次J

第3井1亞第DL在上的研片移到1L

百到U上,第1、2、3片移到

上完成

第4片I1皿第U柱上的兩片移到亞

蒼到亞上,第1、2、3、片移

到柱皿上先成

2----84=2打+1

=15（次j

這節(jié)的前幾個例子都是“退''到簡單的特殊情況來歸納出一般規(guī)律.

在這個例子里，我們將先用一般推理得出遞推公式，再以n=64代入，便

可解決我們這個例題.這種從一般到特殊來解決問題的方法也是數(shù)學上的

一種常用方法。

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

把它上面的nJ片按題目的規(guī)則采用某種程序移到第II根寶石針上，這需

要移動an-1次.然后才能把最下面第n片（最大的），稱到第IH根寶石針上.

最后再經(jīng)過4-1次才能把第II根寶石針上的nJ片金片按上面規(guī)則采用同樣

程序移到第而根寶石針上因此把n片金片按題中的規(guī)則全部移到另一根寶

石針上共應移

4=231rl+1（次）.（5）

這就是遞推公式。為了求得n=64時匕的值，我們當然不能一次次地

由a1=La*3,a3=7,…直到算出也現(xiàn)龍我們設法把遞推公式（5）變形

為由以直接計算?的形式。

二,=24-1+1=2（2a,,.:+1）+1=224.1+2+1

=22（2an-3+l）+2+1=23ali-3+22+2J1

=2*-呵+2丁2+21r3+―+2+1

=l+2+22+-+2n_2+2r-l,

?'?4=2'-4

=2（1+2+22+,?,+2B-1）-（1+2+…+2，）

=2:1，

.,.、=2丈1。

不是一個非常大的數(shù).如果按每移動一片次需一秒鐘算，把64片金片

從一根寶石針移到另一根寶石針上大約需要580陀年。

習題十四

1.請你根據(jù)下列各個數(shù)之間的關系，在括號里填上恰當?shù)臄?shù):

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

③22幺上…3

10T6'22'28'58'

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

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

一?22f23-----------

8f9f1

12

1—1

>

1—2

?

16-15—14—

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

二個彎，“5”處轉(zhuǎn)第三個彎，….問哪個數(shù)處轉(zhuǎn)第二十個彎？

3.請用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少種不同

站法？

4.上一段12級樓悌，規(guī)定每一步只能上一級或兩級.問要登上第12級樓梯共

有多少種不同走法？

5.有10個村莊，分別用A/A:,???,\：表示，某人從A1出發(fā)按箭頭方向繞

一圈最后經(jīng)由A1：再回到A】，有多少種不同走法？

注：每點(村)至多過一次，兩村之間，可走直線，也可走圓周上弧線,

但都必須按箭頭方向走.

五年級奧數(shù)下冊：第十四講遞推方法習題解答

習題十四解答

1.①;相鄰兩數(shù)的差均為4,故括號里應填17+4=21o

②：1.25-0.625=0.625,

2.5-1.25=1.25,

3.525=25

可見差正好等于減數(shù)。

()-5=5,

/.()=5+5=10。

或者：后一個數(shù)為前一個數(shù)的2倍，故

括號里應填2X5=10。

③:從數(shù)列可見分子從2開始逐個增大15分母從10開始逐個增

大6,要填()，須先知道二^是第幾個數(shù).分母順序為：10,16,

JO

22,28,34,40,46,52,58。

..?這個分數(shù)為第9個數(shù)。

..?括號里應填10。

④十位上數(shù)不變，百位上數(shù)依次遞增1,個位上數(shù)依次遞減1,故括號中數(shù)

應填594,693。

2.解：拐彎處數(shù)的規(guī)律可見下頁表。

拐彎處序號拐彎處的數(shù)前后關系

①21+①=2

②32+9=3

③53+②=5

75+②=7

⑤107+③=10

⑥1310+③=13

⑦1713+@=17

2117+④=21

??.第19個拐彎處的數(shù)比第18個拐彎處的數(shù)大10,第20個拐彎處的數(shù)比第19

個拐彎處的數(shù)也大10,故第20個拐彎處的數(shù)為：

1+2X(1+2+3+-+10)=111。

3解：假設n個人站成一排共有4種不同站法.可以先讓其中的n-l個人站成

一排，共有乙,種不同的站法，再讓廁下的那個人站在他們中間或兩頭，又有n

種站法.由乘法:原理，可得到遞推公式：

4=nXj。

又...4=1,

.,.a4=4Xa,=4X3Xa.=4X3X2Xai=4!=24,

4.解：設登上該樓梯共有a.種不同走法，n=l,2,….把上到第遨樓梯的

情形分為兩種走法.一類是先上到第n-l級樓梯，然后再上一級，共有4T種走法.

另一類是先上到第n-2級樓梯，然后再上兩級，共有a_［種走法.由加法原理，上

到第薇樓梯的走法4滿足下列遞推關系式：

ar=ar.-l+ar.-2°

又...藥=1,&=2,故上樓梯方法數(shù)與.依次為1,2,3,5,8,13,21,34,

55,89,144,233,…一

???上到第12級樓梯共有233種不同走法。