小学奥数训练专题计数之递推法学生版推荐

1、43-2【考点】计数之递推法 【解析】教学目标前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、 树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有 归纳法、整体法、对应法、递推法.对这些计数方法与技巧要做到灵活运用.归例题精讲对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法.如果一个【例1】每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来.人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔

2、子？【难度】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

3、 对兔子.【答案】144休息”时间供自身生长，而后才能萌发新枝. 一棵 第二年新枝 休息”老枝依旧萌发新枝； 此后，老枝与 休息”过一 鲁德维格定律”那么十年后树木生长的过程中，新生的枝条往往需要一段 树苗在一年后长出一条新枝，年的枝同时萌发，当年生的新枝则依次休息”.这在生物学上称为 这棵树上有多少条树枝？【考点】计数之递推法【难度】3星【例2】【题型】解答【解析】一株树木各个年份的枝桠数,构成斐波那契数列：1, 2,3, 5, 8，13, 21，34, 55,【答案】89,所以十年后树上有8989条树枝.【例3】一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法

4、？【考点】计数之递推法【难度】4星【题型】解答牛 Ai rr【解析】登1级2级 3级 4级1种方法 2种 3种 5种 我们观察每级的种数，发现这么一个规律：从第三个数开始， 可以知道了第10级的种数是89.其实这也是加法的运用： 么登了 1级的位置是在 A1, 2级在A2A10级就在A10. 这里要强调一点，那么A2到A3既然是一步到了，那么是一种选择了同时我们假设到n级的选择数就是 AnA0 - A1 A3 ,那么就可以分成两步.有A1 X1种,A0 - A2 - A3, 同样道理 有A2 .类类相加原理：【答案】8910级?每个数是前面两个数的和；依此规律我们就假如我们把这个人开始登楼梯的

5、位置看做Ao,那到A3的前一步有两个位置；分别是A2和A1 .在A2、A3之间就是一种选择了；同理 A1到A3也 .那么从Ao到A3就可以分成两类了：第一类： 也就是A1种；（A1 - A3是一种选择）第二类：A3 = A1 + A2，依次类推 An = An-1 + An-2.12【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法?【考点】计数之递推法【难度】4星【题型】解答【解析】登1级1种方法我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律 我们就可以知道了第 10级的种数是28.【答案】28【例4】1 X2

6、的小长方形（横的竖的都行）覆盖2 X10的方格网，共有多少种不同的盖法. 【考点】计数之递推法【解析】【答案】【难度】4星 【题型】解答如果用1X2的长方形盖2xn的长方形，设种数为an,则a1 , a2 ,对于n 3,左边可能竖放 1个1X2的，也可能横放2个1X2的，前者有an-1种，后者有an-2种，所以a. =an-1+an-2 ,所以根 据递推，覆盖2X10的长方形一共有 89种.89【例5】【考点】计数之递推法【解析】用1X3的小长方形覆盖3咒8的方格网，共有多少种不同的盖法？【难度】5星【题型】解答如果用1X3的长方形盖3Xn的长方形，设种数为 an,则a, =1, a1,a2,

7、对于n 4 ,左边可 能竖放1个1X3的，也可能横放3个1X3的，前者有an-1种，后者有an-3种，所以a. =an-1 ”厲 依照这条递推公式列表：3咒13X23咒33X43咒53咒63X73咒8112346913所以用1X3的小长方形形覆盖 3咒8的方格网，共有13种不同的盖法.13【答案】有一堆火柴共12根，如果规定每次取 13根，那么取完这堆火柴共有多少种不同取法？【考点】计数之递推法【难度】4星【题型】解答【解析】取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的 种数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下：【例6】1根2根3根

8、4根5根6根7根8根9根10根11根12根124713244481149274504927取完这堆火柴一共有 927种方法.【答案】927【巩固】一堆苹果共有8个，如果规定每次取13个，那么取完这堆苹果共有多少种不同取法？【考点】计数之递推法【解析】【难度】4星【题型】解答取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的 种数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下：1个2个3个4个5个6个7个8个124713244481取完这堆苹果一共有 81种方法.81【答案】有10枚棋子，每次拿出 2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同

9、的拿法？【考点】计数之递推法【难度】4星 【题型】解答【解析】本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举.（法1）递推法.假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为an种.则 a2 =1 , a3 =1 , a4 =1.由于每次拿出2枚或3枚，所以an =an+an/（ n 5）.所以，a5 =a2 +33 =2 ； a =a3 +a4 =2 ； a = a4 +a5 =3 ； a = a5 +a6 =4 ； a9 =a6 + a7 =5 ； a1 =a7 + ag = 7 . 即当有10枚棋子时，共有7种不同的拿法.（法2）分类讨论.由于棋子总数为

