1、7-6-4.计数之递推法.题库 教师版 page 1 of 97-6-4.计数之递推法教学目标前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法对这些计数方法与技巧要做到灵活运用例题精讲对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来如果一个人在一月份买了一对小
2、兔子，那么十二月份的时候他共有多少对兔子？【考点】计数之递推法 【难度】3 星 【题型】解答【 解析解析 】 第一个月，有 1 对小兔子；第二个月，长成大兔子，所以还是 1 对；第三个月，大兔子生下一对小兔子，所以共有 2 对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有 3 对；第五个月，两对大兔子生下 2 对小兔子，共有 5 对；这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加 依次类推可以列出下表： 经过月数：-1-2-3-4-5-6-7-8-9-10-11-12兔
3、子对数：-1-1-2-3-5-8-13-21-34-55-89144，所以十二月份的时候总共有 144 对兔子【答案】 14【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”这在生物学上称为“鲁德维格定律”那么十年后这棵树上有多少条树枝？【考点】计数之递推法 【难度】3 星 【题型】解答【 解析解析 】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，所以十年后树上有 89
4、条树枝【答案】 9【例 3】 一楼梯共 10 级，规定每步只能跨上一级或两级，要登上第 10 级，共有多少种不同走法？【考点】计数之递推法 【难度】4 星 【题型】解答7-6-4.计数之递推法.题库 教师版 page 2 of 9【解析】 登 1 级 2 级 3 级 4 级 . 10 级1 种方法 2 种 3 种 5 种 . ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第 10 级的种数是 89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做 A0，那么登了 1 级的位置是在 A1，2 级在 A2. A10级就在 A10到
5、 A3的前一步有两个位置；分别是 A2 和 A1 在这里要强调一点，那么 A2 到 A3 既然是一步到了，那么 A2 、A 3之间就是一种选择了；同理 A1 到 A3 也是一种选择了同时我们假设到 n 级的选择数就是 An 那么从 A0 到A3 就可以分成两类了：第一类：A0 - A1 - A3 ，那么就可以分成两步有 A11 种，也就是A1 种；(A 1 - A3 是一种选择 )第二类：A0 - A2 - A3， 同样道理 有 A2 类类相加原理：A3 = A1 A2，依次类推 An = An-1 + An-2【答案】 89【巩固】一楼梯共 10 级，规定每步只能跨上一级或三级，要登上第 1
6、0 级，共有多少种不同走法？【考点】计数之递推法 【难度】4 星 【题型】解答【解析】 登 1 级 2 级 3 级 4 级 5 级 . 10 级1 种方法 1 种 2 种 3 种 4 种. ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第 10 级的种数是 28.【答案】 28【例 4】 12 的小长方形 (横的竖的都行)覆盖 210 的方格网，共有多少种不同的盖法【考点】计数之递推法 【难度】4 星 【题型】解答【解析】 如果用 的长方形盖 的长方形，设种数为 ,则 ， ,对于 ，左边可能竖放 12nna12a3n个 的，也可能
7、横放 2 个 的，前者有 种，后者有 种，所以 ,所以根据递1-1-n-1-2na推，覆盖 的长方形一共有 89 种2107-6-4.计数之递推法.题库 教师版 page 3 of 9【答案】 89【例 5】 用 的小长方形覆盖 的方格网，共有多少种不同的盖法？1338【考点】计数之递推法 【难度】5 星 【题型】解答【解析】 如果用 的长方形盖 的长方形，设种数为 ,则 ， , ,对于 ，左边可能nna12a34n竖放 1 个 的，也可能横放 3 个 的，前者有 种，后者有 种，所以 ,依照1-n-1-3na这条递推公式列表： 324356781 1 2 3 4 6 9 13所以用 的小长方
8、形形覆盖 的方格网，共有 13 种不同的盖法8【答案】【例 6】 有一堆火柴共 12 根，如果规定每次取 13 根，那么取完这堆火柴共有多少种不同取法？【考点】计数之递推法 【难度】4 星 【题型】解答【解析】 取 1 根火柴有 1 种方法，取 2 根火柴有 2 种方法，取 3 根火柴有 4 种取法，以后取任意根火柴的种数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如下：1 根 2 根 3 根 4 根 5 根 6 根 7 根 8 根 9 根 10 根 11根12 根1 2 4 7 13 24 44 81 149 274 504 927取完这堆火柴一共有 927 种方法【答案】 97【
9、巩固】 一堆苹果共有 8 个，如果规定每次取 13 个，那么取完这堆苹果共有多少种不同取法？【考点】计数之递推法 【难度】4 星 【题型】解答【解析】 取 1 个苹果有 1 种方法，取 2 个苹果有 2 种方法，取 3 个苹果有 4 种取法，以后取任意个苹果的种数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下：1 个 2 个 3 个 4 个 5 个 6 个 7 个 8 个1 2 4 7 13 24 44 81取完这堆苹果一共有 81 种方法【答案】 81【例 7】 有 10 枚棋子，每次拿出 2 枚或 3 枚，要想将 10 枚棋子全部拿完，共有多少种不同的拿法？【考点】计数之递推法
10、 【难度】4 星 【题型】解答【 解析解析 】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举(法 1)递推法假设有 枚棋子，每次拿出 2 枚或 3 枚，将 枚棋子全部拿完的拿法总数为 种nnna则 ， ， 21a341a由于每次拿出 2 枚或 3 枚，所以 ( )32nna5所以， ； ； ； ； ；563474a8564a9675a1078即当有 10 枚棋子时，共有 7 种不同的拿法(法 2)分类讨论由于棋子总数为 10 枚，是个偶数，而每次拿 2 枚或 3 枚，所以其中拿 3 枚的次数也应该是偶数由于拿 3 枚的次数不超过 3 次，所以只能为 0 次或 2 次若为 0
11、次，则相当于 2 枚拿了 5 次，此时有 1 种拿法；7-6-4.计数之递推法.题库 教师版 page 4 of 9若为 2 次，则 2 枚也拿了 2 次，共拿了 4 次，所以此时有 种拿法246C根据加法原理，共有 种不同的拿法167【答案】 7【例 8】 如下图，一只蜜蜂从 处出发，回到家里 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆AB行，共有多少种回家的方法？【考点】计数之递推法 【难度】4 星 【题型】解答BAA B1 3 5 7 94 6 821235813213455891【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大
12、号码的蜂房明确了行走路径的方向，就可以运用标数法进行计算如右图所示，小蜜蜂从 A出发到 B 处共有 89 种不同的回家方法【答案】 89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由 房间到达 房间有多少种AB方法？【考点】计数之递推法 【难度】4 星 【题型】解答【 解析解析 】 斐波那契数列第八项21 种86427531【答案】 1【例 9】 如下图，一只蜜蜂从 A 处出发，回到家里 B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4 星 【题型】解答BA【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂
13、房的原则，运用标号法进行计算如右图所示，小蜜蜂从 A 出发到 B 处共有 296 种不同的回家方法【答案】 296【例 10】 对一个自然数作如下操作：如果是偶数则除以 2，如果是奇数则加 1，如此进行直到得数为 1操作停止问经过 9 次操作变为 1 的数有多少个？【考点】计数之递推法 【难度】4 星 【题型】解答【 解析解析 】 可以先尝试一下，倒推得出下面的图：7-6-4.计数之递推法.题库 教师版 page 5 of 92410131112514302831643215167683421其中经 1 次操作变为 1 的 1 个，即 2，经 2 次操作变为 1 的 1 个，即 4，经 3 次
14、操作变为 1 的 2 个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、次操作变为 1 的数的个数依次为：1，1，2，3，5，8， 这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过 9 次操作变为 1 的数有34 个.为什么上面的规律是正确的呢？道理也很简单. 设经过 次操作变为 1 的数的个数为 ,则 1， 1， 2，nna2a3从上面的图看出， 比 大. 1a一方面，每个经过 次操作变为 1 的数，乘以 2，就得出一个偶数，经过 次操作变为 1；反过n来，每个经过 次操作变为 1 的偶数，除以 2，就得出一个经过 次操作
15、变为 1 的数. 所以经过次操作变为 1 的数与经过 次操作变为 1 的偶数恰好一样多.前者的个数是 ,因此后者也是nn na个.a另一方面，每个经过 次操作变为 1 的偶数，减去 1，就得出一个奇数，它经过 次操作变为1，反过来.每个经过 次操作变为 1 的奇数，加上 1，就得出一个偶数，它经过 次操作变为 1. 所以经过 次操作变为 1 的偶数经过 次操作变为 1 的奇数恰好一样多.nn而由上面所说，前者的个数就是 ,因此后者也是 .1ana经过 1 次操作变为 1 的数，分为偶数、奇数两类，所以 ，即上面所说的规律的确 11na成立.【答案】 34【例 11】 有 20 个石子，一个人分
16、若干次取，每次可以取 1 个，2 个或 3 个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【考点】计数之递推法 【难度】5 星 【题型】解答【 解析解析 】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面 3 个数相加现在剩下的不能是质数个，可以看作是质数个的取法总数都是 0，然后再进行递推7-6-4.计数之递推法.题库 教师版 page 6 of 9【答案】 25【巩固】有 20 个相同的棋子，一个人分若干次取，每次可取 1 个，2 个，3 个或 4 个，但要求每次取之后留下的棋子数不是 3 或 4 的
17、倍数，有 种不同的方法取完这堆棋子 . 【考点】计数之递推法 【难度】5 星 【题型】填空【 解析解析 】 把 20、0 和 20 以内不是 3 或 4 的倍数的数写成一串，用递推法把所有的方法数写出来：【答案】 54【例 12】 个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【考点】计数之递推法 【难度】5 星 【题型】解答【 解析解析 】 设第 次传球后，球又回到甲手中的传球方法有 种可以想象前 次传球，如果每一次传球都n na1n任选其他三人中的一人进行传球，即每次传球都有 种可能，由乘法原
18、理，共有3(种) 传球方法这些传球方法并不是都符合要求的，它们可以分为两类，一类是113nn()个第 次恰好传到甲手中，这有 种传法，它们不符合要求，因为这样第 次无法再把球传给甲；1na n另一类是第 次传球，球不在甲手中，第 次持球人再将球传给甲，有 种传法根据加法原理，a有 13na(个 )由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以 10利用递推关系可以得到： ， ， ，230a36a4362a516a这说明经过 次传球后，球仍回到甲手中的传球方法有 种0本题也可以列表求解由于第 次传球后，球不在甲手中的传球方法，第 次传球后球就可能回到甲手中，所以只需求n 1n
19、出第四次传球后，球不在甲手中的传法共有多少种从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有 种60【答案】 60【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过 次传球后，球仍回到甲手中问：共4有多少种传球方式？【考点】计数之递推法 【难度】5 星 【题型】解答【 解析解析 】 递推法设第 次传球后球传到甲的手中的方法有 种由于每次传球有 4 种选择，传 次有 次n na n4可能其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有 种，球不在甲的手中na的，下一次传球都可以将球传到甲的手中，故有 种所以 11n7-6-4.计数之递推法.题库 教师版 page 7
20、 of 9由于 ，所以 ， ， 即经过 次传球后，球仍回10a124a2341a3452a4到甲手中的传球方法有 52 种【答案】 52【例 13】 设 、 为正八边形 的相对顶点，顶点 处有一只青蛙，除顶点 外青蛙可以从AEABCDEFGHAE正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点 时青蛙就停止跳动，则青蛙从顶E点 出发恰好跳 次后落到 的方法总数为 种10【考点】计数之递推法 【难度】5 星 【题型】填空【关键词】清华附中【 解析解析 】 可以使用递推法回到 跳到 或 跳到 或 跳到 或 停在ABHCGDFE1 步 12 步 2 13 步 3 14 步 6 4 25 步
21、10 46 步 20 14 87 步 34 148 步 68 48 289 步 116 48其中，第一列的每一个数都等于它的上一行的第二列的数的 2 倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的 2 倍这一规律很容易根据青蛙的跳动规则分析得来所以，青蛙第 10 步跳到 有 种方法E4896【答案】 96【巩固】在正五边形 上，一只青蛙从 点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，ABCDA一旦跳到 点上
22、就停止跳动青蛙在 6 次之内( 含 6 次)跳到 点有 种不同跳法D【考点】计数之递推法 【难度】5 星 【题型】填空 ABCDE【 解析解析 】 采用递推的方法列表如下：跳到 跳到 跳到 停在 跳到ABE1 步 1 12 步 2 1 13 步 3 1 24 步 5 3 25 步 8 3 57-6-4.计数之递推法.题库 教师版 page 8 of 96 步 13 8 5其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到 点上就停止跳动所以，D每一步跳到 的跳法数等于上一步跳到 和 的跳法数之和，每一步跳到 的跳法数等于上一步跳ABEB到 和 的跳法数之和，每一步跳到 的跳法数等
23、于上一步跳到 的跳法数，每一步跳到 的跳法CC E数等于上一步跳到 的跳法数，每一步跳到 的跳法数等于上一步跳到 或跳到 的跳法数DC观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在 6 次之内(含 6 次) 跳到 点共有种不同的跳法12351【答案】【例 14】 有 6 个木箱，编号为 1，2，3，6，每个箱子有一把钥匙，6 把钥匙各不相同，每个箱子放进一把钥匙锁好先挖开 1，2 号箱子，可以取出钥匙去开箱子上的锁，如果最终能把 6 把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种【考点】计数之递推法 【难度】5 星 【题型】填空【关键词】迎春杯，中年级组，决赛
24、【 解析解析 】 (法 1)分类讨论如果 1，2 号箱中恰好放的就是 1，2 号箱的钥匙，显然不是“好”的方法，所以“ 好”的方法有两种情况：1，2 号箱的钥匙恰有 1 把在 1，2 号箱中，另一箱装的是 36 箱的钥匙1，2 号箱的钥匙都不在 1，2 号箱中对于，从 1，2 号箱的钥匙中选 1 把，从 36 号箱的钥匙中选 1 把，共有 (种) 选法，每248一种选法放入 1，2 号箱各有 2 种放法，共有 (种) 放法821不妨设 1，3 号箱的钥匙放入了 1，2 号箱，此时 3 号箱不能装 2 号箱的钥匙，有 3 种选法，依次类推，可知此时不同的放法有 (种)3所以，第种情况有“好” 的
25、方法 (种)69对于，从 36 号箱的钥匙中选 2 把放入 1，2 号箱，有 (种) 放法不妨设 3，4 号箱的钥41匙放入了 1，2 号箱此时 1，2 号箱的钥匙不可能都放在 3，4 号箱中，也就是说 3，4 号箱中至少有 1 把 5，6 号箱的钥匙如果 3，4 号箱中有 2 把 5，6 号箱的钥匙，也就是说 3，4 号箱中放的恰好是 5，6 号箱的钥匙，那么 1，2 号箱的钥匙放在 5，6 号箱中，有 种放法；2如果 3，4 号箱中有 1 把 5，6 号箱的钥匙，比如 3，4 号箱中放的是 5，1 号箱的钥匙，则只能是 5号箱放 6 号箱的钥匙，6 号箱放 2 号箱的钥匙，有 种放法；12
26、同理，3，4 号箱放 5，2 号箱或 6，1 号箱或 6，2 号箱的钥匙，也各有 2 种放法所以，第种情况有“好” 的放法 (种)4所以“好”的方法共有 (种)90(法 2)递推法设第 1，2，3，6 号箱子中所放的钥匙号码依次为 ， ， ， 当箱1k236k子数为 ( )时，好的放法的总数为 nna当 时，显然 ( ， 或 ， )22a1k21k2当 时，显然 ，否则第 3 个箱子打不开，从而 或 ，如果 ，则把 1 号箱子3313k21k和 3 号箱子看作一个整体，这样还是锁着 1，2 两号钥匙，撬开 1，2 两号箱子，那么方法有 种；2a当 也是如此于是 时的每一种情况对应 或 时的一种
27、情况，这样就有2kn34a7-6-4.计数之递推法.题库 教师版 page 9 of 9当 时，也一定有 ，否则第 个箱子打不开，从而 、 、 中有一个为 ，不4nnkn1k21nkn论其中哪一个是 ，由于必须要把该箱子打开才能打开 号箱子，所以可以将锁着这把钥匙的箱子n与第 号箱子看作 1 个箱子，于是还是锁着 、 、 这 把钥匙，需要撬开 1，2 两1k2号箱子，所以每种情况都有 种所以 1na1nna所以， ，即好的方法总数为 240 种654535!40a【答案】 240【巩固】有 10 个木箱，编号为 1，2，3，10，每个箱子有一把钥匙，10 把钥匙各不相同，每个箱子放进一把钥匙锁
28、好先挖开 1，2 号箱子，可以取出钥匙去开箱子上的锁，如果最终能把 10 把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种【考点】计数之递推法 【难度】5 星 【题型】填空【 解析解析 】 递推法设第 1，2，3，6 号箱子中所放的钥匙号码依次为 ， ， ， 当箱子数为1k236k( )时，好的放法的总数为 nna当 时，显然 ( ， 或 ， )2a1k21k2当 时，显然 ，否则第 3 个箱子打不开，从而 或 ，如果 ，则把 1 号箱子313k21k和 3 号箱子看作一个整体，这样还是锁着 1，2 两号钥匙，撬开 1，2 两号箱子，那么方法有 种；2a当 也是如此于是 时的每一种情况对应 或 时的一种情况，这样就有2kn34a当 时，也一定有 ，否则第 个箱子打不开，从而 、 、 中有一个为 ，不nnkn1k21nkn论其中哪一个是 ，由于必须要把该箱子打开才能打开 号箱子，所以可以将锁着这把钥匙的箱子n与第 号箱子看作 1 个箱子，于是还是锁着 、 、 这 把钥匙，需要撬开 1，2 两1k2号箱子，所以每种情况都有 种所以 1na1nna所以， ，即好的方法总数为 72576010989765439!=72560a种【答案】 7256
