小學(xué)奧數(shù)教程-計數(shù)之遞推法 教師版全國通用（含答案）

目混

前面在講加法原理、乘法原理、排列組合時已經(jīng)穿插講解了計數(shù)中的一些常用的方法，比如枚舉法、樹

形圖法、標(biāo)數(shù)法、捆綁法、排除法、插板法等等，這里再集中學(xué)習(xí)一下計數(shù)中其他常見的方法，主要有歸納

法、整體法、對應(yīng)法、遞推法.對這些計數(shù)方法與技巧要做到靈活運用.

對于某些難以發(fā)現(xiàn)其一般情形的計數(shù)問題，可以找出其相鄰數(shù)之間的遞歸關(guān)系，有了這一遞歸關(guān)系就可

以利用前面的數(shù)求出后面未知的數(shù)，這種方法稱為遞推法.

【例1】每對小兔子在出生后一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來.如果一個人

在一月份買了一對小兔子，那么十二月份的時候他共有多少對兔子？

【考點】計數(shù)之遞推法【難度】3星【題型】解答

【解析】第一個月，有1對小兔子；第二個月，長成大兔子，所以還是1對；第三個月，大兔子生下一對小

兔子，所以共有2對；第四個月，剛生下的小兔子長成大兔子，而原來的大兔子又生下一對小兔子，

共有3對；第五個月，兩對大兔子生下2對小兔子，共有5對；……這個特點的說明每月的大兔子

數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，即上上月的兔子數(shù)，所以每月的兔子數(shù)為

上月的兔子數(shù)與上上月的兔子數(shù)相加.依次類推可以列出下表：

經(jīng)過月數(shù)：—1—2—3—4—5—6—7—8—9—10—11—12

兔子對數(shù)：-一1一1-2-3-5--8-13-21-34-55-89—144,所以十二月份的時候總共有144對兔子.

【答案】144

【例2】樹木生長的過程中，新生的枝條往往需要一段“休息”時間供自身生長，而后才能萌發(fā)新枝.一棵樹

苗在一年后長出一條新枝，第二年新枝“休息”，老枝依舊萌發(fā)新枝；此后，老枝與“休息”過一年的

枝同時萌發(fā)，當(dāng)年生的新枝則依次“休息”.這在生物學(xué)上稱為“魯?shù)戮S格定律”.那么十年后這棵樹

上有多少條樹枝？

【考點】計數(shù)之遞推法【難度】3星【題型】解答

【解析】一株樹木各個年份的枝才亞數(shù)，構(gòu)成斐波那契數(shù)列：1,2,3,5,8,13,21,34,55,89,……所以

十年后樹上有89條樹枝.

【答案】89

【例3】一樓梯共1()級，規(guī)定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法?

【考點】計數(shù)之遞推法【難度】4星【題型】解答

Aio-

【解析】登1級2級

1種方法2種

我們觀察每級的種數(shù)，發(fā)現(xiàn)這么一個規(guī)律：從第三個數(shù)開始，每個數(shù)是前面兩個數(shù)的和；依此規(guī)律

我們就可以知道了第10級的種數(shù)是89.其實這也是加法的運用：假如我們把這個人開始登樓梯的位

置看做Ao,那么登了1級的位置是在Ai,2級在A2...Ao級就在Aio.到A3的前一步有兩個位置：分

別是上和Ai.在這里要強調(diào)一點，那么42到小既然是一步到了，那么A2、4之間就是一種選

擇了；同理4到A3也是一種選擇了.同時我們假設(shè)到〃級的選擇數(shù)就是A”.那么從A）至4A3就

可以分成兩類了：第一類：A0-一A1——A3,那么就可以分成兩步.有Alxl種，也就是A1種；

（41——A3是一種選擇）第二類：4）--A2——43,同樣道理有A2.類類相加原理：43=A1+

A2,依次類推A”=An-\+An-2.

【答案】89

【鞏固】一樓梯共10級，規(guī)定每步只能跨上一級或三級，要登上第10級，共有多少種不同走法?

