小学奥数习题教案-7-6-4 计数之递推法.教师版.doc

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

2、个月能生出一对小兔子来如果一个人每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来如果一个人 在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？ 【考点】计数之递推法【难度】3 星【题型】解答 【解析】【解析】第一个月，有 1 对小兔子；第二个月，长成大兔子，所以还是 1 对；第三个月，大兔子生下一对小 兔子，所以共有 2 对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子， 共有 3 对；第五个月，两对大兔子生下 2 对小兔子，共有 5 对；这个特点的说明每月的大兔子 数为上月的

3、兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为 上月的兔子数与上上月的兔子数相加 依次类推可以列出下表： 经过月数：-1-2-3-4-5-6-7-8-9-10-11-12 兔子对数：-1-1-2-3-5-8-13-21-34-55-89144，所以十二月份的时候总共有 144 对兔子 【答案】144 【例【例 2】树木生长的过程中，新生的枝条往往需要一段树木生长的过程中，新生的枝条往往需要一段“休息休息”时间供自身生长，而后才能萌发新枝一棵树时间供自身生长，而后才能萌发新枝一棵树 苗在一年后长出一条新枝，第二年新枝苗在一年后长出一条新枝，第二年新枝“休息休息”，老

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

5、两级，要登上第 10 级，共有多少种不同走法？级，共有多少种不同走法？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】登 1 级2 级3 级4 级.10 级 1 种方法2 种3 种5 种.？ 7-6-4.计数之递推法.题库教师版page2of8 我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律 我们就可以知道了第 10 级的种数是 89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位 置看做 A0，那么登了 1 级的位置是在 A1，2 级在 A2. A10级就在 A10到 A3的前一步有两个位置；分 别是 A2和 A1在这里要强调一点，那么

6、 A2到 A3既然是一步到了，那么 A2、A3之间就是一种选 择了；同理 A1到 A3也是一种选择了同时我们假设到 n 级的选择数就是 An 那么从 A0到 A3就 可以分成两类了：第一类：A0 - A1 - A3 ，那么就可以分成两步有 A11 种，也就是 A1 种； (A1 - A3 是一种选择)第二类： A0 - A2 - A3， 同样道理 有 A2 类类相加原理： A3 = A1 A2，依次类推 An = An-1 + An-2 【答案】89 【巩固】【巩固】一楼梯共一楼梯共 10 级，规定每步只能跨上一级或三级，要登上第级，规定每步只能跨上一级或三级，要登上第 10 级，共有多少种不

7、同走法？级，共有多少种不同走法？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】登 1 级2 级3 级4 级5 级 .10 级 1 种方法1 种2 种3 种4 种.？ 我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依 此规律我们就可以知道了第 10 级的种数是 28. 【答案】28 【例【例 4】12 的小长方形的小长方形(横的竖的都行横的竖的都行)覆盖覆盖 210 的方格网，共有多少种不同的盖法的方格网，共有多少种不同的盖法 【考点】计数之递推法【难度】4 星【题型】解答 【解析】如果用1 2的长方形盖2n的长方形，设种数为 n a,则 1 1

8、a ， 2 2a ,对于3n ，左边可能竖放 1 个 1 2的，也可能横放 2 个1 2的，前者有 -1n a种，后者有 -2n a种，所以 -1-2nnn aaa,所以根据递推， 覆盖2 10的长方形一共有 89 种 【答案】89 【例【例 5】用用1 3的小长方形覆盖的小长方形覆盖3 8的方格网，共有多少种不同的盖法？的方格网，共有多少种不同的盖法？ 【考点】计数之递推法【难度】5 星【题型】解答 【解析】如果用1 3的长方形盖3n的长方形，设种数为 n a,则 1 1a ， 2 1a , 3 2a ,对于4n ，左边可能竖 放 1 个1 3的，也可能横放 3 个1 3的，前者有 -1n

