奥数全年级一百七十九专题题库学生版764计数之递推法学生版

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．【例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】一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？【考点】计数之递推法【难度】4星【题型】解答【解析】登1级2级3级4级......10级例题精讲教学目标7-6-4.计数之递推法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．【答案】89【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？【考点】计数之递推法【难度】4星【题型】解答【解析】登1级2级3级4级5级......10级1种方法1种2种3种4种......？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.【答案】28【例4】1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法．【考点】计数之递推法【难度】4星【题型】解答【解析】如果用12的长方形盖2n的长方形，设种数为na,则11a，22a,对于3n，左边可能竖放1个12的，也可能横放2个12的，前者有-1na种，后者有-2na种，所以-1-2nnnaaa,所以根据递推，覆盖210的长方形一共有89种．【答案】89【例5】用13的小长方形覆盖38的方格网，共有多少种不同的盖法？【考点】计数之递推法【难度】5星【题型】解答【解析】如果用13的长方形盖3n的长方形，设种数为na,则11a，21a,32a,对于4n，左边可能竖放1个13的，也可能横放3个13的，前者有-1na种，后者有-3na种，所以-1-3nnnaaa,依照这条递推公式列表：3132333435363738112346913所以用13的小长方形形覆盖38的方格网，共有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)递推法．假设有n枚棋子，每次拿出2枚或3枚，将n枚棋子全部拿完的拿法总数为na种．则21a，31a，41a．由于每次拿出2枚或3枚，所以32nnnaaa(5n)．所以，5232aaa；6342aaa；7453aaa；8564aaa；9675aaa；10787aaa．即当有10枚棋子时，共有7种不同的拿法．(法2)分类讨论．由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次．若为0次，则相当于2枚拿了5次，此时有1种拿法；若为2次，则2枚也拿了2次，共拿了4次，所以此时有246C种拿法．根据加法原理，共有167种不同的拿法．【答案】7【例8】如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法【难度】4星【题型】解答BAAB1357946821235813213455891【解析】蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A出发到B处共有89种不同的回家方法．【答案】89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A房间到达B房间有多少种方法？【考点】计数之递推法【难度】4星【题型】解答【【解解析析】】斐波那契数列第八项．21种．86427531【答案】21【例9】如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法【难度】4星【题型】解答BA【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，小蜜蜂从A出发到B处共有296种不同的回家方法．【答案】296【例10】对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？【考点】计数之递推法【难度】4星【题型】解答【【解解析析】】可以先尝试一下，倒推得出下面的图：2410131112514302831643215167683421其中经1次操作变为1的1个，即2，经2次操作变为1的1个，即4，经3次操作变为1的2个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.为什么上面的规律是正确的呢？道理也很简单.设经过n次操作变为1的数的个数为na,则1a1，2a1，3a2，…从上面的图看出，1na比na大.一方面，每个经过n次操作变为1的数，乘以2，就得出一个偶数，经过1n次操作变为1；反过来，每个经过1n次操作变为1的偶数，除以2，就得出一个经过n次操作变为1的数.所以经过n次操作变为1的数与经过1n次操作变为1的偶数恰好一样多.前者的个数是na,因此后者也是na个.另一方面，每个经过n次操作变为1的偶数，减去1，就得出一个奇数，它经过1n次操作变为1，反过来.每个经过1n次操作变为1的奇数，加上1，就得出一个偶数，它经过n次操作变为1.所以经过n次操作变为1的偶数经过1n次操作变为1的奇数恰好一样多.而由上面所说，前者的个数就是1na,因此后者也是1na.经过n1次操作变为1的数，分为偶数、奇数两类，所以11nnnaaa，即上面所说的规律的确成立.【答案】34【例11】有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【考点】计数之递推法【难度】5星【题型】解答【【解解析析】】如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．【答案】25【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是3或4的倍数，有种不同的方法取完这堆棋子.【考点】计数之递推法【难度】5星【题型】填空【【解解析析】】把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：【答案】54【例12】4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【考点】计数之递推法【难度】5星【题型】解答【【解解析析】】设第n次传球后，球又回到甲手中的传球方法有na种．可以想象前1n次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有11333333nn()个…(种)传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第1n次恰好传到甲手中，这有1na种传法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第1n次传球，球不在甲手中，第n次持球人再将球传给甲，有na种传法．根据加法原理，有11133333nnnnaa(个…)．由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以10a．利用递推关系可以得到：2303a，33336a，4333621a，533332160a．这说明经过5次传球后，球仍回到甲手中的传球方法有60种．本题也可以列表求解．由于第n次传球后，球不在甲手中的传球方法，第1n次传球后球就可能回到甲手中，