小学奥数:计数之递推法.专项练习_第1页
小学奥数:计数之递推法.专项练习_第2页
小学奥数:计数之递推法.专项练习_第3页
小学奥数:计数之递推法.专项练习_第4页
小学奥数:计数之递推法.专项练习_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、对 兔子?【考点】计数之递推法【难度】3星【题型】解答【解析】第一个月,有1对小兔子;第二个月,长成大兔子,所以还是1对;第三个月,大兔子生下一对小兔子, 所以共有2对;第四个月,刚生下的小兔子长成大兔子, 而 原来的大兔子又生下一对小兔子,共有3对;第五个月,两对大兔子生下2对小兔子,共有5对;这个特点的说明每月的大兔子数为上月的兔子数,每月的小兔子数为上月的大兔子数, 即上上月的兔子数,所以每月的兔子数为上月的兔子数与 上上月的兔子数相加.依次类推可以列出下表:经过月数: 1 234567891011 12 兔子对数: 112358-13-21-34-55-89144,所以十月份的时候总共

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

4、有多少种不同走法?【考点】计数之递推法【难度】4星【题型】解答【解析】登 1种方法3 种2 种我们观察每级的种数,发现这么一个规律:从第三个数开始,每个数是前面两个数的和;依 此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用:假如我们把这个人开始登楼梯的位置看做 A 那么登了 1级的位置是在 A, 2级在A10级就在Ao.到的前一步有两个位置;分别是 A2和A1 .在这里要强调一点,那么 A到A 既然是一步到了,那么A2、A之间就是一种选择了;同理 A1到A3也是一种选择了.同时我们假设到nA0 -A1A3是一种选择)第二类:级的选择数就是 An .那么从 A到A3就可以分成两

