小学数学知识点例题精讲《计数之递推法》教师版.pdf

《小学数学知识点例题精讲《计数之递推法》教师版.pdf》由会员分享，可在线阅读，更多相关《小学数学知识点例题精讲《计数之递推法》教师版.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、解析解析】第一个月,有 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-89144,所以十二月份的时候总共有144

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

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

5、 到 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 级,共有多少种不同走法?【考点】计数之递推法 【难度】4 星 【题型】解答【解

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

7、aaa,所以根据递推,覆盖2 10的长方形一共有 89 种【答案】89【例例 5】 用1 3的小长方形覆盖3 8的方格网,共有多少种不同的盖法?【考点】计数之递推法 【难度】5 星 【题型】解答【解析】如果用1 3的长方形盖3n的长方形,设种数为na,则11a ,21a ,32a ,对于4n ,左边可能竖放 1 个1 3的,也可能横放 3 个1 3的,前者有-1na种,后者有-3na种,所以-1-3nnnaaa,依照这条递3推公式列表：3 1323 3343 53 63 73 8112346913所以用1 3的小长方形形覆盖3 8的方格网,共有 13 种不同的盖法【答案】13【例例 6】 有一

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

9、 【难度】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枚棋子,每

10、次拿出 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

11、次,所以此时有246C 种拿法根据加法原理,共有167种不同的拿法【答案】7【例例 8】 如下图,一只蜜蜂从A处出发,回到家里B处,每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行,共有多少种回家的方法?【考点】计数之递推法 【难度】4 星 【题型】解答BA AB1357946821235813213455891【解析】蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房明确了行走路径的方向,就可以运用标数法进行计算如右图所示,小蜜蜂从 A出发到 B 处共有 89 种不同的回家方法4【答案】89【巩固】小蜜蜂通过蜂巢房间,规定只能由小号房间进入大

12、号房间问小蜜蜂由A房间到达B 房间有多少种方法?【考点】计数之递推法 【难度】4 星 【题型】解答【解析解析解析】斐波那契数列第八项21 种86427531【答案】21【例例 9】 如下图,一只蜜蜂从 A 处出发,回到家里 B 处,每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行,共有多少种回家的方法?【考点】计数之递推法 【难度】4 星 【题型】解答BA 【解析】按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则,运用标号法进行计算如右图所示,小蜜蜂从 A 出发到 B 处共有 296 种不同的回家方法【答案】296【例例 10】对一个自然数作如下操作：如果是偶数则除以 2,如果是奇数则加 1

13、,如此进行直到得数为 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, 这一串数中有个特点：自第三个开始,每一个等于前两个的和,即即经过

14、 9 次操作变为 1 的数有 34个.为什么上面的规律是正确的呢?道理也很简单. 设经过n次操作变为 1 的数的个数为na,则1a 1,2a 1,3a2,5从上面的图看出,1na比na大. 一方面,每个经过n次操作变为 1 的数,乘以 2,就得出一个偶数,经过1n 次操作变为 1;反过来,每个经过1n 次操作变为 1 的偶数,除以 2,就得出一个经过n次操作变为 1 的数. 所以经过n次操作变为 1 的数与经过1n 次操作变为 1 的偶数恰好一样多.前者的个数是na,因此后者也是na个.另一方面,每个经过n次操作变为 1 的偶数,减去 1,就得出一个奇数,它经过1n 次操作变为 1,反过来.每

15、个经过1n 次操作变为 1 的奇数,加上 1,就得出一个偶数,它经过n次操作变为 1. 所以经过n次操作变为 1 的偶数经过1n 次操作变为 1 的奇数恰好一样多.而由上面所说,前者的个数就是1na,因此后者也是1na.经过n 1 次操作变为 1 的数,分为偶数、奇数两类,所以11nnnaaa,即上面所说的规律的确成立.【答案】34【例例 11】有 20 个石子,一个人分若干次取,每次可以取 1 个,2 个或 3 个,但是每次取完之后不能留下质数个,有多少种方法取完石子?（石子之间不作区分,只考虑石子个数）【考点】计数之递推法 【难度】5 星 【题型】解答【解析解析解析】如果没有剩下的不能使质

16、数这个条件,那么递推方法与前面学过的递推法相似,只不过每次都是前面3 个数相加现在剩下的不能是质数个,可以看作是质数个的取法总数都是 0,然后再进行递推【答案】25【巩固】有 20 个相同的棋子,一个人分若干次取,每次可取 1 个,2 个,3 个或 4 个,但要求每次取之后留下的棋子数不是 3 或 4 的倍数,有种不同的方法取完这堆棋子. 【考点】计数之递推法 【难度】5 星 【题型】填空【解析解析解析】把 20、0 和 20 以内不是 3 或 4 的倍数的数写成一串,用递推法把所有的方法数写出来：【答案】54【例例 12】4个人进行篮球训练,互相传球接球,要求每个人接球后马上传给别人,开始由

17、甲发球,并作为第一次传球,第五次传球后,球又回到甲手中,问有多少种传球方法?【考点】计数之递推法 【难度】5 星 【题型】解答【解析解析解析】设第n次传球后,球又回到甲手中的传球方法有na种可以想象前1n 次传球,如果每一次传球都任选其他三人中的一人进行传球,即每次传球都有3种可能,由乘法原理,共有1133 3 333nn ()个(种)传球方法这些传球方法并不是都符合要求的,它们可以分为两类,一类是第1n 次恰好传到甲手中,这有1na种传法,它们不符合要求,因为这样第n次无法再把球传给甲;另一类是第1n 次传球,球不在甲手中,第n次持球人再将球传给甲,有na种传法根据加法原理,有11133 3

