奥数讲义计数专题：归纳与递推.docx

《奥数讲义计数专题：归纳与递推.docx》由会员分享，可在线阅读，更多相关《奥数讲义计数专题：归纳与递推.docx（4页珍藏版）》请在第一文库网上搜索。

1、华杯赛计数专题：归纳与递推基础知识：1 .递推的基本思想：从简单情况出发寻找规律，逐步找到更杂问题的解法。2 .基本类型：上楼梯问题、直线分平面问题、传球法、圆周连线问题。3 .递推分析的常用思路：直接累加、增量分析、从复杂化归简单。例题：例1.一个楼梯共有10级台阶，规定每步可以迈一级台阶或二级台阶.走完这10级台阶，一共可以有多少种不同的走法？【答案】89种【解答】设n级台阶有a11种走法,则an=an-+a,1-21级有1种走法；2级有（1+1和2）2种走法；3级有（1+1+1、2+1和1+2）3种走法；4级有3+2=5种走法；5级有3+5=8种走法；6级有5+8=13种走法；7级有8+

2、13=21种走法；8级有13+21=34种走法；9级有21+34=55种走法；10级有34+55=89种走法例2.小悦买了10块巧克力，她每天最少吃一块，最多吃3块，直到吃完，共有多少种吃法？【答案】274种【解答】通过枚举法和递推法：设n块糖有小种走法，则an=an+a11-2*af1-31块糖有1种吃法；2块糖有2种吃法；3块糖有4种吃法；4块糖有1+2+4=7种吃法；5块糖有2+4+7=13种吃法；6块糖有4+7+13=24种吃法；7块糖有7+13+24=44种吃法；8块糖有13+24+44=81种吃法；9块糖有24+44+81=149种吃法；10块糖有44+81+149=274种吃法。

3、例3.用1X2的小方格覆盖2X7的长方形，共有多少种不同的覆盖方法？【答案】21种【解答】2X1的方格有1种盖法；2X2的方格有2种盖法；2X3的方格有2+1=3种盖法;2X4的方格有3+2=5种盖法；2X5的方格有3+5=8种盖法；2X6的方格有5+8=13种盖法；2X7的方格有8+13=21种盖法。例4.如果在一个平面上画出4条直线，最多可以把平面分成几个部分？如果画20条直线，最多可以分成几个部分？【答案】211个【解答】1条直线将平面分成1+1=2部分；2条直线最多将平面分成1+2+1=4部分；3条直线最多将平面分成1+2+3+1=7部分；4条直线最多将平面分成1+2+3+4+1=11

4、部分20条直线最多将平面分成1+2+3+20+1=211部分；例5.甲、乙、丙三名同学练习传球，每人都可以把球传给另外两个人中的任意一个.先由甲发球，经过6次传球后球仍然回到了甲的手中.请问：整个传球过程共有多少种不同的可能？【答案】89种【解答】通过递推，可知O次传球到甲有1种；1次传球到甲有O种；2次传球到甲有2种；3次传球到甲有2种；4次传球到甲有6种；5次传球到甲有10种；6次传球到甲有22种。例6.现有14块糖，如果阿奇每天吃奇数块糖，直到吃完，那么阿奇共有多少种吃【答案】377种【解答】当有1块糖时，有1种吃法；当有2块糖时，有1种吃法；当有3块糖时，有2种吃法；当有4块糖时，最后

5、1天吃1块有2种吃法，最后一天吃3块，有1种吃法，所以，共有2+1=3种吃法；当有5块糖时，有1+1+3=5种吃法；当有6块糖时，有1+2+5=8种吃法;当有7块糖时，有1+1+3+8=13种吃法;当有8块糖时,有1+2+5+13=21种吃法;当有9块糖时,有1+21+8+3+1=34种吃法；当有10块糖时，有21+34=55种吃法；当有11块糖时，有55+34=89种吃法；当有12块糖时，有55+89=144种吃法；当有13块糖时,有89+144=233种吃法；当有14块糖时，有233+144=377种吃法。例7.如果在一个平面上画出8条直线，最多可以把平面分成几个部分？如果画8个圆，最多可