【考點】計數(shù)之遞推法【難度】4星【題型】解答

1種方法1種2種3種4種......?

我們觀察每級的種數(shù)，發(fā)現(xiàn)這么一個規(guī)律：從第三個數(shù)開始，每個數(shù)是前面相隔的兩個數(shù)的和；依

此規(guī)律我們就可以知道了第10級的種數(shù)是28.

【答案】28

【例4】1x2的小長方形（橫的豎的都行）覆蓋2x10的方格網(wǎng)，共有多少種不同的蓋法.

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】如果用1x2的長方形蓋2x〃的長方形，設(shè)種數(shù)為%，則q=1,%=2,對于“23,左邊可能豎放1個

1x2的，也可能橫放2個1x2的，前者有a”」種，后者有a”1種，所以%-2,所以根據(jù)遞推，

覆蓋2x10的長方形一共有89種.

【答案】89

【例5】用1x3的小長方形覆蓋3x8的方格網(wǎng)，共有多少種不同的蓋法？

【考點】計數(shù)之遞推法【難度】5星【題型】解答

【解析】如果用1x3的長方形蓋3x〃的長方形，設(shè)種數(shù)為冊，則q=l,%=1，%=2,對于“24,左邊可能豎

放1個1x3的，也可能橫放3個1x3的，前者有％一?種，后者有%一3種，所以%=%」+%一3,依照這

條遞推公式列表：

3x13x23x33x43x53x63x73x8

112346913

所以用1x3的小長方形形覆蓋3x8的方格網(wǎng)，共有13種不同的蓋法.

【答案】13

【例6】有一堆火柴共12根，如果規(guī)定每次取1?3根，那么取完這堆火柴共有多少種不同取法？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種

數(shù)等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：

1根2根3根4根5根6根7根8根9根10根11根12根

124713244481149274504927

取完這堆火柴一共有927種方法.

【答案】927

【鞏固】一堆蘋果共有8個，如果規(guī)定每次取1?3個，那么取完這堆蘋果共有多少種不同取法？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以后取任意個蘋果的種

數(shù)等于取到前三個蘋果所有情況之和，以此類推，參照上題列表如下：

1個2個3個4個5個6個7個8個

124713244481

取完這堆蘋果一共有81種方法.

【答案】81

【例7】有10枚棋子，每次拿出2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】本題可以采用遞推法，也可以進行分類討論，當(dāng)然也可以直接進行枚舉.

（法1）遞推法.假設(shè)有八枚棋子，每次拿出2枚或3枚，將〃枚棋子全部拿完的拿法總數(shù)為％種.

則“2=1，%=1，44=1.

由于每次拿出2枚或3枚，所以4"=%_3+%_2（"25）。

白斤,6/5=42+”3=2；46=+"4=2：dZy—44+=3；“8—+Cl^=4；6j+Clj=5；

“io=%+的=7?

即當(dāng)有10枚棋子時，共有7種不同的拿法.

（法2）分類討論.

由于棋子總數(shù)為10枚，是個偶數(shù)，而每次拿2枚或3枚，所以其中拿3枚的次數(shù)也應(yīng)該是偶數(shù).由

于拿3枚的次數(shù)不超過3次，所以只能為0次或2次.

若為。次，則相當(dāng)于2枚拿了5次，此時有1種拿法；

若為2次，則2枚也拿了2次，共拿了4次，所以此時有C：=6種拿法.

根據(jù)加法原理，共有1+6=7種不同的拿法.

【答案】7

【例8】如下圖，一只蜜蜂從4處出發(fā)，回到家里8處，每次只能從一個蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆

行，共有多少種回家的方法？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】蜜蜂“每次只能從一個蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆行”這意味著它只能從小號碼的蜂房爬近相

鄰大號碼的蜂房.明確了行走路徑的方向，就可以運用標(biāo)數(shù)法進行計算.如右圖所示，小蜜蜂從A

出發(fā)到B處共有89種不同的回家方法.

【答案】89

【鞏固】小蜜蜂通過蜂巢房間，規(guī)定只能由小號房間進入大號房間問小蜜蜂由A房間到達B房間有多少種

