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

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

基礎(chǔ)知識(shí)：

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

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

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

例題：

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

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

【答案】89種

【解答】

設(shè)n級(jí)臺(tái)階有an種走法，則an=a?-i+a?-2

1級(jí)有1種走法；2級(jí)有（1+1和2）2種走法；3級(jí)有（1+1+1、2+1和1+2）3種走

法；4級(jí)有3+2=5種走法；5級(jí)有3+5=8種走法；6級(jí)有5+8=13種走法；7級(jí)有8+13=21種

走法；8級(jí)有13+21=34種走法;9級(jí)有21+34=55種走法；10級(jí)有34+55=89種走法

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

種吃法？

【答案】274種

【解答】通過(guò)枚舉法和遞推法：設(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的長(zhǎng)方形，共有多少種不同的覆蓋方法？

【答案】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.如果在一個(gè)平面上畫出4條直線，最多可以把平面分成幾個(gè)部分？如果畫20條

直線，最多可以分成幾個(gè)部分？

【答案】211個(gè)

【解答】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í)傳球，每人都可以把球傳給另外兩個(gè)人中的任意一個(gè).

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

的可能？

【答案】89種

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

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

22種。

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

【答案】377種

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

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

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

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

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

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

13塊糖時(shí),有89+144=233種吃法；當(dāng)有14塊糖時(shí)，有233+144=377種吃法。

例7.如果在一個(gè)平面上畫出8條直線，最多可以把平面分成幾個(gè)部分？如果畫8個(gè)

圓，最多可以分成幾個(gè)部分？

【答案】（1）37部分；（2）58部分

【解答】

（1）1+2+3+4+5+6+7+8+1=37;

（2）1個(gè)圓可將平面分成2部分；2個(gè)圓最多可將平面分成2+2=4部分；3個(gè)圓最多

可將平面分成4+4=8部分；4個(gè)圓最多可將平面分成8+6=14部分；5個(gè)圓最多可將平面分

成14+8=22部分；6個(gè)圓最多可將平面分成22+10=32部分；7個(gè)圓最多可將平面分成

32+12=44部分；8個(gè)圓最多可將平面分成44+14=58部分；

例8.如圖所示，一個(gè)圓環(huán)被分成8部分，現(xiàn)將每一部分染上紅、黃、藍(lán)三種顏色之

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

【答案】258種

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

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

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

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

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

法。

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

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

【答案】42種

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

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

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

例10.用10個(gè)1X3的長(zhǎng)方形紙片覆蓋一個(gè)10X3的方格表，共有多少種覆蓋方法？

【答案】89種

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

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

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

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

時(shí)，有13+6=19種蓋法；當(dāng)是10X3的方格表時(shí)，有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個(gè)部分。

例22.5個(gè)圓和1條直線最多把平面分成多少部分？

【答案】32

【解答】用a”表示〃個(gè)圓和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個(gè)圓和1條直線最多把平面分成32部分。

例13.10級(jí)臺(tái)階，每次可以邁廣3級(jí)，那么有多少種邁法？

【答案】274

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

第一類：第一步邁1級(jí)臺(tái)階，有a源種邁法；

第二類：第一步邁2級(jí)臺(tái)階，有a,t種邁法；

第三類：第一步邁3級(jí)臺(tái)階，有a*種邁法；

+

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

ai=l；a2=2；