五年級下冊數學奧數專題講座第十四課《遞推方法》難題練習及題目答案

五年級奧數下冊：第十四講遞推方法

第十四講遞推方法

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

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

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

設第n個數為?則

a>i=ar+l

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

4+2=4+1+1,

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

再看一個例子：

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

圓的內部分成幾部分？

解：

假設用，表示k條直線最多能把圓的內部分成的部分數.這里k=0,1,2,

….如圖可見。

%V=1

a=a.+l=2

a2=aL+2=4

a3=a4.+3=7

a4=a3+4=11

歸納出遞推公式Q）

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

圓分成兩部分，故d=2.當畫第二條直線時要想把圓內部分割的部分盡可能

多，就應和第一條直線在圓內相交，交點把第二條直線在圓內部分分成兩條線

段，而每條線段又把原來的一個區域劃分成兩個區域，因而增加的區域數是

2,正好等于第二條直線的序號.同理，當畫第三條直線時，要想把圓內部分割

的部分數盡可能多，它就應和前兩條直線在圓內各有一個交點兩個交點把第三

條線在圓內部分成三條線段.而每條線段又把原來一個區域劃分成兩個區域.因

而增加的區域部分數是3,正好等于笫三條直線的序號，….這個道理適用于任

意多條直線的情形所以遞推公式（1）是正確的.這樣就易求得5條直線最多把

圓內分成：

a5=a4+5=11=5=16（部分）。

要想求出100條直線最多能把圓內分成多少區域，不能直接用上面公式

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

74=4-1+0=11^+（n-1）+n

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

n(n+1)

…=1+1+2+…+n=l+

2-

100X101

??"⑼=1+~—5051（部分）。

乙

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

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

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

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

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

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

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

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

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

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

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

當嫉大時也成立。

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

圓最多能將平面分割成多少個區域？

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

情形如圖可見

a:=2,『=2+2X1,

a3=8=44-2X2,

a4=14=8+2X3,

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

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

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

分點旁標上相鄰兩分點旁所標兩數的和，如圖(b),標上4=:+;).第

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

標數的和，如圖(c),分別標上1+|?和12(=:+.如此繼續下

3\2b)b\3b)

去，當笫八次標完數以后，圓周上所有己標的數的和是多少？

解：

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

完后各分點所標數的和.如圖可見

SI=a+b,S2=S.+2S.=3S1=3(a+b)。

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

的和"，另一類是新增分點所標數的和，它正好是由原來各分點所標的數

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

所有數之和的2倍2S.,因此有

S2=S1+2S.=3S:,同理類推

S3=S2+2S2=3S2=32S.,

S4=32S1+2X32S,=32S1,

Sr3門S產3r（a+b）（4）

（4）式為遞推公式：SxUBS.-l在S]=a+b時已解出的表達式.所謂解

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

S-…這樣的形式。

月份兔了戲費r

O表示未成熟的免于對

?表示可生小兔的兔彳對

第一個月：只有1對小兔。

笫二個月：一對小兔長成一對大兔，但尚不會生殖仍只有一對兔

子。

第三個月：這對大兔生了一對小兔，這時共2對兔子。

第四個月：大兔又生了一對小兔，而上月出生的小兔正在長大，這

時共3對兔子。

第五個月：這時己有兩對大兔可以生殖（原來的大兔和第三個月出

生的小兔），于是生了兩對小兔，這時共有5對兔子。

把推算的結果列成一張表

月份數一二三四五六七A九■1*十二十三■■■

兔對數112二；58132134E589144233???

由表中可見滿一年時可得144對兔子。

,如果要算的時間長，這種方法就有困難了，現在我們來找遞推關

系。

用｛%｝表示第口個月時的兔子對數，則

｛%｝：1,1,2,3,5,8,13,21,3%…。

容易發現遞推公式是

現在說明這個遞推公式是正確的.因為第n個月時的兔子對分兩類，一

類是第nJ個月時的兔子對，另一類是當月新生的兔子對，而這些小兔對

數恰好是第n?2個月時的兔子對數％工。

有了上面的遞推公式就可以寫出｛uj的第12項為144對.這正是本題

要求的滿一年時的小兔總對數。數列｛%｝稱為斐波那契數列