9、a种，后者有 -3n a种，所以 -1-3nnn aaa,依照这 条递推公式列表： 3 1323 3343 53 6373 8 112346913 所以用1 3的小长方形形覆盖3 8的方格网，共有 13 种不同的盖法 【答案】13 【例【例 6】有一堆火柴共有一堆火柴共 12 根，如果规定每次取根，如果规定每次取 13 根，那么取完这堆火柴共有多少种不同取法？根，那么取完这堆火柴共有多少种不同取法？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】取 1 根火柴有 1 种方法，取 2 根火柴有 2 种方法，取 3 根火柴有 4 种取法，以后取任意根火柴的种 数等于取到前三根火柴所有情况

10、之和，以此类推，参照上题列表如下： 1 根2 根3 根4 根5 根6 根7 根8 根9 根10 根11 根12 根 124713244481149274504927 取完这堆火柴一共有 927 种方法 【答案】927 7-6-4.计数之递推法.题库教师版page3of8 【巩固】【巩固】 一一堆苹果共有堆苹果共有 8 个，如果规定每次取个，如果规定每次取 13 个，那么取完这堆苹果共有多少种不同取法？个，那么取完这堆苹果共有多少种不同取法？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】取 1 个苹果有 1 种方法，取 2 个苹果有 2 种方法，取 3 个苹果有 4 种取法，以后取任

11、意个苹果的种 数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如下： 1 个2 个3 个4 个5 个6 个7 个8 个 124713244481 取完这堆苹果一共有 81 种方法 【答案】81 【例【例 7】有有 10 枚棋子，每次拿出枚棋子，每次拿出 2 枚或枚或 3 枚，要想将枚，要想将 10 枚棋子全部拿完，共有多少种不同的拿法？枚棋子全部拿完，共有多少种不同的拿法？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】【解析】本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举 (法 1)递推法假设有n枚棋子，每次拿出 2 枚或 3 枚，将n枚棋子全部拿完的拿法总

12、数为 n a种 则 2 1a ， 3 1a ， 4 1a 由于每次拿出 2 枚或 3 枚，所以 32nnn aaa (5n ) 所以， 523 2aaa； 634 2aaa； 745 3aaa； 856 4aaa； 967 5aaa； 1078 7aaa 即当有 10 枚棋子时，共有 7 种不同的拿法 (法 2)分类讨论 由于棋子总数为 10 枚，是个偶数，而每次拿 2 枚或 3 枚，所以其中拿 3 枚的次数也应该是偶数由 于拿 3 枚的次数不超过 3 次，所以只能为 0 次或 2 次 若为 0 次，则相当于 2 枚拿了 5 次，此时有 1 种拿法； 若为 2 次，则 2 枚也拿了 2 次，共

13、拿了 4 次，所以此时有 2 4 6C 种拿法 根据加法原理，共有167种不同的拿法 【答案】7 【例【例 8】如下图如下图，一只蜜蜂从一只蜜蜂从A处出发处出发，回到家里回到家里B处处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆 行，共有多少种回家的方法？行，共有多少种回家的方法？ 【考点】计数之递推法【难度】4 星【题型】解答 ? B ? A ? A ? B ? 1 ? 3 ? 5 ? 7 ? 9 ? 4 ? 6 ? 8 ? 2 ? 1 ? 2 ? 3 ? 5 ? 8 ? 13 ? 21 ? 34 ? 55 ? 89 ? 1 【解析】蜜蜂“每次只

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

15、回到家里 B 处处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆 7-6-4.计数之递推法.题库教师版page4of8 行，共有多少种回家的方法？行，共有多少种回家的方法？ 【考点】计数之递推法【难度】4 星【题型】解答 ? B ? A 【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算如右图所示， 小蜜蜂从 A 出发到 B 处共有 296 种不同的回家方法 【答案】296 【例【例 10】对一个自然数作如下操作：如果是偶数则除以对一个自然数作如下操作：如果是偶数则除以 2，如果是奇数则加，如果是奇数则加 1，如此进行直

16、到得数为，如此进行直到得数为 1 操作停止问经过操作停止问经过 9 次操作变为次操作变为 1 的数有多少个？的数有多少个？ 【考点】计数之递推法【难度】4 星【题型】解答 【解析】【解析】 可以先尝试一下，倒推得出下面的图： ? 24 ? 10 ? 13 ? 11 ? 12 ? 5 ? 14 ? 30 ? 28 ? 31 ? 64 ? 32 ? 15 ? 16 ? 7 ? 6 ? 8 ? 3 ? 4 ? 2 ? 1 其中经 1 次操作变为 1 的 1 个，即 2， 经 2 次操作变为 1 的 1 个，即 4， 经 3 次操作变为 1 的 2 个，是一奇一偶， 以后发现，每个偶数可以变成两个数，