6、以分成几个部分？【答案】(1)37部分；(2)58部分【解答】(1) 1+2+3+4+5+6+7+8+1=37;(2) 1个圆可将平面分成2部分；2个圆最多可将平面分成2+2=4部分；3个圆最多可将平面分成4+4=8部分；4个圆最多可将平面分成8+6=14部分；5个圆最多可将平面分成14+8=22部分；6个圆最多可将平面分成22+10=32部分；7个圆最多可将平面分成32+12=44部分；8个圆最多可将平面分成44+14=58部分；例8.如图所示，一个圆环被分成8部分，现将每一部分染上红、黄、蓝三种颜色之一，求相邻两部分颜色不同，共有多少种染色方法？【答案】258种【解答】当一个圆环被分成2部

7、分时，有3义2=6种染色方法；当一个圆环被分成3部分时，有3X2X1=6种染色方法；当一个圆环被分成4部分时，有3X2X2X26=246=18种染色方法；当一个圆环被分成5部分时，有3X2X2X2X2-18=30种染色方法；当一个圆环被分成6部分时，有3X25-30=66种染色方法；当一个圆环被分成7部分时，有3X2，66=126种染色方法；当一个圆环被分成8部分时，有3X27-126=258种染色方法。例9.圆周上有10个点A1A2,，A10,以这些点为端点连接5条线段，要求线段之间没有公共点，共有多少种连接方式？【答案】42种【解答】当有2个点时，有1种连接方式；当有4个点时，有2种连接方

8、式；当有6个点时，有2+1+2=5种连接方式；当有8个点时，有5+2X1+2X1+5=14种连接方式；当有10个点时，有14X2+1X5X2+2X2=42种连接方式；例10.用10个1X3的长方形纸片覆盖一个10X3的方格表，共有多少种覆盖方法？【答案】89种【解答】当是1X3的方格表时，有1种盖法；当是2X3的方格表时，有1种盖法；当是3X3的方格表时，有2种盖法；当是4X3的方格表时，有2+1=3种盖法；当是5X3的方格表时，有3+1=4种盖法；当是6X3的方格表时，有4+2=6种盖法；当是7X3的方格表时，有6+3=9种盖法；当是8X3的方格表时，有9+4=13种盖法；当是9X3的方格表

9、时，有13+6=19种盖法；当是10X3的方格表时，有19+9=28种盖法.例I11O条直线把平面最多分成多少部分？【答案】56【解答】用a”表示条直线最多分平面的区域数，a=2;a2=4；包=7af1ti=an+1；因J,3o=ag+10=a+9+10=a?+8+9+10=a1+2+3+8+9+10=2+2+3+8+9+10=56所以，10条直线把平面最多分成56个部分。例22.5个圆和1条直线最多把平面分成多少部分？【答案】32【解答】用a表示个圆和1条直线最多把平面分成的区域数:a.1=ap+2(1).ai=4；a2=a+4=4+4;a3=a+6=4+4+6；at=a+8as=a1+10

10、=4+4+6+8+10=32.所以，5个圆和1条直线最多把平面分成32部分。例13.10级台阶，每次可以迈广3级，那么有多少种迈法？【答案】274【解答】用表示级台阶的迈法数：第一类：第一步迈1级台阶，有azr种迈法；第二类：第一步迈2级台阶，有a0种迈法；第三类：第一步迈3级台阶，有ax种迈法；所以，apa,r+ar2+azr3(24).ai=1；32=2；as=4;a-i=7;a=13;u=24;a7=44；a=81；的=149；aw=274所以，有274种迈法。例14.如果用1果用的长方形沿网状格线，不重叠地盖满图中的图形，那么共有多少种不同的盖法？【答案】15【解答】用a”表示层的盖法数。通过分析，我们得出：azi=1+1+a=2+aa=3;a=5a=150所以,共有15种不同的盖法。