（Fibonacci,11"0—1250,是意大利數季家）.由于數列｛1｝具有許多重

要的奇特性質.因而受到數學家們的極大關注，并把數列w取名為斐

波那契數列.

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

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

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

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

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

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

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

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

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

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

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

需移動4次。

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

態，并計數，歸納出遞歸關系式。

”4吊一片材納JL

初始獻$=i（it>

海2；：-迎第一片移到n

（電、2片移

到in完成）

a；m+]

=3（次j

m第3片1亞第D［在上的兩片移到U

見君到JL

上，第1、2、3片移到

上完成

2--

3二二

u第1［在上的畫片移到IE

上,第1、2、3、片移

到在DLL完成

3

3二二1一2--——2--&4=2a3+1

mmAnnmnnnrfnmmnnmhnnn=15（ftj

這節的前幾個例子都是“退”到簡單的特殊情況來歸納出一般規律.

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

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

一種常用方法。

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

把它上面的n-1片按題目的規則采用某種程序移到笫H根寶石針上，這需

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

最后再經過arT次才能把第II根寶石針上的nJ片金片按上面規則采用同樣

程序移到第III根寶石針上.因此把n片金片按題中的規則全部移到另一根寶

石針上共應移

4=20.7+1（次）.（5）

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

由4=1,干3,a3=7,…直到算出—現在莪們設法把遞推公式（5）變形

為由以直接計算a“的形式。

^=221.-1+1=2（2芍.+1）+l=22ar_:+2+1

=22（2aX*-3+1）-*-2X+I1=23a-3X+22+2+1

??

=2r-l%+2T+2/3+-?+2+1

=1+2+22+…+2c-4.+2n-1,

???4=24-4

=2（1+2+22+.??+2］一1）-（1+2+---+2--1）

=2j

64

aS4=2-lo

與：是一個非常大的數.如果按每移動一片次需一秒鐘算，把64片金片

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

五年

級奧數下冊：第十四講遞推方法習題

習題十四

1.請你根據下列各個數之間的關系，在括號里填上恰當的數:

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

③23W上…3

10T6'22'28'58'

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

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

41f22f23..........；

20jf8f9-10

19；ii

fI|：

185—312j

17-4—16-*—15-<—13;

2.將自然數1,2,3,…，按圖排列，在“2”處轉第一個彎，“3”處轉第

二個彎，“5”處轉第三個彎，….問哪個數處轉第二十個彎？

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

站法？

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

有多少種不同走法？

5.有10個村莊，分別用A1，A:,%：表示，某人從A1出發按箭頭方向繞

一圈最后經由A二再回到A】，看多少種不同走法？

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

但都必須按箭頭方向走.

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

習題十四解答

L①;相鄰兩數的差均為4,故括號里應填17-4=21。

②??T.25?0.625=0.625,

2.5-1.25=1.25,

3.5-25=2.5,

可見差正好等于減數。

:?（）-5=5,

（）=5+5=10。

或者：后一個數為前一個數的2倍，故

括號里應填2X5=10。

③從數列可見分子從2開始逐個增大1；分母從10開始逐個增

大6,要填（），須先知道二是第幾個數?分母順序為：16,

JO

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

??.這個分數為第9個數。

???括號里應填10。

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

應填594,693o

2解：拐彎處數的規律可見下頁表。

拐彎處序號拐彎處的數前后關系

①21?①二2

②32?①二3

③53?②二5

④75+②=7

⑤107?③=10

⑥1310?③二13

⑦1713+@=17

⑧2117+④=21

.■■

■.■

??.第19個拐彎處的數比笫18個拐彎處的數大10,第20個拐彎處的數比第19

個拐彎處的數也大10,故第20個拐彎處的數為：

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

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

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

種站法住乘和原理，可得到遞推公式：

4=口乂4-1。

又二a.=1,

.*.a4=4Xa,=4X3Xa2=4X3X2Xai=4!=24。

4解設登上讖樓悌共有a.種不同走法，n=l,2,….把上到第酸樓悌的

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

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

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

an=ar.-l+an-2<>

X*/a.=l,a:=2,故上樓梯方法數4依次為1,2,3,5,8,13,21,34,

55,89,144,233,….

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

