小学奥数教程-计数之递推法 教师版全国通用（含答案）

目混

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树

形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳

法、整体法、对应法、递推法.对这些计数方法与技巧要做到灵活运用.

对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可

以利用前面的数求出后面未知的数，这种方法称为递推法.

【例1】每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来.如果一个人

在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？

【考点】计数之递推法【难度】3星【题型】解答

【解析】第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小

兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，

共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子

数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为

上月的兔子数与上上月的兔子数相加.依次类推可以列出下表：

经过月数：—1—2—3—4—5—6—7—8—9—10—11—12

兔子对数：-一1一1-2-3-5--8-13-21-34-55-89—144,所以十二月份的时候总共有144对兔子.

【答案】144

【例2】树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝.一棵树

苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的

枝同时萌发，当年生的新枝则依次“休息”.这在生物学上称为“鲁德维格定律”.那么十年后这棵树

上有多少条树枝？

【考点】计数之递推法【难度】3星【题型】解答

【解析】一株树木各个年份的枝才亚数，构成斐波那契数列：1,2,3,5,8,13,21,34,55,89,……所以

十年后树上有89条树枝.

【答案】89

【例3】一楼梯共1()级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法?

【考点】计数之递推法【难度】4星【题型】解答

Aio-

【解析】登1级2级

1种方法2种

我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律

我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位

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

别是上和Ai.在这里要强调一点，那么42到小既然是一步到了，那么A2、4之间就是一种选

择了；同理4到A3也是一种选择了.同时我们假设到〃级的选择数就是A”.那么从A）至4A3就

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

（41——A3是一种选择）第二类：4）--A2——43,同样道理有A2.类类相加原理：43=A1+

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

【答案】89

【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法?

【考点】计数之递推法【难度】4星【题型】解答

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

我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依

此规律我们就可以知道了第10级的种数是28.

【答案】28

【例4】1x2的小长方形（横的竖的都行）覆盖2x10的方格网，共有多少种不同的盖法.

【考点】计数之递推法【难度】4星【题型】解答

【解析】如果用1x2的长方形盖2x〃的长方形，设种数为%，则q=1,%=2,对于“23,左边可能竖放1个

1x2的，也可能横放2个1x2的，前者有a”」种，后者有a”1种，所以%-2,所以根据递推，

覆盖2x10的长方形一共有89种.

【答案】89

【例5】用1x3的小长方形覆盖3x8的方格网，共有多少种不同的盖法？

【考点】计数之递推法【难度】5星【题型】解答

【解析】如果用1x3的长方形盖3x〃的长方形，设种数为册，则q=l,%=1，%=2,对于“24,左边可能竖

放1个1x3的，也可能横放3个1x3的，前者有％一।种，后者有%一3种，所以%=%」+%一3,依照这

条递推公式列表：

3x13x23x33x43x53x63x73x8

112346913

所以用1x3的小长方形形覆盖3x8的方格网，共有13种不同的盖法.

【答案】13

【例6】有一堆火柴共12根，如果规定每次取1〜3根，那么取完这堆火柴共有多少种不同取法？

【考点】计数之递推法【难度】4星【题型】解答

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

数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下：

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

124713244481149274504927

取完这堆火柴一共有927种方法.

【答案】927

【巩固】一堆苹果共有8个，如果规定每次取1〜3个，那么取完这堆苹果共有多少种不同取法？

【考点】计数之递推法【难度】4星【题型】解答

【解析】取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种

数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下：

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

124713244481

取完这堆苹果一共有81种方法.

【答案】81

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

【考点】计数之递推法【难度】4星【题型】解答

【解析】本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举.

（法1）递推法.假设有八枚棋子，每次拿出2枚或3枚，将〃枚棋子全部拿完的拿法总数为％种.

则“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・

即当有10枚棋子时，共有7种不同的拿法.

（法2）分类讨论.

由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数.由

于拿3枚的次数不超过3次，所以只能为0次或2次.

若为。次，则相当于2枚拿了5次，此时有1种拿法；

若为2次，则2枚也拿了2次，共拿了4次，所以此时有C：=6种拿法.

根据加法原理，共有1+6=7种不同的拿法.

【答案】7

【例8】如下图，一只蜜蜂从4处出发，回到家里8处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆

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

【考点】计数之递推法【难度】4星【题型】解答

【解析】蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相

邻大号码的蜂房.明确了行走路径的方向，就可以运用标数法进行计算.如右图所示，小蜜蜂从A

出发到B处共有89种不同的回家方法.

【答案】89

【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A房间到达B房间有多少种

方法？

【考点】计数之递推法【难度】4星【题型】解答

【解析】斐波那契数列第八项.21种.

【答案】21

【例9】如下图，一只蜜蜂从A处出发，回到家里8处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆

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

【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算,如右图所示,

小蜜蜂从A出发到B处共有296种不同的回家方法.

【答案】296

【例10】对一个自然数作如下操作：如果是偶数则除以2,如果是奇数则加I,如此进行直到得数为1

操作停止.问经过9次操作变为1的数有多少个？

【考点】计数之递推法【难度】4星【题型】解答

【解析】可以先尝试一下，倒推得出下面的图：

10

13

14

28

1530

----------31

32

64

其中经1次操作变为1的1个，即2,