10、10枚，是个偶数，而每次拿 3枚的次数不超过3次，所以只能为0次或 若为0次，则相当于2枚拿了 5次，此时有【例7】2枚或3枚, 2次.1种拿法；所以其中拿3枚的次数也应该是偶数.由于拿若为2次，则2枚也拿了 2次，共拿了 4次，所以此时有 根据加法原理，共有1+6 =7种不同的拿法.【答案】7C： =6种拿法.【例8】如下图，一只蜜蜂从 A处出发, 准逆行，共有多少种回家的方法？【考点】计数之递推法【难度】4星回到家里 B处,每次只能从一个蜂房爬向右侧邻近的蜂房而不【题型】【解析】蜜蜂每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房.明确了行走

11、路径的方向，就可以运用标数法进行计算.如右图所示，小蜜 蜂从A出发到B处共有89种不同的回家方法.【答案】89A房间到达B房间有多少【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由 种方法？【题型】解答【考点】计数之递推法【难度】4星【解析】斐波那契数列第八项.21种.【答案】21回到家里 B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不【例9】如下图，一只蜜蜂从 A处出发, 准逆行，共有多少种回家的方法？【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则, 小蜜蜂从A出发到B处共有296种不同的回家方法.【答案】296运用标号法进行计算.如右图所示,【例10】对一

12、个自然数作如下操作：如果是偶数则除以2，如果是奇数则加 1,如此进行直到得数为1操作停止.问经过 9次操作变为1的数有多少个？【考点】计数之递推法【难度】4星【题型】解答【解析】 可以先尝试一下，倒推得出下面的图：41410112413283031641、2、次9次操作变为1的数有34个.其中经1次操作变为1的1个，即2, 经2次操作变为1的1个，即4, 经3次操作变为1的2个，是一奇一偶， 以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经 操作变为1的数的个数依次为：1, 1, 2, 3, 5, 8, 这一串数中有个特点：自第三个开始，每一个等于前两个的和，即

13、即经过 为什么上面的规律是正确的呢？ 道理也很简单.设经过n次操作变为1的数的个数为an,则ai =1, a1, a2, - 从上面的图看出， ah比an大.一方面，每个经过n次操作变为1的数，乘以2,就得出一个偶数，经过n+1次操作变为1;反过来，每个经过n+1次操作变为1的偶数，除以2,就得出一个经过n次操作变为1的数.所以经过n次操作变为1的数与经过n+1次操作变为1的偶数恰好一样多.前者的个数是an,因此后者也是an个.另一方面，每个经过 n次操作变为1的偶数，减去1,就得出一个奇数，它经过 n+1次操作变为1，反过 来每个经过n+1次操作变为1的奇数，加上1,就得出一个偶数，它经过

14、n次操作变为1.所以经过n次 操作变为1的偶数经过n十1次操作变为1的奇数恰好一样多.而由上面所说，前者的个数就是an4,因此后者也是an斗.经过n+1次操作变为1的数，分为偶数、奇数两类，所以an* =an +anj，即上面所说的规律的确成立【答案】34【例11】有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【考点】计数之递推法【难度】5星【题型】解答只不过每次都是0,然后再进行【解析】如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，前面3个数相加.现在剩下的不能是质

15、数个，可以看作是质数个的取法总数都是 递推.剰下此1 石子数2019iS17161514131211109S7543210取法总 數101012305051015025025002525【答案】25【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是 3或4的倍数，有 种不同的方法取完这堆棋子 .【考点】计数之递推法【难度】5星【题型】填空【解析】把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：2019171413111075210112246121313133554【答案】54【例12】4个人进行篮球训

16、练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【考点】计数之递推法【难度】5星【题型】解答【解析】设第n次传球后，球又回到甲手中的传球方法有為种.可以想象前n-1次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有 3X3X3严=归（种）传球方法.这些传球方法并不是都符合要求的，它们可以分为两类，一类（n）个3是第n-1次恰好传到甲手中，这有 an_L种传法，它们不符合要求，因为这样第 n次无法再把球传 给甲；另一类是第 n-1次传球，球不在甲手中，第 n次持球人再将球

17、传给甲，有 an种传法.根 据加法原理，有 an 4 +an =3x3%*3=3 .（n J）个 3由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以印=0 .禾 U用递推关系可以得至 y：a2=3-0=3 , a3 =3x33=6 , a4 =3x3x36 =21 , a5 =3 3 3x3-21 = 60 .这说明经过5次传球后，球仍回到甲手中的传球方法有60种.本题也可以列表求解.由于第n次传球后，球不在甲手中的传球方法，第n+1次传球后球就可能回到甲手中，所以只需求出第四从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有【答案】60次传球后，球不在甲手中的传法共

