奧數(shù)講義計數(shù)：歸納與遞推

華杯賽計數(shù)專題：歸納與遞推

基礎(chǔ)知識：

1.遞推的基本思想：從簡單情況出發(fā)尋找規(guī)律，逐步找到復(fù)雜問題的解法。

2.基本類型：上樓梯問題、直線分平面問題、傳球法、圓周連線問題。

3.遞推分析的常用思路：直接累加、增量分析、從復(fù)雜化歸簡單。

例題：

例L一個樓梯共有10級臺階，規(guī)定每步可以邁一級臺階或二級臺階.走完這10級臺

階，一共可以有多少種不同的走法？

【答案】89種

【解答】

設(shè)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種

【解答】通過枚舉法和遞推法：設(shè)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.甲、乙、丙三名同學(xué)練習(xí)傳球，每人都可以把球傳給另外兩個人中的任意一個.

先由甲發(fā)球，經(jīng)過6次傳球后球仍然回到了甲的手中.請問：整個傳球過程共有多少種不同

的可能？

【答案】89種

【解答】通過遞推，可知0次傳球到甲有1種；1次傳球到甲有。種；2次傳球到甲有

2種；3次傳球到甲有2種；4次傳球到甲有6種；5次傳球到甲有10種；6次傳球到甲有

22種。

例6.現(xiàn)有14塊糖，如果阿奇每天吃奇數(shù)塊糖，直到吃完，那么阿奇共有多少種吃

【答案】377種

【解答】當(dāng)有1塊糖時，有1種吃法；當(dāng)有2塊糖時，有1種吃法；當(dāng)有3塊糖時，

有2種吃法；當(dāng)有4塊糖時，最后1天吃1塊有2種吃法，最后一天吃3塊，有1種吃

法，所以，共有2+1=3種吃法；當(dāng)有5塊糖時，有1+1+3=5種吃法；當(dāng)有6塊糖時，有

1+2+5=8種吃法;當(dāng)有7塊糖時，有1+1+3+8=13種吃法;當(dāng)有8塊糖時,有1+2+5+13=21

種吃法；當(dāng)有9塊糖時，有1+21+8+3+1=34種吃法；當(dāng)有10塊糖時，有21+34=55種吃

法；當(dāng)有11塊糖時，有55+34=89種吃法；當(dāng)有12塊糖時，有55+89=144種吃法；當(dāng)有

13塊糖時,有89+144=233種吃法；當(dāng)有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.如圖所示，一個圓環(huán)被分成8部分，現(xiàn)將每一部分染上紅、黃、藍(lán)三種顏色之

一，求相鄰兩部分顏色不同，共有多少種染色方法？

【答案】258種

【解答】當(dāng)一個圓環(huán)被分成2部分時，有3義2=6種染色方法；當(dāng)一個圓環(huán)被分成3部

分時，有3X2X1=6種染色方法；當(dāng)一個圓環(huán)被分成4部分時，有3X2X2X2-6=24-

6=18種染色方法；當(dāng)一個圓環(huán)被分成5部分時，有3X2X2X2X2—18=30種染色方法；

當(dāng)一個圓環(huán)被分成6部分時，有3X2'—30=66種染色方法；當(dāng)一個圓環(huán)被分成7部分時，

有3X2'—66=126種染色方法；當(dāng)一個圓環(huán)被分成8部分時，有3X2,-126=258種染色方

法。

例9.圓周上有10個點(diǎn)Al,A2,……,A10,以這些點(diǎn)為端點(diǎn)連接5條線段，要求線段

之間沒有公共點(diǎn)，共有多少種連接方式？

【答案】42種

【解答】當(dāng)有2個點(diǎn)時，有1種連接方式；當(dāng)有4個點(diǎn)時，有2種連接方式；當(dāng)有6

個點(diǎn)時，有2+1+2=5種連接方式；當(dāng)有8個點(diǎn)時，有5+2X1+2X1+5=14種連接方式；當(dāng)有

10個點(diǎn)時，有14X2+1X5X2+2X2=42種連接方式；

例10.用10個1X3的長方形紙片覆蓋一個10X3的方格表，共有多少種覆蓋方法？

【答案】89種

【解答】當(dāng)是1X3的方格表時，有1種蓋法；當(dāng)是2X3的方格表時，有1種蓋法；

當(dāng)是3X3的方格表時，有2種蓋法；當(dāng)是4X3的方格表時，有2+1=3種蓋法；當(dāng)是5X3

的方格表時，有3+1=4種蓋法；當(dāng)是6X3的方格表時，有4+2=6種蓋法；當(dāng)是7X3的方

格表時，有6+3=9種蓋法；當(dāng)是8X3的方格表時，有9+4=13種蓋法；當(dāng)是9X3的方格表

時，有13+6=19種蓋法；當(dāng)是10X3的方格表時，有19+9=28種蓋法.

例11.10條直線把平面最多分成多少部分？

【答案】56

【解答】用a.表示〃條直線最多分平面的區(qū)域數(shù)，

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條直線最多把平面分成的區(qū)域數(shù):

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

ai=4；

a2=&+4=4+4；

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

a產(chǎn)@3+8

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

所以，5個圓和1條直線最多把平面分成32部分。

例13.10級臺階，每次可以邁廣3級，那么有多少種邁法？

【答案】274

【解答】用a“表示〃級臺階的邁法數(shù)：

第一類：第一步邁1級臺階，有a源種邁法；

第二類：第一步邁2級臺階，有a,t種邁法；

第三類：第一步邁3級臺階，有a*種邁法；

+

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

ai=l；a2=2；