17、分别是一奇一偶，每个奇数变为一个偶数，于是，经 1、2、 次操作变为 1 的数的个数依次为：1，1，2，3，5，8， 这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过 9 次操作变为 1 的数有 34 个. 为什么上面的规律是正确的呢？ 道理也很简单. 设经过n次操作变为 1 的数的个数为 n a,则 1 a 1， 2 a 1， 3 a 2， 从上面的图看出， 1n a 比 n a大. 一方面，每个经过n次操作变为 1 的数，乘以 2，就得出一个偶数，经过1n 次操作变为 1；反过来， 每个经过1n 次操作变为 1 的偶数，除以 2，就得出一个经过n次操作变为 1 的数. 所以

18、经过n次操 作变为 1 的数与经过1n 次操作变为 1 的偶数恰好一样多.前者的个数是 n a,因此后者也是 n a个. 另一方面，每个经过n次操作变为 1 的偶数，减去 1，就得出一个奇数，它经过1n 次操作变为 1， 反过来.每个经过1n 次操作变为 1 的奇数，加上 1，就得出一个偶数，它经过n次操作变为 1. 所以 经过n次操作变为 1 的偶数经过1n 次操作变为 1 的奇数恰好一样多. 而由上面所说，前者的个数就是 1n a ,因此后者也是 1n a . 经过n 1 次操作变为 1 的数，分为偶数、奇数两类，所以 11nnn aaa ，即上面所说的规律的确 成立. 【答案】34 【例

19、【例 11】有有 20 个石子个石子，一个人分若干次取一个人分若干次取，每次可以取每次可以取 1 个个，2 个或个或 3 个个，但是每次取完之后不能留下但是每次取完之后不能留下 质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数） 7-6-4.计数之递推法.题库教师版page5of8 【考点】计数之递推法【难度】5 星【题型】解答 【解析】【解析】如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前 面 3 个数相加现在剩下的不能是质数个，可以看作是质数个的取法总数都是 0，然后再

20、进行递推 【答案】25 【巩固】有【巩固】有 20 个相同的棋子，一个人分若干次取，每次可取个相同的棋子，一个人分若干次取，每次可取 1 个，个，2 个，个，3 个或个或 4 个，但要求每次取之后留个，但要求每次取之后留 下的棋子数不是下的棋子数不是 3 或或 4 的倍数，有的倍数，有种不同的方法取完这堆棋子种不同的方法取完这堆棋子. 【考点】计数之递推法【难度】5 星【题型】填空 【解析】【解析】把 20、0 和 20 以内不是 3 或 4 的倍数的数写成一串，用递推法把所有的方法数写出来： 【答案】54 【例【例 12】4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由

21、甲发球，并作个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作 为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？ 【考点】计数之递推法【难度】5 星【题型】解答 【解析】【解析】设第n次传球后，球又回到甲手中的传球方法有 n a种可以想象前1n 次传球，如果每一次传球都 任选其他三人中的一人进行传球， 即每次传球都有3种可能， 由乘法原理， 共有 1 13 3 3 333n n ()个 (种) 传球方法这些传球方法并不是都符合要求的，它们可以分为两类，一类是第1n 次恰好传到甲手 中，

22、这有 1n a 种传法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第1n 次传 球 ， 球 不 在 甲 手 中 ， 第n次 持 球 人 再 将 球 传 给 甲 ， 有 n a种 传 法 根 据 加 法 原 理 ， 有 1 1 13 3 333n nn n aa (个 ) 由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以 1 0a 利 用 递 推 关 系 可 以 得 到 ： 2 303a ， 3 3 336a ， 4 3 3 3621a ， 5 3 3 3 32160a 这说明经过5次传球后，球仍回到甲手中的传球方法有60种 本题也可以列表求解 由于第n次传球后，

