2022-2023學(xué)年奧數(shù)專家點(diǎn)撥小學(xué)五年級(jí)下冊(cè)《遞推方法》試題附答案

狀元必讀專家點(diǎn)緩

小學(xué)五年級(jí)下冊(cè)數(shù)學(xué)奧數(shù)知識(shí)點(diǎn)講解第13課《遞推方法》試題附答案

第十四講遞推方法

遞推方法是人們從開始認(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ù)為5則

an-l=an+1

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

4+2=4+I+1，

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

再看一個(gè)例子：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

遠(yuǎn)要放在大片的上面.當(dāng)時(shí)傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石

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

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

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

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

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

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

需移動(dòng)4次。

先對(duì)4片金片的簡單情形用下列的幾組圖來表示移動(dòng)過程中的各種狀

態(tài)，并計(jì)數(shù)，歸納出遞歸關(guā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ù)為4則

an，l=an+1

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

4.+2=4+i+1,

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

再看一個(gè)例子：

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

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

解:

假設(shè)用與表示k條直線最多能把圓的內(nèi)部分成的部分?jǐn)?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條直線時(shí)，最多增加n部分原因是這樣的：第一條直線最多把

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

多，就應(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)分成多少區(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,…的通項(xiàng)公式

一般來說，如果一個(gè)與自然數(shù)有關(guān)的數(shù)列中的任一項(xiàng)與可以由它前面的k

?n-l）項(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)系.如何尋求這個(gè)遞推公式是解決這類問題的關(guān)鍵之一，常用的方法

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

生階段，我們僅要求學(xué)生能撥開問題的一些表面現(xià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è)圓最多能將平面分割成a,部分.我們先“退”到最簡單的

情形如圖可見

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

a3=8=4+2X2,

a4=14=8+2X3,

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

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

結(jié)果的公式：

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(個(gè))，

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

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

顯然將平面分為兩個(gè)區(qū)域；當(dāng)畫第二個(gè)圓時(shí)，應(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)該是

Wl+2(n-1)。

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

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

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

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

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

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

解:

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

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

Si=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=3SJ同理類推

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

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

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

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

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

Si…這樣的形式。

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

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

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

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

遠(yuǎn)要放在大片的上面.當(dāng)時(shí)傳說當(dāng)64片金片都按上面的規(guī)則從第一根寶石

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

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

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

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

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

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

需移動(dòng)4次。

先對(duì)4片金片的簡單情形用下列的幾組圖來表示移動(dòng)過程中的各種狀

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

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é)的前幾個(gè)例子都是“退''到簡單的特殊情況來歸納出一般規(guī)律.

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

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

一種常用方法。

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

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

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

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

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

石針上共應(yīng)移

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

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

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

為由以直接計(jì)算?的形式。

二,=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。

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

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

習(xí)題十四

1.請(qǐng)你根據(jù)下列各個(gè)數(shù)之間的關(guān)系，在括號(hào)里填上恰當(dāng)?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)第一個(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è)村莊，分別用A/A:,???,\：表示，某人從A1出發(fā)按箭頭方向繞

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

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

但都必須按箭頭方向走.

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

習(xí)題十四解答

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

②：1.25-0.625=0.625,

2.5-1.25=1.25,

3.525=25

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

()-5=5,

/.()=5+5=10。

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

括號(hào)里應(yīng)填2X5=10。

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

大6,要填()，須先知道二^是第幾個(gè)數(shù).分母順序?yàn)椋?0,16,

JO

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

..?這個(gè)分?jǐn)?shù)為第9個(gè)數(shù)。

..?括號(hào)里應(yīng)填10。

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

應(yīng)填594,693。

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

拐彎處序號(hào)拐彎處的數(shù)前后關(guān)系

①21+①=2

②32+9=3

③53+②=5

75+②=7

⑤107+③=10

⑥1310+③=13

⑦1713+@=17

2117+④=21

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

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

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

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

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

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

4=nXj。

又...4=1,

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

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

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

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

到第薇樓梯的走法4滿足下列遞推關(guān)系式：

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

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

55,89,144,233,…一

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