方法？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】斐波那契數(shù)列第八項.21種.

【答案】21

【例9】如下圖，一只蜜蜂從A處出發(fā)，回到家里8處，每次只能從一個蜂房爬向右側(cè)鄰近的蜂房而不準(zhǔn)逆

行，共有多少種回家的方法？

【解析】按照蜜蜂只能從小號碼的蜂房爬近相鄰大號碼的蜂房的原則，運用標(biāo)號法進行計算,如右圖所示,

小蜜蜂從A出發(fā)到B處共有296種不同的回家方法.

【答案】296

【例10】對一個自然數(shù)作如下操作：如果是偶數(shù)則除以2,如果是奇數(shù)則加I,如此進行直到得數(shù)為1

操作停止.問經(jīng)過9次操作變?yōu)?的數(shù)有多少個？

【考點】計數(shù)之遞推法【難度】4星【題型】解答

【解析】可以先嘗試一下，倒推得出下面的圖：

10

13

14

28

1530

----------31

32

64

其中經(jīng)1次操作變?yōu)?的1個，即2,

經(jīng)2次操作變?yōu)镮的1個，即4,

經(jīng)3次操作變?yōu)?的2個，是一奇一偶，

以后發(fā)現(xiàn)，每個偶數(shù)可以變成兩個數(shù)，分別是一奇一偶，每個奇數(shù)變?yōu)橐粋€偶數(shù)，于是，經(jīng)1、2,...

次操作變?yōu)?的數(shù)的個數(shù)依次為：1,1,2,3,5,8,...

這一串?dāng)?shù)中有個特點：自第三個開始，每一個等于前兩個的和，即即經(jīng)過9次操作變?yōu)?的數(shù)有34

個.

為什么上面的規(guī)律是正確的呢？

道理也很簡單.設(shè)經(jīng)過〃次操作變?yōu)?的數(shù)的個數(shù)為冊，則q=1,a2=l,%=2,…

從上面的圖看出，%+］比%大.

一方面，每個經(jīng)過〃次操作變?yōu)?的數(shù)，乘以2,就得出一個偶數(shù)，經(jīng)過〃+1次操作變?yōu)?;反過來，

每個經(jīng)過〃+1次操作變?yōu)?的偶數(shù)，除以2,就得出一個經(jīng)過w次操作變?yōu)?的數(shù).所以經(jīng)過〃次操

作變?yōu)?的數(shù)與經(jīng)過〃+1%,因此后者也是a“個.

另一方面，每個經(jīng)過〃次操作變?yōu)?的偶數(shù)，減去1,就得出一個奇數(shù)，它經(jīng)過〃+1”+1次操作變

為1的奇數(shù)，加上1,就得出一個偶數(shù)，它經(jīng)過N次操作變?yōu)?.所以經(jīng)過〃次操作變?yōu)?的偶數(shù)經(jīng)

過〃+1次操作變?yōu)?的奇數(shù)恰好一樣多.

而由上面所說，前者的個數(shù)就是即_|，因此后者也是勺_1.

經(jīng)過〃+1次操作變?yōu)?的數(shù)，分為偶數(shù)、奇數(shù)兩類，所以%+]=%+%_],即上面所說的規(guī)律的確

成立.

【答案】34

【例11】有20個石子，一個人分若干次取，每次可以取1個，2個或3個，但是每次取完之后不能留下

質(zhì)數(shù)個，有多少種方法取完石子？（石子之間不作區(qū)分，只考慮石子個數(shù)）

【考點】計數(shù)之遞推法【難度】5星【題型】解答

【鞏固】有20個相同的棋子，一個人分若干次取，每次可取1個，2個，3個或4個，但要求每次取之后留

下的棋子數(shù)不是3或4的倍數(shù)，有種不同的方法取完這堆棋子.

【考點】計數(shù)之遞推法【難度】5星【題型】填空

【解析】把20、0和20以內(nèi)不是3或4的倍數(shù)的數(shù)寫成一串，用遞推法把所有的方法數(shù)寫出來：

