【教培专用】五年级下册春季数学奥数培优讲义-第09讲 递推计数 全国通用（学生版+教师版） (2份打包)

第9讲 递推计数 知识点 1、 递推计数（五下） 1、递推计数    用于解决复杂的计数问题，通过考虑问题的简单情况，看看简单情形如何处理，在解决了简单情形后，再考虑如何利用简单情形的结论来解决更复杂的问题．这个由简单到复杂的推导过程就叫“递推”。 2、递推计数的分类    （1）利用数列中各项的简单累加来解决的递推计数问题（如上楼梯、覆盖问题）．    （2）依靠增量分析，写出递推数列来解决的递推计数问题（如直线分平面问题）．    （3）利用数表中各项的简单累加来解决的递推计数问题（如传球法）．    （4）不以简单累加形式进行的递推问题（如圆周连线问题），此类问题必须重视如何将复杂情形化归为简单情形来解决，利用简单情形下已有的结论来推算复杂情形． 3、染色问题[来源:学科网ZXXK]    （1）能对于染色问题，只要能保证前面步骤的染色结果不会影响到后面步骤染色的方法数，就是合理的分步方法．    （1）对于较复杂的染色问题等较复杂的乘法原理问题，在分步时要优先考虑可选择情况较少的步骤，必须让前面步骤的结果不影响后面步骤选择的方法数． 课堂例题 1、 上楼梯及分平面问题 1、老师给小高布置了12篇作文，规定他每天至少写1篇．如果小高每天最多能写2篇，那么共有多少种不同的完成方法？（小高每天只能写完整数篇） 【答案】 233 【解析】 假设有1篇作文，则有1种方法；有2篇作文，则有种方法；有3篇作文，则有种方法；有4篇作文，则有种方法；有5篇作文，则有种方法……有12篇作文，则有种方法． 作文数 1 2 3 4 5 6 7 8 9 10 11 12 方法数 1 2 3 5 8 13 21 34 55 89 144 233 2、老师给小高布置了12篇作文，规定他每天至少写1篇．如果小高每天最多能写3篇，那么共有多少种写完作文的方法？ 【答案】 927种 【解析】 将作文数量与完成作文的方法数列成一张表格，如下所示： 作文数 1 2 3 4 5 6 7 8 9 10 11 12 完成方法数 1 2 4 7 13 24 44 81 149 274 504 927 下面解释一下这张数表是如何累加得到的．写1、2、3篇作文的方法数可以枚举得到．写4篇作文的完成方法数可以分三类去数：如果第一天写1篇，那么参考数表可得，剩下3篇有4种完成方法；如果第一天写2篇，同样参考数表可得，剩下2篇有2种完成方法；如果第一天写3篇，那么剩下1篇还有1种完成方法——因此4篇作文的完成方法总数为，如上表箭头所示．接着分析5篇作文的完成方法数，仍然分三类：第一天写1篇，那么参考数表可得，剩下4篇还有7种完成方法；第一天写2篇，那么剩下3篇还有4种完成方法；第一天写3篇，那么剩下2篇还有2种完成方法——因此5篇作文的完成方法数等于……以此类推便可填满整张表格． 3、用10个的长方形纸片覆盖一个的方格表，共有多少种覆盖方法？ 【答案】 28种 【解析】 我们可以列出一个递推数表，将其表示如下： 方格表大小 覆盖方法数 1 1 2 3 4 6 9 13 19 28 下面详细说明该问题的递推规律．覆盖、和方格表的方法数可以枚举得到．接着分析覆盖的表格有几种覆盖方法．如下图所示，左上角的阴影方格在覆盖的时候有两种方法：竖着覆盖或横着覆盖．当竖着覆盖时，余下部分恰好是一个的方格表，覆盖方法数为2；当横着覆盖时，其下方的方格只能被横放的纸片盖住，因此只剩下一个的方格表需要覆盖，方法数为1．由此可得表格的方法数为．用同样的方法分析的[来源:学。科。网Z。X。X。K] [来源:Zxxk.Com] 余下部分是的方格表，覆盖方法有2种． 阴影方格下方的格子只能用横放的纸片盖住，因此只剩下的方格表需要覆盖． 方格表，可得其覆盖方法数等于的方法数加上的方法数，因此等于．接着以此类推即可． 4、在一个平面上画出100条直线，最多可以把平面分成几个部分？ 【答案】 5051 【解析】 1条直线，把平面分成部分；2条直线，直线间增加1个交点，把平面分成部分；3条直线，直线间增加2个交点，把平面分成部分；4条直线，直线间增加3个交点，把平面分成部分……100条直线，直线间增加99个交点，把平面分成部分． 直线数 1 2 3 4 5 6 …… 100 增加交点 0 1 2 3 4 5 99 分成部分 2 4 7 11 16 22 5051 5、在一个平面上画出10个圆，最多可以把平面分成多少部分？ 【答案】 92[来源:学科网ZXXK] 【解析】 一个圆最多能把平面分成2个部分； 2个圆最多能把平面分成个部分； 3个圆最多能把平面分成个部分； 现在加入第4个圆，为了使分成的部分最多，第4个圆必须与前面3个圆都有两个交点，因此得6个交点将第4个圆的圆周分成6段圆弧，而每一段圆弧将原来