5解：設從A：按箭頭方向走到An+1的走法數為4,n=l,2,…，9.則a9即為

所求（因為從A10回到A1只有一種方式）.可見，a：=l,a：=2,a<+i=ak+a1為遞

推公式。*

Aa（n=l,2,…，9）依次為1,2,3,5,8,13,21,34,55.即共55種

不同的走法。也可以用圖來表示解答過程.

每一個村（點）旁邊的數字就是到這村的K同走法個數正好符合斐波那契

數列的特點。

從A.出發走到A：點只有一種方式，&點標有數目L從A，到An一種直接沿

圓弧走，另一種途經A.走，所以共有1+1=2種方式，從A,朝A“有兩種方

式，一種途經A二再沿忒&到A,的直線走，另一種途經A己到A」.所以總方式數目等

于A1到A；的方式數加A1到的方式數。

也即（A「f）方式數

=（AlffA2）方式數+（A1ffA3）方式數

=1+2

=3。

其余類推.

以下資料為班級建設資料，有需要可以用：《滴水精神》主題班會

活動目的：教育學生懂得“水”這一寶貴資源對于我們來說是極為珍貴的，每

個人都要保護它，做到節約每一滴水，造福子孫萬代。

活動過程：

1.主持人上場，神秘地說：“我讓大家猜個謎語，你們愿意嗎？"大家回答:

“愿意！”

主持人口述謎語:

“雙手抓不起，一刀劈不開,

煮飯和洗衣，都要請它來

主持人問：“誰知道這是什么？”生答：“水！”

一生戴上水的頭飾上場說：“我就是同學們猜到的水。聽大家說，我的用處

可大了，是真的嗎？”

主持人：我宣布：“水”是萬物之源主題班會現在開始。

水說：“同學們，你們知道我有多重要嗎？”齊答：“知道。”

甲：如果沒有水，我們人類就無法生存。

小熊說：我們動物可喜歡你了，沒有水我們會死掉的。

花說：我們花草樹木更喜歡和你做朋友，沒有水，我們早就枯死了，就不能

為美化環境做貢獻了。

主持人：下面請聽快板《水的用處真叫大》

竹板一敲來說話,水的用處真叫大；

洗衣服，洗碗筷,洗臉洗手又洗腳，

煮飯洗菜又沏茶,生活處處離不開它

栽小樹，種莊稼,農民伯伯把它有;

魚兒河馬大對蝦,日日夜夜不離它；

采煤發電要靠它,京城美化更要它。

主持人：同學們,聽完了這個快板，你們說水的用處大不大?

甲說：看了他們的快板表演，我知道日常生活種離不了水。

乙說：看了表演后，我知道水對莊稼、植物是非常重要的。

丙說：我還知道水對美化城市起很大作用。

2.主持人：水有這么多用處，你們該怎樣做呢？

（1）（生）：我要節約用水，保護水源。

（2）（生）：我以前把水壺剩的水隨便就到掉很不對，以后我一定把喝剩下

的水倒在盆里洗手用。

（3）（生）：前幾天，我看到了學校電視里轉播的“水日談水”的節目，很

受教育，同學們看得可認真了，知道了我們北京是個缺水城市，我們再不能浪費

水了。

（4）（生）：我要用洗腳水沖廁所。

3.主持人：大家談得都很好，下面誰想出題考考大家，答對了請給點掌聲。

（1）（生）：小明讓爸爸刷車時把水龍頭開小點，請回答對不對。

（2）（生）：小蘭告訴奶奶把洗菜水別到掉，留沖廁所用。

（3）一生跑上說：主持人請把手機借我用用好嗎？我想現在就給姥姥打個

電話，告訴她做飯時別把淘米水到掉了，用它沖廁所或澆花用。（電話內容略寫）

（4）一生說：主持人我們想給大家表演一個小品行嗎？

主持人：可以，大家歡迎！請看小品《這又不是我家的》

大概意思是：學校男廁所便池堵了，水龍頭又大開，水流滿地。學生甲乙丙

二人分別上廁所，看見后乂皺眉乂罵，但都沒有關水管，嘴里還念念有詞，又說:

“反正不是我家的。”

旁白：“那又是誰家的呢？”

主持人：看完這個小品，你們有什么想法嗎？誰愿意給大家說說？