18、33nnnnaa (个)由于甲是发球者,一次传球后球又回到甲手中的传球方法是不存在的,所以10a 利用递推关系可以得到：2303a ,33 336a ,43 3 3621a ,53 3 3 32160a 这说明经过5次传球后,球仍回到甲手中的传球方法有60种本题也可以列表求解由于第n次传球后,球不在甲手中的传球方法,第1n 次传球后球就可能回到甲手中,所以只需求出第四次传球后,球不在甲手中的传法共有多少种6从表中可以看出经过五次传球后,球仍回到甲手中的传球方法共有60种【答案】60【巩固】五个人互相传球,由甲开始发球,并作为第一次传球,经过4次传球后,球仍回到甲手中问：共有多少种传球方式?【考

19、点】计数之递推法 【难度】5 星 【题型】解答【解析解析解析】递推法设第n次传球后球传到甲的手中的方法有na种由于每次传球有 4 种选择,传n次有4n次可能其中有的球在甲的手中,有的球不在甲的手中,球在甲的手中的有na种,球不在甲的手中的,下一次传球都可以将球传到甲的手中,故有1na种所以14nnnaa由于10a ,所以12144aa,232412aa,343452aa即经过4次传球后,球仍回到甲手中的传球方法有 52 种【答案】52【例例 13】设A、E为正八边形ABCDEFGH的相对顶点,顶点A处有一只青蛙,除顶点E外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个,落到顶点E时青

20、蛙就停止跳动,则青蛙从顶点A出发恰好跳10次后落到E的方法总数为 种【考点】计数之递推法 【难度】5 星 【题型】填空【关键词】清华附中【解析解析解析】可以使用递推法回到A跳到B或H跳到C或G跳到D或F停在E1 步12 步213 步314 步6425 步1046 步201487 步34148 步6848289 步11648其中,第一列的每一个数都等于它的上一行的第二列的数的 2 倍,第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和,第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和,第四列的每一个数都等于它的上一行的第三列的数,第五列的每一个数都等于都等于它的上一行的第四

21、列的数的 2 倍这一规律很容易根据青蛙的跳动规则分析得来所以,青蛙第 10 步跳到E有48296种方法【答案】96【巩固】在正五边形ABCDE上,一只青蛙从A点开始跳动,它每次可以随意跳到相邻两个顶点中的一个上,一旦跳到D点上就停止跳动青蛙在 6 次之内(含 6 次)跳到D点有 种不同跳法【考点】计数之递推法 【难度】5 星 【题型】填空ABCDE7【解析解析解析】采用递推的方法列表如下：跳到A 跳到B 跳到C 停在D 跳到E1 步 1 12 步 2 1 13 步 3 1 24 步 5 3 25 步 8 3 56 步 13 8 5其中,根据规则,每次可以随意跳到相邻两个顶点中的一个上,一旦跳到

22、D点上就停止跳动所以,每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和,每一步跳到B的跳法数等于上一步跳到A和C的跳法数之和,每一步跳到C的跳法数等于上一步跳到B的跳法数,每一步跳到E的跳法数等于上一步跳到A的跳法数,每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数观察可知,上面的递推结果与前面的枚举也相吻合,所以青蛙在 6 次之内(含 6 次)跳到D点共有1 123512 种不同的跳法【答案】12【例例 14】有 6 个木箱,编号为 1,2,3,6,每个箱子有一把钥匙,6 把钥匙各不相同,每个箱子放进一把钥匙锁好先挖开 1,2 号箱子,可以取出钥匙去开箱子上的锁,如果最终能把 6 把

23、锁都打开,则说这是一种放钥匙的“好”的方法,那么“好”的方法共有 种【考点】计数之递推法 【难度】5 星 【题型】填空【关键词】迎春杯,中年级组,决赛【解析解析解析】(法 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 号箱的钥匙放

24、入了 1,2 号箱,此时 3 号箱不能装 2 号箱的钥匙,有 3 种选法,依次类推,可知此时不同的放法有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 把

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

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

27、!240aaaa ,即好的方法总数为 240 种【答案】240【巩固】有 10 个木箱,编号为 1,2,3,10,每个箱子有一把钥匙,10 把钥匙各不相同,每个箱子放进一把钥匙锁好先挖开 1,2 号箱子,可以取出钥匙去开箱子上的锁,如果最终能把 10 把锁都打开,则说这是一种放钥匙的“好”的方法,那么“好”的方法共有 种【考点】计数之递推法 【难度】5 星 【题型】填空【解析解析解析】递推法设第 1,2,3,6 号箱子中所放的钥匙号码依次为1k,2k,3k,6k当箱子数为n(2n )时,好的放法的总数为na当2n 时,显然22a (11k ,22k 或12k ,21k )当3n 时,显然33k

28、 ,否则第 3 个箱子打不开,从而13k 或23k ,如果13k ,则把 1 号箱子和 3号箱子看作一个整体,这样还是锁着 1,2 两号钥匙,撬开 1,2 两号箱子,那么方法有2a种;当23k 也是如此于是2n 时的每一种情况对应13k 或23k 时的一种情况,这样就有3224aa当4n 时,也一定有nkn,否则第n个箱子打不开,从而1k、2k、1nk中有一个为n,不论其中哪一个是n,由于必须要把该箱子打开才能打开n号箱子,所以可以将锁着这把钥匙的箱子与第n号箱子看作 1 个箱子,于是还是锁着1k、2k、1nk这1n 把钥匙,需要撬开 1,2 两号箱子,所以每种情况都有1na种所以11nnana所以,1098299 89 876543229!=725760aaaa ,即好的方法总数为 725760种【答案】725760