5、类了:第一类: 那么就可以分成两步.有 A1 X1种,也就是 A1 种;(A1 A0 -A2 A3,=An-1 + An-2 .同样道理有A2.类类相加原理:A3 =A1 +A2,依次类推An89【巩固】同走法?【考点】一楼梯共 10级,规定每步只能跨上一级或三级,要登上第10级,共有多少种不计数之递推法【难度】4星【题型】解答即事级1种方法10级1种7-6-4.计数之递推法.题库教师版page 9 of 9每个数是前面相隔的两个数的我们观察每级的种数,发现这么一个规律: 从第三个数开始,和;依此规律我们就可以知道了第10级的种数是28.28【例4】1X2的小长方形(横的竖白都行)覆盖2X 1

6、0的方格网,共有多少种不同的盖法.【考点】计数之递推法【难度】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种.【答案】89【例5】用1 3的小长方形覆盖3 8的方格网,共有多少种不同的盖法?【考点】计数之递推法【难度】5星【题型】解答【解析】如果用1 3的长方形盖3 n的长方形,设种数为an,则a1 1 , a2 1, a3 2,对于 n 4,左边可能竖放1

7、个1 3的,也可能横放 3个1 3的,前者有an-1种,后者 有an-3种,所以an an-1 an-3,依照这条递推公式列表:3 13 23 33 43 53 63 73 81123469一13所以用1 3的小长方形形覆盖 3 8的方格网,共有13种不同的盖法.【答案】13【例6】有一堆火柴共12根,如果规定每次取 13根,那么取完这堆火柴共有多少种不 同取法?【考点】计数之递推法【难度】4星【题型】解答【解析】取1根火柴有1种方法,取2根火柴有2种方法,取3根火柴有4种取法,以后取 任意根火柴的种数等于取到前三根火柴所有情况之和,以此类推,参照上题列表如下:1根2根3根4根5根6根7根8根

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

9、考点】计数之递推法【难度】4星【题型】解答【解析】本题可以采用递推法,也可以进行分类讨论,当然也可以直接进行枚举.(法1)递推法.假设有n枚棋子,每次拿出2枚或3枚,将n枚棋子全部拿完的拿法总数为 an 种.则 a2 1, a3 1 , a4 1 .由于每次拿出2枚或3枚,所以an an 3 an 2( n 5).所以,a5a2a3 2 ;a6a3a42 ;a7a4a53 ; a8 a5%4;a9a6 a75;ao a7 a87 .即当有10枚棋子时,共有 7种不同的拿法.(法2)分类讨论.由于棋子总数为10枚,是个偶数,而每次拿 2枚或3枚,所以其中拿3枚的次数也应该是 偶数.由于拿3枚的次

10、数不超过 3次,所以只能为0次或2次.若为。次,则相当于2枚拿了 5次,此时有1种拿法;若为2次,则2枚也拿了 2次,共拿了 4次,所以此时有Cj 6种拿法.根据加法原理,共有1 6 7种不同的拿法.【答案】7【例8】如下图,一只蜜蜂从 A处出发,回到家里 B处,每次只能从一个蜂房爬向右侧邻 近的蜂房而不准逆行,共有多少种回家的方法?【考点】计数之递推法【难度】4星【题型】解答【解析】蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从 小号码的蜂房爬近相邻大号码的蜂房.明确了行走路径的方向, 就可以运用标数法进行计算.如右图所示,小蜜蜂从A出发到B处共有89种不同的回家方法

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

12、则加 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个.为什么上面的规律是正确的呢?道理也很简单.设经过n次操作变为1的数的个数为an,则研1, a

13、2 1, a3 2,从上面的图看出, an 1比an大.一方面,每个经过n次操作变为1的数,乘以2,就得出一个偶数,经过 n 1次操作变为1; 反过来,每个经过n 1次操作变为1的偶数,除以2,就得出一个经过n次操作变为1的数.所以经过n次操作变为1的数与经过n 1次操作变为1的偶数恰好一样多.前者的个数是an, 因此后者也是an个.另一方面,每个经过 n次操作变为1的偶数,减去1,就得出一个奇数,它经过 n 1次操作 变为1,反过来.每个经过n 1次操作变为1的奇数,加上1,就得出一个偶数,它经过n次 操作变为1.所以经过n次操作变为1的偶数经过n 1次操作变为1的奇数恰好一样多.而由上面所

14、说,前者的个数就是 an 1 ,因此后者也是an 1.经过n 1次操作变为1的数,分为偶数、奇数两类,所以 an 1 an an 1 ,即上面所说的规 律的确成立.【答案】34【例11】 有20个石子,一个人分若干次取,每次可以取1个,2个或3个,但是每次取完之后不能留下质数个,有多少种方法取完石子?(石子之间不作区分,只考 虑石子个数)【考点】计数之递推法【难度】5星【题型】解答【解析】如果没有剩下的不能使质数这个条件,那么递推方法与前面学过的递推法相似,只不过每次都是前面 3个数相加.现在剩下的不能是质数个, 可以看作是质数个的取 法总数都是0,然后再进行递推.剩下的而子数20191S17

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

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

17、 3 3 3n 1 .an41 4 442 4 4 4 a(n 1)个 3由于甲是发球者,一次传球后球又回到甲手中的传球方法是不存在的,所以 a1 0.利用递推关系可以得到:a2 3 0 3 , a3 3 3 3 6 , a4 3 3 3 6 21 , a5 3 3 3 3 21 60.这说明经过5次传球后,球仍回到甲手中的传球方法有60种.本题也可以列表求解.由于第n次传球后,球不在甲手中的传球方法,第n 1次传球后球就可能回到甲手中,所以4次传球后,球仍回到只需求出第四次传球后,球不在甲手中的传法共有多少种.第号次传球传球的方法球在邛手中的传球方法球不在平手中的传球彷法1303293632

18、76214S131钝524360IS3从表中可以看出经过五次传球后,球仍回到甲手中的传球方法共有60种.【答案】60【巩固】五个人互相传球,由甲开始发球,并作为第一次传球,经过甲手中.问:共有多少种传球方式?【考点】计数之递推法【难度】5星【题型】解答【解析】递推法.设第n次传球后球传到甲的手中的方法有an种.由于每次传球有 4种选择,传n次有4n次可能.其中有的球在甲的手中,有的球不在甲的手中,球在甲 的手中的有 种,球不在甲的手中的,下一次传球都可以将球传到甲的手中,故 有an 1种.所以an an 14n.由于ai0,所以a241a14,a342a212,a443a352.即经过4次传球

19、后,球仍回到甲手中的传球方法有52种.【答案】52【例13】 设A、E为正八边形 ABCDEFGH的相对顶点,顶点A处有一只青蛙,除顶点E外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个,落到顶点E时青蛙就停止跳动,则青蛙从顶点A出发恰好跳10次后落到E的方法总数为种.【考点】计数之递推法【难度】5星【题型】填空【关键词】清华附中【解析】可以使用递推法.跳到D或F停在E回到A跳到B或H跳到C或G1步12步213步314步6425步1046步201487步34148步6848289步11648其中,第列的每个数都等于它的上一行的第二列的数的2倍,第二列的每一个数都等于它的上一行的第一列

20、和第三列的两个数的和,第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和,第四列的每一个数都等于它的上一行的第三列的数,第五列的每个数都等于都等于它的上一行的第四列的数的2倍.这一规律很容易根据青蛙的跳动规则分析得来.所以,青蛙第10步跳到E有48 2 96种方法.【答案】96【巩固】在正五边形 ABCDE上,一只青蛙从 A点开始跳动,它每次可以随意跳到相邻两个顶点中的一个上,一旦跳到D点上就停止跳动.青蛙在6次之内(含6次)跳到D点 有 种不同跳法.【考点】计数之递推法【难度】5星【题型】填空跳到E【解析】采用递推的方法.列表如下:跳到A 跳到B 跳到C1步112步 2113 步3

21、124步5325 步8356 步1385其中,根据规则,每次可以随意跳到相邻两个顶点中的一个上,一旦跳到D点上就停止跳动.所以,每一步跳到 A的跳法数等于上一步跳到 B和E的跳法数之和,每一步跳到 B的 跳法数等于上一步跳到 A和C的跳法数之和,每一步跳到 C的跳法数等于上一步跳到 B的 跳法数,每一步跳到 E的跳法数等于上一步跳到 A的跳法数,每一步跳到 D的跳法数等于 上一步跳到C或跳到E的跳法数.观察可知,上面的递推结果与前面的枚举也相吻合,所以青蛙在6次之内(含6次)跳到D点共有1 1 2 3 5 12种不同的跳法.【答案】12【例14】有6个木箱,编号为1,2, 3,,6,每个箱子有

22、一把钥匙,6把钥匙各不相同,每个箱子放进一把钥匙锁好.先挖开 1, 2号箱子,可以取出钥匙去开箱 子上的锁,如果最终能把6把锁都打开,则说这是一种放钥匙的“好”的方法,那么“好”的方法共有 种.【考点】计数之递推法【难度】5星 【题型】填空【关键词】迎春杯,中年级组,决赛【解析】(法1)分类讨论.如果1,2号箱中恰好放的就是 1, 2号箱的钥匙,显然不是“好” 的方法,所以“好”的方法有两种情况: (1)1, 2号箱的钥匙恰有1把在1, 2号箱中,另一箱装的是 36箱的钥匙.1, 2号箱的钥匙都不在1 , 2号箱中.对于,从1, 2号箱的钥匙中选1把,从36号箱的钥匙中选1把,共有2 4 8(

23、种)选 法,每一种选法放入 1, 2号箱各有2种放法,共有8 2 16(种)放法.不妨设1, 3号箱的钥匙放入了 1, 2号箱,此时3号箱不能装2号箱的钥匙,有3种选法, 依次类推,可知此日不同的放法有3 2 1 6(种).所以,第种情况有“好”的方法 16 6 96(种).对于,从36号箱的钥匙中选 2把放入1, 2号箱,有4 3 12(种)放法.不妨设3, 4 号箱的钥匙放入了 1, 2号箱.此时1, 2号箱的钥匙不可能都放在 3, 4号箱中,也就是说 3, 4号箱中至少有1把5, 6 号箱的钥匙.如果3, 4号箱中有2把5, 6号箱的钥匙,也就是说 3, 4号箱中放的恰好是 5, 6号箱

24、的钥 匙,那么1, 2号箱的钥匙放在5, 6号箱中,有2 2 4种放法;如果3, 4号箱中有1把5, 6号箱的钥匙,比如3, 4号箱中放的是5, 1号箱的钥匙,则只 能是5号箱放6号箱的钥匙,6号箱放2号箱的钥匙,有2 1 2种放法;同理,3, 4号箱放5, 2号箱或6, 1号箱或6, 2号箱的钥匙,也各有 2种放法.所以,第种情况有“好”的放法 124 2 2 2 2144(种).所以“好”的方法共有 96 144 240(种).(法2)递推法.设第1,2, 3,,6号箱子中所放的钥匙号码依次为 I, k2, k3,,k6,当 箱子数为n(n 2)时,好的放法的总数为 a-当 n 2 时,显然 a2 2( k1 1 , k2 2 或 k1 2 , k2 1).当n3时,显然k33,否则第3个箱子打不开,从而k13或k23,如果k13,则把1号箱子和3号箱子看作一个整体,这样还是锁着1, 2两号钥匙,撬开1, 2两号箱子,那么方法有a2种;当k2 3也是如此.于是n 2时的每一种情况对应 k1 3或k2 3时的一种情 况,这样就有a3 2a2 4 .当n 4时,也一定有kn n ,否则第n个箱子打不开,从而 k1、k2、 、 kn 1中有一个 为n,不论其中哪一个是 n,由于必须要把该箱子打开才能打开 n号

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论