奥数讲义计数：归纳与递推

华杯赛计数专题：归纳与递推

基础知识：

1.递推的基本思想：从简单情况出发寻找规律，逐步找到复杂问题的解法。

2.基本类型：上楼梯问题、直线分平面问题、传球法、圆周连线问题。

3.递推分析的常用思路：直接累加、增量分析、从复杂化归简单。

例题：

例L一个楼梯共有10级台阶，规定每步可以迈一级台阶或二级台阶.走完这10级台

阶，一共可以有多少种不同的走法？

【答案】89种

【解答】

设n级台阶有an种走法，则an=a„-i+a„-2

1级有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+13=21种

走法；8级有13+21=34种走法;9级有21+34=55种走法；10级有34+55=89种走法

例2.小悦买了10块巧克力，她每天最少吃一块，最多吃3块，直到吃完，共有多少

种吃法？

【答案】274种

【解答】通过枚举法和递推法：设n块糖有a“种走法，则a『ae+aea„7

1块糖有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.用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部

分……20条直线最多将平面分成1+2+3+……+20+1=211部分；

例5.甲、乙、丙三名同学练习传球，每人都可以把球传给另外两个人中的任意一个.

先由甲发球，经过6次传球后球仍然回到了甲的手中.请问：整个传球过程共有多少种不同

的可能？

【答案】89种

【解答】通过递推，可知0次传球到甲有1种；1次传球到甲有。种；2次传球到甲有

2种；3次传球到甲有2种；4次传球到甲有6种；5次传球到甲有10种；6次传球到甲有

22种。

例6.现有14块糖，如果阿奇每天吃奇数块糖，直到吃完，那么阿奇共有多少种吃

【答案】377种

【解答】当有1块糖时，有1种吃法；当有2块糖时，有1种吃法；当有3块糖时，

有2种吃法；当有4块糖时，最后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个

圆，最多可以分成几个部分？

【答案】（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部分时，有3义2=6种染色方法；当一个圆环被分成3部

分时，有3X2X1=6种染色方法；当一个圆环被分成4部分时，有3X2X2X2-6=24-

6=18种染色方法；当一个圆环被分成5部分时，有3X2X2X2X2—18=30种染色方法；

当一个圆环被分成6部分时，有3X2'—30=66种染色方法；当一个圆环被分成7部分时，

有3X2'—66=126种染色方法；当一个圆环被分成8部分时，有3X2,-126=258种染色方

法。

例9.圆周上有10个点Al,A2,……,A10,以这些点为端点连接5条线段，要求线段

之间没有公共点，共有多少种连接方式？

【答案】42种

【解答】当有2个点时，有1种连接方式；当有4个点时，有2种连接方式；当有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的方格表

时，有13+6=19种盖法；当是10X3的方格表时，有19+9=28种盖法.

例11.10条直线把平面最多分成多少部分？

【答案】56

【解答】用a.表示〃条直线最多分平面的区域数，

ai=2；a2=4；43=7...a向=；

因止匕，a.io=ag+10

=as+9+10

=a?+8+9+10

=ai+2+3+...+8+9+10

=2+2+3+...+8+9+10=56

所以，10条直线把平面最多分成56个部分。

例22.5个圆和1条直线最多把平面分成多少部分？

【答案】32

【解答】用a”表示〃个圆和1条直线最多把平面分成的区域数:

d/rl=a“+2(/?+1).

ai=4；

a2=&+4=4+4；

a：ka2+6=4+4+6；

a产@3+8

3.5~&4+10=4+4+6+8+10=32.

所以，5个圆和1条直线最多把平面分成32部分。

例13.10级台阶，每次可以迈广3级，那么有多少种迈法？

【答案】274

【解答】用a“表示〃级台阶的迈法数：

第一类：第一步迈1级台阶，有a源种迈法；

第二类：第一步迈2级台阶，有a,t种迈法；

第三类：第一步迈3级台阶，有a*种迈法；

+

所以，a,ra^i+a,r2a,rt（〃，4）.

ai=l；a2=2；