2019171413111075210

112246121818183654

【答案】54

【例12】4個人進行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作

為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方法？

【考點】計數(shù)之遞推法【難度】5星【題型】解答

【解析】設(shè)第N次傳球后，球又回到甲手中的傳球方法有冊種.可以想象前〃-1次傳球，如果每一次傳球都

任選其他三人中的一人進行傳球，即每次傳球都有3種可能，由乘法原理，共有Jx3x3“：x3=3"T（種）

傳球方法.這些傳球方法并不是都符合要求的，它們可以分為兩類，一類是第次恰好傳到甲手

中，這有冊_1種傳法，它們不符合要求，因為這樣第〃次無法再把球傳給甲；另一類是第n-1次傳

球，球不在甲手中，第"次持球人再將球傳給甲，有?！胺N傳法.根據(jù)加法原理，有

+?！?3x3x…x3=3"T.

—（n-D個3-

由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方法是不存在的，所以q=0.

利用遞推關(guān)系可以得至4:a2=3-0=3,%=3x3-3=6,a4=3x3x3-6=21,

a5=3x3x3x3-21=60.

這說明經(jīng)過5次傳球后，球仍回到甲手中的傳球方法有60種.

本題也可以列表求解.

由于第〃次傳球后，球不在甲手中的傳球方法，第〃+1次傳球后球就可能回到甲手中，所以只需求

出第四次傳球后，球不在甲手中的傳法共有多少種.

第n次傳球傳球的方法俅在甲手中的傳球方法球不在甲手中的傳球方法

1303

2936

327621

4812160

524360183

從表中可以看出經(jīng)過五次傳球后，球仍回到甲手中的傳球方法共有60種.

【答案】60

【鞏固】五個人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經(jīng)過4次傳球后，球仍回到甲手中.問：共

有多少種傳球方式？

【考點】計數(shù)之遞推法【難度】5星【題型】解答

【解析】遞推法.設(shè)第〃次傳球后球傳到甲的手中的方法有％種.由于每次傳球有4種選擇，傳"次有4"次

可能.其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有種，球不在甲的手中的,

下一次傳球都可以將球傳到甲的手中，故有a?+l種.所以/+an+i=4".

23

由于q=0,所以。2=〃-4=4,a3=4-a2=12,a4=4-?3=52.即經(jīng)過4次傳球后，球仍回

到甲手中的傳球方法有52種.

【答案】52

【例13】設(shè)A、E為正八邊形ABC0EFG”的相對頂點，頂點A處有一只青蛙，除頂點E外青蛙可以從

正八邊形的任一頂點跳到其相鄰兩個頂點中任意一個，落到頂點E時青蛙就停止跳動，則青蛙從頂

點A出發(fā)恰好跳10次后落到E的方法總數(shù)為種.

【考點】計數(shù)之遞推法【難度】5星【題型】填空

【關(guān)鍵詞】清華附中

【解析】可以使用遞推法.

回到A的匕至UB或“跳至UC或G跳到D或F停在E

1步

1

2步

21

3步

31

4步

642

5步

104

6步

20148

7步

3414

8步

684828

9步

11648

附

其

,第一列的每一個數(shù)都等于它的上一行的第二列的數(shù)的2倍，第二列的每一個數(shù)都等于它的上

一行的第一列和第三列的兩個數(shù)的和，第三列的每一個數(shù)都等于它的上一行的第二列和第四列的兩

個數(shù)的和，第四列的每一個數(shù)都等于它的上一行的第三列的數(shù)，第五列的每一個數(shù)都等于都等于它

的上一行的第四列的數(shù)的2倍.這一規(guī)律很容易根據(jù)青蛙的跳動規(guī)則分析得來.

所以，青蛙第10步跳到E有48x2=96種方法.

【答案】96

【鞏固】在正五邊形45cDE上，一只青蛙從A點開始跳動，它每次可以隨意跳到相鄰兩個頂點中的一個上,

一旦跳到D點上就停止跳動.青蛙在6次之內(nèi)（含6次）跳到D點有種不同跳法.