18、有多少种.第n次传球蛭在甲手申的传蛭为进球不在申手申的传球方214S121(50534313360种.【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过 共有多少种传球方式？【考点】计数之递推法【难度】5星【解析】递推法.次可能.手中的，4次传球后，球仍回到甲手中.问:【题型】解答设第n次传球后球传到甲的手中的方法有其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有 下一次传球都可以将球传到甲的手中，故有由于 a =0，所以 a = 4 a =4 , a = 4 a? =12 , a = 4中的传球方法有52种.【答案】52an种.由于每次传球有4种

19、选择，传n次有4n an种，球不在甲的an卡种所以 + anH1 =4.-a3=52 即经过4次传球后，球仍回到甲手顶点A处有一只青蛙，除顶点E外青蛙可以 从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点 蛙从顶点A出发恰好跳10次后落到E的方法总数为种.【例13】设A、E为正八边形 ABCDEFGH的相对顶点,E时青蛙就停止跳动，则青【考点】计数之递推法【难度】5星【题型】填空【关键词】清华附中【解析】可以使用递推法.回到A跳到B或H跳到C或G跳到D或F停在1步12步213步314步6425步1046步201487步34148步6848289步11648第一列的每一个数都等于它的上

20、一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的 第其中，第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍.这一规律很容易根据青蛙的跳动规则分析得来.所以，青蛙第10步跳到E有48X2 =96种方法.【答案】96【巩固】在正五边形 ABCDE上，一只青蛙从 A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个（含6次）跳到D点有种不同跳法.上，一旦跳到 D点上就停止跳动. 【考点】计数之递推法【难度】青蛙在【题型】6次之内填空E【解析】采用递推

21、的方法.列表如下: 跳到A1步2步3步4步5步6步其中,跳到B1跳到停在D跳到E11123513根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动.所以，每步跳到A的跳法数等于上一步跳到 B和E的跳法数之和，每一步跳到 B的跳法数等于上一步跳到 A和C 的跳法数之和，每一步跳到C的跳法数等于上一步跳到 B的跳法数，每一步跳到E的跳法数等于上一步跳 到A的跳法数，每一步跳到 D的跳法数等于上一步跳到 C或跳到E的跳法数.观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内（含6次）跳到D点共有1 +1 +2 +3+5 =12种不同的跳法.【答案】12【例14】

22、子放进一把钥匙锁好先挖开 锁都打开，则说这是一种放钥匙的【考点】计数之递推法【难度】5星【关键词】迎春杯，中年级组，决赛每个箱6把有6个木箱，编号为1 , 2, 3,6,每个箱子有一把钥匙，6把钥匙各不相同,1, 2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把 好”的方法，那么好”的方法共有种.【题型】填空所以好”【解析】（法1）分类讨论.如果1 ,2号箱中恰好放的就是 1,2号箱的钥匙，显然不是 好”的方法， 的方法有两种情况：1, 2号箱的钥匙恰有1把在1, 2号箱中，另一箱装的是 36箱的钥匙. 1, 2号箱的钥匙都不在 1, 2号箱中.对于，从1, 2号箱的钥匙中选1把，从36号箱

23、的钥匙中选1把，共有2x4 =8（种）选法，每一种选 法放入1, 2号箱各有2种放法，共有8x2 =16（种）放法.不妨设1, 3号箱的钥匙放入了 1, 2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可 知此时不同的放法有 3x2x1 =6（种）.所以，第种情况有 好”的方法16x6=96（种）.对于，从36号箱的钥匙中选2把放入1, 2号箱，有4x3=12（种）放法.不妨设3, 4号箱的钥匙放入 了 1, 2号箱.此时1 , 2号箱的钥匙不可能都放在 3, 4号箱中，也就是说 3, 4号箱中至少有1把5, 6号箱的钥匙. 如果3, 4号箱中有2把5, 6号箱的钥匙，也就是说 3

24、, 4号箱中放的恰好是 5, 6号箱的钥匙，那么1, 2号箱的钥匙放在 5, 6号箱中，有2x2=4种放法；6号箱放2号箱的钥匙，有2咒1=2种放法；3, 4号箱放5, 2号箱或6, 1号箱或6, 2号箱的钥匙，也各有 2种放法. 第 种情况有 好”的放法12x（4+2 +2+2+ 2）=144（种）.好”的方法共有96+144 =240（种）.如果3, 4号箱中有1把5, 6号箱的钥匙，比如3, 4号箱中放的是5, 1号箱的钥匙，则只能是 5号箱放 6号箱的钥匙，同理， 所以， 所以（法2）递推法.设第1,2, 3,，6号箱子中所放的钥匙号码依次为k1 , k2, k3，k6 .当箱子数为n

25、（n2）k2 =2 或 kt = 2 , k =1）.3个箱子打不开，从而 k1 =3或k2 =3，如果k1 =3，则把1号箱子和3号1, 2两号钥匙，撬开1, 2两号箱子，那么方法有 a2种；当k2=3也是 a3 = 2a2 = 4 .时，好的放法的总数为 a 当 n =2 时，显然 a2 =2（k1 =1 , 当n =3时，显然ks H3，否则第 箱子看作一个整体，这样还是锁着、knj中有一个为n,不论其中 n号箱子1 , 2两号箱子，所以每种如此.于是n =2时的每一种情况对应 k, =3或k2 =3时的一种情况，这样就有 当n 4时，也一定有kn Hn，否则第n个箱子打不开，从而 匕、k?、 哪一个是n,由于必须