经2次操作变为I的1个，即4,

经3次操作变为1的2个，是一奇一偶，

以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2,...

次操作变为1的数的个数依次为：1,1,2,3,5,8,...

这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34

个.

为什么上面的规律是正确的呢？

道理也很简单.设经过〃次操作变为1的数的个数为册，则q=1,a2=l,%=2,…

从上面的图看出，%+］比%大.

一方面，每个经过〃次操作变为1的数，乘以2,就得出一个偶数，经过〃+1次操作变为1;反过来，

每个经过〃+1次操作变为1的偶数，除以2,就得出一个经过w次操作变为1的数.所以经过〃次操

作变为1的数与经过〃+1%,因此后者也是a“个.

另一方面，每个经过〃次操作变为1的偶数，减去1,就得出一个奇数，它经过〃+1”+1次操作变

为1的奇数，加上1,就得出一个偶数，它经过N次操作变为1.所以经过〃次操作变为1的偶数经

过〃+1次操作变为1的奇数恰好一样多.

而由上面所说，前者的个数就是即_|，因此后者也是勺_1.

经过〃+1次操作变为1的数，分为偶数、奇数两类，所以%+]=%+%_],即上面所说的规律的确

成立.

【答案】34

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

质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）

【考点】计数之递推法【难度】5星【题型】解答

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

下的棋子数不是3或4的倍数，有种不同的方法取完这堆棋子.

【考点】计数之递推法【难度】5星【题型】填空

【解析】把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：

2019171413111075210

112246121818183654

【答案】54

【例12】4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作

为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？

【考点】计数之递推法【难度】5星【题型】解答

【解析】设第N次传球后，球又回到甲手中的传球方法有册种.可以想象前〃-1次传球，如果每一次传球都

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

传球方法.这些传球方法并不是都符合要求的，它们可以分为两类，一类是第次恰好传到甲手

中，这有册_1种传法，它们不符合要求，因为这样第〃次无法再把球传给甲；另一类是第n-1次传

球，球不在甲手中，第"次持球人再将球传给甲，有。“种传法.根据加法原理，有

+。“=3x3x…x3=3"T.

—（n-D个3-

由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以q=0.

利用递推关系可以得至4:a2=3-0=3,%=3x3-3=6,a4=3x3x3-6=21,

a5=3x3x3x3-21=60.

这说明经过5次传球后，球仍回到甲手中的传球方法有60种.

本题也可以列表求解.

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

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

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

1303

2936

327621

4812160

524360183

从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种.

【答案】60

【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中.问：共

有多少种传球方式？

【考点】计数之递推法【难度】5星【题型】解答

【解析】递推法.设第〃次传球后球传到甲的手中的方法有％种.由于每次传球有4种选择，传"次有4"次

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

下一次传球都可以将球传到甲的手中，故有a„+l种.所以/+an+i=4".

23

由于q=0,所以。2=〃-4=4,a3=4-a2=12,a4=4-«3=52.即经过4次传球后，球仍回

到甲手中的传球方法有52种.

【答案】52

【例13】设A、E为正八边形ABC0EFG”的相对顶点，顶点A处有一只青蛙，除顶点E外青蛙可以从

正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶

点A出发恰好跳10次后落到E的方法总数为种.

【考点】计数之递推法【难度】5星【题型】填空

【关键词】清华附中

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

回到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

附

其

,第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上

一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两

个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它

的上一行的第四列的数的2倍.这一规律很容易根据青蛙的跳动规则分析得来.

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

【答案】96

【巩固】在正五边形45cDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上,

一旦跳到D点上就停止跳动.青蛙在6次之内（含6次）跳到D点有种不同跳法.

【考点】计数之递推法【难度】5星【题型】填空

A

BE

D

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

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

1步11

2步211

3步312

4步532

5步835

6步1385

其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到。点上就停止跳动.所以,

每一步跳到A的跳法数等于上一步跳到8和E的跳法数之和，每一步跳到3的跳法数等于上一步跳

到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到8的跳法数，每一步跳到E的跳法

数等于上一步跳到A的跳法数，每一步跳到。的跳法数等于上一步跳到C或跳到E的跳法数.

观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内（含6次）跳到。点共有

1+1+2+3+5=12种不同的跳•法.

【答案】12

【例14】有6个木箱，编号为1,2,3.............6,每个箱子有一把钥匙，6把钥匙各不相同，每个箱子

放进一把钥匙锁好.先挖开1,2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打

开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有种.

【考点】计数之递推法【难度】5星【题型】填空

【关键词】迎春杯，中年级组，决赛

【解析】（法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（种）放法.

不妨设1,3号箱的钥匙放入了1,2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类

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

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

对于⑵，从3〜6号箱的钥匙中选2把放入1,2号箱，有4x3=12（种）放法.不妨设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）递推法.设第1,2,3,…，6号箱子中所放的钥匙号码依次为勺，k2,玲，…，当箱子

数为〃（〃22）时，好的放法的总数为%.

当〃=2时，显然。2=2（勺=1,£>=2或年=2,k2=1）.

当〃=3时，显然％3*3,否则第3个箱子打不开，从而占=3或占=3,如果仁=3,则把1号箱子

和3号箱子看作一个整体，这样还是锁