【考點】計數(shù)之遞推法【難度】5星【題型】填空

A

BE

D

【解析】采用遞推的方法.列表如下：

跳到A跳到B跳到C停在DS先至E

1步11

2步211

3步312

4步532

5步835

6步1385

其中，根據(jù)規(guī)則，每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到。點上就停止跳動.所以,

每一步跳到A的跳法數(shù)等于上一步跳到8和E的跳法數(shù)之和，每一步跳到3的跳法數(shù)等于上一步跳

到A和C的跳法數(shù)之和，每一步跳到C的跳法數(shù)等于上一步跳到8的跳法數(shù)，每一步跳到E的跳法

數(shù)等于上一步跳到A的跳法數(shù)，每一步跳到。的跳法數(shù)等于上一步跳到C或跳到E的跳法數(shù).

觀察可知，上面的遞推結(jié)果與前面的枚舉也相吻合，所以青蛙在6次之內(nèi)（含6次）跳到。點共有

1+1+2+3+5=12種不同的跳?法.

【答案】12

【例14】有6個木箱，編號為1,2,3.............6,每個箱子有一把鑰匙，6把鑰匙各不相同，每個箱子

放進一把鑰匙鎖好.先挖開1,2號箱子，可以取出鑰匙去開箱子上的鎖，如果最終能把6把鎖都打

開，則說這是一種放鑰匙的“好”的方法，那么“好”的方法共有種.

【考點】計數(shù)之遞推法【難度】5星【題型】填空

【關(guān)鍵詞】迎春杯，中年級組，決賽

【解析】（法1）分類討論.如果1,2號箱中恰好放的就是1,2號箱的鑰匙，顯然不是“好'’的方法，所以“好”

的方法有兩種情況：

（1）1,2號箱的鑰匙恰有1把在1,2號箱中，另一箱裝的是3?6箱的鑰匙.

（2）1,2號箱的鑰匙都不在1,2號箱中.

對于⑴，從1,2號箱的鑰匙中選1把，從3?6號箱的鑰匙中選1把，共有2x4=8（種）選法，每一

種選法放入1,2號箱各有2種放法，共有8x2=16（種）放法.

不妨設(shè)1,3號箱的鑰匙放入了1,2號箱，此時3號箱不能裝2號箱的鑰匙，有3種選法，依次類

推，可知此時不同的放法有3x2xl=6（種）.

所以，第⑴種情況有“好”的方法16x6=96（種）.

對于⑵，從3?6號箱的鑰匙中選2把放入1,2號箱，有4x3=12（種）放法.不妨設(shè)3,4號箱的鑰

匙放入了1,2號箱.

此時1,2號箱的鑰匙不可能都放在3,4號箱中，也就是說3,4號箱中至少有1把5,6號箱的鑰

匙.

如果3,4號箱中有2把5,6號箱的鑰匙，也就是說3,4號箱中放的恰好是5,6號箱的鑰匙，那

么1,2號箱的鑰匙放在5,6號箱中，有2x2=4種放法；

如果3,4號箱中有1把5,6號箱的鑰匙，比如3,4號箱中放的是5,1號箱的鑰匙，則只能是5

號箱放6號箱的鑰匙，6號箱放2號箱的鑰匙，有2x1=2種放法；

同理，3,4號箱放5,2號箱或6,1號箱或6,2號箱的鑰匙，也各有2種放法.

所以，第⑵種情況有“好”的放法12x（4+2+2+2+2）=144（種）.

所以“好”的方法共有96+144=240（種）.

（法2）遞推法.設(shè)第1,2,3,…，6號箱子中所放的鑰匙號碼依次為勺，k2,玲，…，當(dāng)箱子

數(shù)為〃（〃22）時，好的放法的總數(shù)為%.

當(dāng)〃=2時，顯然。2=2（勺=1,￡>=2或年=2,k2=1）.

當(dāng)〃=3時，顯然％3*3,否則第3個箱子打不開，從而占=3或占=3,如果仁=3,則把1號箱子

和3號箱子看作一個整體，這樣還是鎖