7-6-4 计数之递推法 教师版

7-6-4.计数之递推法

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法,比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等,这里再集中学习一下计数中其他常见的方法,主要有归纳法、整体法、对应法、递推法.对这些计数方法与技巧要做到灵活运用.

教学目标

对于某些难以发现其一般情形的计数问题,可以找出其相邻数之间的递归关系,有了这一递归关系就可以利用前面的数求出后面未知的数,这种方法称为递推法. 【例 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星 【题型】解答

例题精讲

7-6-4.计数之递推法.题库 教师版 page 1 of 9

【解析】 登 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.

【答案】89

【巩固】一楼梯共10级,规定每步只能跨上一级或三级,要登上第10级,共有多少种不同走法? 【考点】计数之递推法 【难度】4星 【题型】解答

【解析】 登 1级 2级 3级 4级 5级 ...... 10级

1种方法 1种 2种 3种 4种...... ?

我们观察每级的种数,发现这么一个规律:从第三个数开始,每个数是前面相隔的两个数的和;依此规律我们就可以知道了第10级的种数是28.

【答案】28

【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网,共有多少种不同的盖法. 【考点】计数之递推法 【难度】4星 【题型】解答

【解析】 如果用1?2的长方形盖2?n的长方形,设种数为an,则a1?1,a2?2,对于n?3,左边可能竖放1个

1?2的,也可能横放2个1?2的,前者有an-1种,后者有an-2种,所以an?an-1?an-2,所以根据递推,

覆盖2?10的长方形一共有89种.

7-6-4.计数之递推法.题库 教师版 page 2 of 9

【答案】89

【例 5】 用1?3的小长方形覆盖3?8的方格网,共有多少种不同的盖法? 【考点】计数之递推法 【难度】5星 【题型】解答

【解析】 如果用1?3的长方形盖3?n的长方形,设种数为an,则a1?1,a2?1,a3?2,对于n?4,左边可能竖

放1个1?3的,也可能横放3个1?3的,前者有an-1种,后者有an-3种,所以an?an-1?an-3,依照这条递推公式列表: 3?1 3?2 1 1 3?3 3?4 3?5 3?6 3?7 3?8 2 3 4 6 9 13 所以用1?3的小长方形形覆盖3?8的方格网,共有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根 1 2 4 7 13 24 44 81 149 274 504 927 取完这堆火柴一共有927种方法. 【答案】927

【巩固】 一堆苹果共有8个,如果规定每次取1~3个,那么取完这堆苹果共有多少种不同取法? 【考点】计数之递推法 【难度】4星 【题型】解答

【解析】 取1个苹果有1种方法,取2个苹果有2种方法,取3个苹果有4种取法,以后取任意个苹果的种

数等于取到前三个苹果所有情况之和,以此类推,参照上题列表如下: 1个 1 2个 2 3个 4 4个 7 5个 13 6个 24 7个 44 8个 81 取完这堆苹果一共有81种方法. 【答案】81

【例 7】 有10枚棋子,每次拿出2枚或3枚,要想将10枚棋子全部拿完,共有多少种不同的拿法? 【考点】计数之递推法 【难度】4星 【题型】解答

【解析】 本题可以采用递推法,也可以进行分类讨论,当然也可以直接进行枚举.

(法1)递推法.假设有n枚棋子,每次拿出2枚或3枚,将n枚棋子全部拿完的拿法总数为an种. 则a2?1,a3?1,a4?1.

由于每次拿出2枚或3枚,所以an?an?3?an?2(n?5).

所以,a5?a2?a3?2;a6?a3?a4?2;a7?a4?a5?3;a8?a5?a6?4;a9?a6?a7?5;a10?a7?a8?7.

即当有10枚棋子时,共有7种不同的拿法. (法2)分类讨论.

由于棋子总数为10枚,是个偶数,而每次拿2枚或3枚,所以其中拿3枚的次数也应该是偶数.由于拿3枚的次数不超过3次,所以只能为0次或2次. 若为0次,则相当于2枚拿了5次,此时有1种拿法;

7-6-4.计数之递推法.题库 教师版 page 3 of 9

2若为2次,则2枚也拿了2次,共拿了4次,所以此时有C4?6种拿法.

根据加法原理,共有1?6?7种不同的拿法.

【答案】7

【例 8】 如下图,一只蜜蜂从A处出发,回到家里B处,每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆

行,共有多少种回家的方法? 【考点】计数之递推法 【难度】4星 【题型】解答

11323558721955B89ABA124613834

【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相

邻大号码的蜂房.明确了行走路径的方向,就可以运用标数法进行计算.如右图所示,小蜜蜂从A出发到B处共有89种不同的回家方法.

【答案】89

【巩固】小蜜蜂通过蜂巢房间,规定只能由小号房间进入大号房间问小蜜蜂由A房间到达B 房间有多少种

方法? 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 斐波那契数列第八项.21种.

12357846【答案】21

【例 9】 如下图,一只蜜蜂从A处出发,回到家里B处,每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆

行,共有多少种回家的方法? 【考点】计数之递推法 【难度】4星 【题型】解答

AB

【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则,运用标号法进行计算.如右图所示,

小蜜蜂从A出发到B处共有296种不同的回家方法.

【答案】296

【例 10】 对一个自然数作如下操作:如果是偶数则除以2,如果是奇数则加1,如此进行直到得数为1

操作停止.问经过9次操作变为1的数有多少个? 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 可以先尝试一下,倒推得出下面的图:

7-6-4.计数之递推法.题库 教师版 page 4 of 9

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4