23、球不在甲手中的传球方法，第1n 次传球后球就可能回到甲手中，所以只需求 出第四次传球后，球不在甲手中的传法共有多少种 从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种 【答案】60 【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中问：共次传球后，球仍回到甲手中问：共 有多少种传球方式？有多少种传球方式？ 【考点】计数之递推法【难度】5 星【题型】解答 【解析】【解析】递推法设第n次传球后球传到甲的手中的方法有 n a种由于每次传球有 4 种选择，传n次有4n次 可能其中有的球在甲的

24、手中，有的球不在甲的手中，球在甲的手中的有 n a种，球不在甲的手中的， 7-6-4.计数之递推法.题库教师版page6of8 下一次传球都可以将球传到甲的手中，故有 1n a 种所以 1 4n nn aa 由于 1 0a ，所以 1 21 44aa， 2 32 412aa， 3 43 452aa即经过4次传球后，球仍回 到甲手中的传球方法有 52 种 【答案】52 【例【例 13】设设A、E为正八边形为正八边形ABCDEFGH的相对顶点，顶点的相对顶点，顶点A处有一只青蛙，除顶点处有一只青蛙，除顶点E外青蛙可以从外青蛙可以从 正八边形的任一顶点跳到其相邻两个顶点中任意一个正八边形的任一顶点跳

25、到其相邻两个顶点中任意一个，落到顶点落到顶点E时青蛙就停止跳动时青蛙就停止跳动，则青蛙从顶则青蛙从顶 点点A出发恰好跳出发恰好跳10次后落到次后落到E的方法总数为的方法总数为种种 【考点】计数之递推法【难度】5 星【题型】填空 【关键词】清华附中 【解析】【解析】可以使用递推法 回到A跳到B或H跳到C或G跳到D或F停在E 1 步1 2 步21 3 步31 4 步642 5 步104 6 步20148 7 步3414 8 步684828 9 步11648 其中，第一列的每一个数都等于它的上一行的第二列的数的 2 倍，第二列的每一个数都等于它的上 一行的第一列和第三列的两个数的和，第三列的每一个数

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

27、5 星【题型】填空 【解析】【解析】采用递推的方法列表如下： 跳到A跳到B跳到C停在D跳到E 1 步11 2 步211 3 步312 4 步532 5 步835 6 步1385 其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动所以， 每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和，每一步跳到B的跳法数等于上一步跳 到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到B的跳法数，每一步跳到E的跳法 数等于上一步跳到A的跳法数，每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数 观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在 6 次之内(含 6

28、 次)跳到D点共有 1 123512 种不同的跳法 【答案】12 7-6-4.计数之递推法.题库教师版page7of8 【例【例 14】有有 6 个木箱，编号为个木箱，编号为 1，2，3，6，每个箱子有一把钥匙，每个箱子有一把钥匙，6 把钥匙各不相同，每个箱子把钥匙各不相同，每个箱子 放进一把钥匙锁好放进一把钥匙锁好先挖开先挖开 1，2 号箱子号箱子，可以取出钥匙去开箱子上的锁可以取出钥匙去开箱子上的锁，如果最终能把如果最终能把 6 把锁都打把锁都打 开，则说这是一种放钥匙的开，则说这是一种放钥匙的“好好”的方法，那么的方法，那么“好好”的方法共有的方法共有种种 【考点】计数之递推法【难度】5

29、 星【题型】填空 【关键词】迎春杯，中年级组，决赛 【解析】【解析】(法 1)分类讨论如果 1，2 号箱中恰好放的就是 1，2 号箱的钥匙，显然不是“好”的方法，所以“好” 的方法有两种情况： 1，2 号箱的钥匙恰有 1 把在 1，2 号箱中，另一箱装的是 36 箱的钥匙 1，2 号箱的钥匙都不在 1，2 号箱中 对于，从 1，2 号箱的钥匙中选 1 把，从 36 号箱的钥匙中选 1 把，共有248(种)选法，每一 种选法放入 1，2 号箱各有 2 种放法，共有8216(种)放法 不妨设 1，3 号箱的钥匙放入了 1，2 号箱，此时 3 号箱不能装 2 号箱的钥匙，有 3 种选法，依次类 推，

