前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法,比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等,这里再集中学习一下计数中其他常见的方法,主要有归纳法、整体法、对应法、递推法.对这些计数方法与技巧要做到灵活运用.
对于某些难以发现其一般情形的计数问题,可以找出其相邻数之间的递归关系,有了这一递归关系就可以利用前面的数求出后面未知的数,这种方法称为递推法.
【例 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对兔子.
【答案】
【例 2】 树木生长的过程中,新生的枝条往往需要一段“休息”时间供自身生长,而后才能萌发新枝.一棵树苗在一年后长出一条新枝,第二年新枝“休息”,老枝依旧萌发新枝;此后,老枝与“休息”过一年的枝同时萌发,当年生的新枝则依次“休息”.这在生物学上称为“鲁德维格定律”.那么十年后这棵树上有多少条树枝?
【考点】计数之递推法 【难度】3星 【题型】解答
【解析】 一株树木各个年份的枝桠数,构成斐波那契数列:1,2,3,5,8,13,21,34,55,89,……所以十年后树上有89条树枝.
【答案】
【例 3】 一楼梯共10级,规定每步只能跨上一级或两级,要登上第10级,共有多少种不同走法?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 登1级 2级 3级 4级 ...... 10级
1种方法 2种 3种 5种 ...... ?
我们观察每级的种数,发现这么一个规律:从第三个数开始,每个数是前面两个数的和;依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用:假如我们把这个人开始登楼梯的位置看做A0,那么登了1级的位置是在A1,2级在A2... A10级就在A10.到A3的前一步有两个位置;分别是A2 和A1 .在这里要强调一点,那么A2 到A3 既然是一步到了,那么A2 、A3之间就是一种选择了;同理A1 到A3 也是一种选择了.同时我们假设到n级的选择数就是An .那么从A0 到A3 就可以分成两类了:第一类:A0 ---- A1 ------ A3 ,那么就可以分成两步.有A1×1种,也就是A1 种;(A1 ------ A3是一种选择)第二类:A0 ---- A2 ------ A3, 同样道理 有A2 .类类相加原理:A3 = A1 +A2,依次类推An = An-1 + An-2.
【答案】
【巩固】一楼梯共10级,规定每步只能跨上一级或三级,要登上第10级,共有多少种不同走法?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 登1级 2级 3级 4级 5级...... 10级
1种方法 1种 2种 3种 4种...... ?
我们观察每级的种数,发现这么一个规律:从第三个数开始,每个数是前面相隔的两个数的和;依此规律我们就可以知道了第10级的种数是28.
【答案】
【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网,共有多少种不同的盖法.
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 如果用
【答案】
【例 5】 用
【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 如果用
1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 |
所以用
【答案】
【例 6】 有一堆火柴共12根,如果规定每次取1~3根,那么取完这堆火柴共有多少种不同取法?
【考点】计数之递推法 【难度】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种方法.
【答案】
【巩固】一堆苹果共有8个,如果规定每次取1~3个,那么取完这堆苹果共有多少种不同取法?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 取1个苹果有1种方法,取2个苹果有2种方法,取3个苹果有4种取法,以后取任意个苹果的种数等于取到前三个苹果所有情况之和,以此类推,参照上题列表如下:
1个 | 2个 | 3个 | 4个 | 5个 | 6个 | 7个 | 8个 |
1 | 2 | 4 | 7 | 13 | 24 | 44 | 81 |
取完这堆苹果一共有81种方法.
【答案】
【例 7】 有10枚棋子,每次拿出2枚或3枚,要想将10枚棋子全部拿完,共有多少种不同的拿法?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】本题可以采用递推法,也可以进行分类讨论,当然也可以直接进行枚举.
(法1)递推法.假设有
则
由于每次拿出2枚或3枚,所以
所以,
即当有10枚棋子时,共有7种不同的拿法.
(法2)分类讨论.
由于棋子总数为10枚,是个偶数,而每次拿2枚或3枚,所以其中拿3枚的次数也应该是偶数.由于拿3枚的次数不超过3次,所以只能为0次或2次.
若为0次,则相当于2枚拿了5次,此时有1种拿法;
若为2次,则2枚也拿了2次,共拿了4次,所以此时有
根据加法原理,共有
【答案】
【例 8】 如下图,一只蜜蜂从
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房.明确了行走路径的方向,就可以运用标数法进行计算.如右图所示,小蜜蜂从A出发到B处共有89种不同的回家方法.
【答案】
【巩固】小蜜蜂通过蜂巢房间,规定只能由小号房间进入大号房间问小蜜蜂由
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 斐波那契数列第八项.21种.
【答案】
【例 9】 如下图,一只蜜蜂从A处出发,回到家里B处,每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行,共有多少种回家的方法?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则,运用标号法进行计算.如右图所示,小蜜蜂从A出发到B处共有296种不同的回家方法.
【答案】
【例 10】 对一个自然数作如下操作:如果是偶数则除以2,如果是奇数则加1,如此进行直到得数为1操作停止.问经过9次操作变为1的数有多少个?
【考点】计数之递推法 【难度】4星 【题型】解答
【解析】 可以先尝试一下,倒推得出下面的图:
其中经1次操作变为1的1个,即2,
经2次操作变为1的1个,即4,
经3次操作变为1的2个,是一奇一偶,
以后发现,每个偶数可以变成两个数,分别是一奇一偶,每个奇数变为一个偶数,于是,经1、2、…次操作变为1的数的个数依次为:1,1,2,3,5,8,…
这一串数中有个特点:自第三个开始,每一个等于前两个的和,即即经过9次操作变为1的数有34个.
为什么上面的规律是正确的呢?
道理也很简单. 设经过
从上面的图看出,
一方面,每个经过
另一方面,每个经过
而由上面所说,前者的个数就是
经过
【答案】
【例 11】 有20个石子,一个人分若干次取,每次可以取1个,2个或3个,但是每次取完之后不能留下质数个,有多少种方法取完石子?(石子之间不作区分,只考虑石子个数)
【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 如果没有剩下的不能使质数这个条件,那么递推方法与前面学过的递推法相似,只不过每次都是前面3个数相加.现在剩下的不能是质数个,可以看作是质数个的取法总数都是0,然后再进行递推.
【答案】
【巩固】有20个相同的棋子,一个人分若干次取,每次可取1个,2个,3个或4个,但要求每次取之后留下的棋子数不是3或4的倍数,有 种不同的方法取完这堆棋子.
【考点】计数之递推法 【难度】5星 【题型】填空
【解析】 把20、0和20以内不是3或4的倍数的数写成一串,用递推法把所有的方法数写出来:
【答案】
【例 12】
【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 设第
由于甲是发球者,一次传球后球又回到甲手中的传球方法是不存在的,所以
利用递推关系可以得到:
这说明经过
本题也可以列表求解.
由于第
从表中可以看出经过五次传球后,球仍回到甲手中的传球方法共有
【答案】
【巩固】五个人互相传球,由甲开始发球,并作为第一次传球,经过
【考点】计数之递推法 【难度】5星 【题型】解答
【解析】 递推法.设第
由于
【答案】
【例 13】 设
【考点】计数之递推法 【难度】5星 【题型】填空
【关键词】清华附中
【解析】 可以使用递推法.
回到
1步 1
2步 2 1
3步 3 1
4步 6 4 2
5步 10 4
6步 20 14 8
7步 34 14
8步 68 48 28
9步 116 48
其中,第一列的每一个数都等于它的上一行的第二列的数的2倍,第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和,第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和,第四列的每一个数都等于它的上一行的第三列的数,第五列的每一个数都等于都等于它的上一行的第四列的数的2倍.这一规律很容易根据青蛙的跳动规则分析得来.
所以,青蛙第10步跳到
【答案】
【巩固】在正五边形
【考点】计数之递推法 【难度】5星 【题型】填空
【解析】采用递推的方法.列表如下:
跳到
1步 1 1
2步 2 1 1
3步 3 1 2
4步 5 3 2
5步 8 3 5
6步 13 8 5
其中,根据规则,每次可以随意跳到相邻两个顶点中的一个上,一旦跳到
观察可知,上面的递推结果与前面的枚举也相吻合,所以青蛙在6次之内(含6次)跳到
【答案】
【例 14】 有6个木箱,编号为1,2,3,……,6,每个箱子有一把钥匙,6把钥匙各不相同,每个箱子放进一把钥匙锁好.先挖开1,2号箱子,可以取出钥匙去开箱子上的锁,如果最终能把6把锁都打开,则说这是一种放钥匙的“好”的方法,那么“好”的方法共有 种.
【考点】计数之递推法 【难度】5星 【题型】填空
【关键词】迎春杯,中年级组,决赛
【解析】 (法1)分类讨论.如果1,2号箱中恰好放的就是1,2号箱的钥匙,显然不是“好”的方法,所以“好”的方法有两种情况:
⑴1,2号箱的钥匙恰有1把在1,2号箱中,另一箱装的是3~6箱的钥匙.
⑵1,2号箱的钥匙都不在1,2号箱中.
对于⑴,从1,2号箱的钥匙中选1把,从3~6号箱的钥匙中选1把,共有
不妨设1,3号箱的钥匙放入了1,2号箱,此时3号箱不能装2号箱的钥匙,有3种选法,依次类推,可知此时不同的放法有
所以,第⑴种情况有“好”的方法
对于⑵,从3~6号箱的钥匙中选2把放入1,2号箱,有
此时1,2号箱的钥匙不可能都放在3,4号箱中,也就是说3,4号箱中至少有1把5,6号箱的钥匙.
如果3,4号箱中有2把5,6号箱的钥匙,也就是说3,4号箱中放的恰好是5,6号箱的钥匙,那么1,2号箱的钥匙放在5,6号箱中,有
如果3,4号箱中有1把5,6号箱的钥匙,比如3,4号箱中放的是5,1号箱的钥匙,则只能是5号箱放6号箱的钥匙,6号箱放2号箱的钥匙,有
同理,3,4号箱放5,2号箱或6,1号箱或6,2号箱的钥匙,也各有2种放法.
所以,第⑵种情况有“好”的放法
所以“好”的方法共有
(法2)递推法.设第1,2,3,…,6号箱子中所放的钥匙号码依次为
当
当
当
所以,
【答案】
【巩固】有10个木箱,编号为1,2,3,……,10,每个箱子有一把钥匙,10把钥匙各不相同,每个箱子放进一把钥匙锁好.先挖开1,2号箱子,可以取出钥匙去开箱子上的锁,如果最终能把10把锁都打开,则说这是一种放钥匙的“好”的方法,那么“好”的方法共有 种.
【考点】计数之递推法 【难度】5星 【题型】填空
【解析】 递推法.设第1,2,3,…,6号箱子中所放的钥匙号码依次为
当
当
当
所以,
【答案】
联系客服