甲：剛才三個同學太自私了，公家的水也是大家的，流掉了多可惜，應該把

水龍頭關上。

乙：上次我去廁所看見水龍頭沒關就主動關上了。

主持人：我們給他鼓鼓掌，今后你們發現水龍頭沒關會怎樣做呢？

齊：主動關好。

小記者：同學們，你們好！我想打擾一下，聽說你們正在開班會，我想采訪

一下，行嗎？

主持人：可以。

小記者：這位同學，你好！通過參加今天的班會你有什么想法，請淡談好嗎？

答：我要做節水的主人，不浪費一滴水。

小記者：請這位同學談談好嗎？

答：今天參加班會我知道了節約每一滴水要從我們每個人做起。我想把每個

廁所都貼上“節約用水”的字條，這樣就可以提醒同學們節約用水了。

小記者：你們談得很好，我的收獲也很大。我還有新任務先走了，同學們再

見!

水跑上來說：同學們，今天我很高興，我“水伯伯”今天很開心，你們知道

了有了我就有了生命的源泉，請你們今后一定節約用水呀！讓人類和動物、植物

共存，迎接美好的明天！

主持人：你們還有發言的嗎？

答：有。

生：我代表人們謝謝你，水伯伯，節約用水就等于保護我們人類自己。

動物：小熊上場說：我代表動物家族謝謝你了，我們也會保護你的！

花草樹木跑上場說：我們也不會忘記你的貢獻！

水伯伯：（手舞足蹈地跳起了舞蹈）……同學們的笑聲不斷。

主持人：水伯伯，您這是干什么呢？

水伯伯：因為我太高興了，今后還請你們多關照我呀！

主持人：水伯伯，請放心，今后我們一定會做得更好！再見！

4.主持人：大家歡迎老師講話！

同學們，今天我們召開的班會非常生動，非常有意義。水是生命之源，無比

珍貴，愿同學們能加倍珍惜它，做到節約--滴水，造福子孫后代。

5.主持人宣布：“水”是萬物之源主題班會到此結束。

6.活動效果：

此次活動使學生明白了節約用水的道理，浪費水的現象減少了，宣傳節約用

水的人增多了，人人爭做節水小標兵

活動目的：教育學生懂得“水”這一寶貴資源對于我們來說是極為珍貴的，每

個人都要保護它，做到節約每一滴水，造福子孫萬代。

活動過程：

1.主持人上場，神秘地說：“我讓大家猜個謎語，你們愿意嗎？"大家回答:

“愿意！”

主持人口述謎語：

“雙手抓不起，一刀劈不開，

煮飯和洗衣，都要請它來。”

主持人問：“誰知道這是什么？”生答：“水！”

一生戴上水的頭飾上場說：“我就是同學們猜到的水。聽大家說，我的用處

可大了，是真的嗎？”

主持人：我宣布：“水”是萬物之源主題班會現在開始。

水說：“同學們，東們知道我有多重要嗎？”齊答：“知道。”

甲：如果沒有水，我們人類就無法生存。

小熊說：我們動物可喜歡你了，沒有水我們會死掉的。

花說：我們花草樹木更喜歡和你做朋友，沒有水，我們早就枯死了，就不能

為美化環境做貢獻了。

主持人：下面請聽快板《水的用處真叫大》

竹板一敲來說話,水的用處真叫大;

洗衣服，洗碗筷，洗臉洗手乂洗腳，

煮飯洗菜又沏茶，生活處處離不開它。

栽小樹，種莊稼，農民伯伯把它夸;

魚兒河馬大對蝦，日日夜夜不離它;

采煤發電要靠它，京城美化更要它。

主持人：同學們，聽完了這個快板，你們說水的用處大不大？

甲說：看了他們的快板表演，我知道日常生活種離不了水。

乙說：看了表演后，我知道水對莊稼、植物是非常重要的。

丙說：我還知道水對?美化城市起很大作用。

2.主持人：水有這么多用處，你們該怎樣做呢？

（1）（生）：我要節約用水，保護水源。

（2）（生）：我以前把水壺剩的水隨便就到掉很不對，以后我一定把喝剩下

的水倒在盆里洗手用。

（3）（生）：前幾天，我看