30、可知此时不同的放法有32 16 (种) 所以，第种情况有“好”的方法16696(种) 对于，从 36 号箱的钥匙中选 2 把放入 1，2 号箱，有4312(种)放法不妨设 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 号箱中，有224种放法； 如果 3，4 号箱中有 1 把 5，6 号箱的钥匙，比如 3，4 号箱中放的是 5，1 号箱的钥

31、匙，则只能是 5 号箱放 6 号箱的钥匙，6 号箱放 2 号箱的钥匙，有2 12 种放法； 同理，3，4 号箱放 5，2 号箱或 6，1 号箱或 6，2 号箱的钥匙，也各有 2 种放法 所以，第种情况有“好”的放法1242222144(种) 所以“好”的方法共有96144240(种) (法 2)递推法设第 1，2，3，6 号箱子中所放的钥匙号码依次为 1 k， 2 k， 3 k， 6 k当箱子 数为n(2n )时，好的放法的总数为 n a 当2n 时，显然 2 2a ( 1 1k ， 2 2k 或 1 2k ， 2 1k ) 当3n 时，显然 3 3k ，否则第 3 个箱子打不开，从而 1 3

32、k 或 2 3k ，如果 1 3k ，则把 1 号箱子 和 3 号箱子看作一个整体，这样还是锁着 1，2 两号钥匙，撬开 1，2 两号箱子，那么方法有 2 a种； 当 2 3k 也是如此于是2n 时的每一种情况对应 1 3k 或 2 3k 时的一种情况，这样就有 32 24aa 当4n 时，也一定有 n kn，否则第n个箱子打不开，从而 1 k、 2 k、 1n k 中有一个为n，不 论其中哪一个是n， 由于必须要把该箱子打开才能打开n号箱子， 所以可以将锁着这把钥匙的箱子与 第n号箱子看作 1 个箱子，于是还是锁着 1 k、 2 k、 1n k 这1n 把钥匙，需要撬开 1，2 两号 箱子，

33、所以每种情况都有 1n a 种所以 1 1 nn ana 所以， 6542 554543225!240aaaa ，即好的方法总数为 240 种 【答案】240 【巩固【巩固】有有 10 个木箱个木箱，编号为编号为 1，2，3，10，每个箱子有一把钥匙每个箱子有一把钥匙，10 把钥匙各不相同把钥匙各不相同，每个箱子放每个箱子放 进一把钥匙锁好先挖开进一把钥匙锁好先挖开 1，2 号箱子，可以取出钥匙去开箱子上的锁，如果最终能把号箱子，可以取出钥匙去开箱子上的锁，如果最终能把 10 把锁都打把锁都打 开，则说这是一种放钥匙的开，则说这是一种放钥匙的“好好”的方法，那么的方法，那么“好好”的方法共有的

34、方法共有种种 【考点】计数之递推法【难度】5 星【题型】填空 【解析】【解析】递推法 设第 1， 2， 3， ， 6 号箱子中所放的钥匙号码依次为 1 k， 2 k， 3 k， ， 6 k 当箱子数为n(2n ) 时，好的放法的总数为 n a 当2n 时，显然 2 2a ( 1 1k ， 2 2k 或 1 2k ， 2 1k ) 当3n 时，显然 3 3k ，否则第 3 个箱子打不开，从而 1 3k 或 2 3k ，如果 1 3k ，则把 1 号箱子 和 3 号箱子看作一个整体，这样还是锁着 1，2 两号钥匙，撬开 1，2 两号箱子，那么方法有 2 a种； 7-6-4.计数之递推法.题库教师版

35、page8of8 当 2 3k 也是如此于是2n 时的每一种情况对应 1 3k 或 2 3k 时的一种情况，这样就有 32 24aa 当4n 时，也一定有 n kn，否则第n个箱子打不开，从而 1 k、 2 k、 1n k 中有一个为n，不 论其中哪一个是n， 由于必须要把该箱子打开才能打开n号箱子， 所以可以将锁着这把钥匙的箱子与 第n号箱子看作 1 个箱子，于是还是锁着 1 k、 2 k、 1n k 这1n 把钥匙，需要撬开 1，2 两号 箱子，所以每种情况都有 1n a 种所以 1 1 nn ana 所以， 10982 99 89 876543229!=725760aaaa ，即好的方法总数为 725760 种 【答案】725760