華杯賽計(jì)數(shù)專題：歸納與遞推基礎(chǔ)知識(shí)：

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

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

3.遞推分析的常用思路：直接累加、增量分析、從復(fù)雜化歸簡單。例題：例1.一個(gè)樓梯共有10級(jí)臺(tái)階，規(guī)定每步可以邁一級(jí)臺(tái)階或二級(jí)臺(tái)階.走完這10級(jí)臺(tái)階，一共可以有多少種不同的走法？【答案】89種

【解答】

設(shè)n級(jí)臺(tái)階有an種走法，則an=an-1+an-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種

【解答】通過枚舉法和遞推法：設(shè)n塊糖有an種走法，則an=an-1+an-2+an-3

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.用1×2的小方格覆蓋2×7的長方形，共有多少種不同的覆蓋方法？【答案】21種

【解答】2×1的方格有1種蓋法；2×2的方格有2種蓋法；2×3的方格有2+1=3種蓋法；

2×4的方格有3+2=5種蓋法；2×5的方格有3+5=8種蓋法；2×6的方格有5+8=13種蓋法；

2×7的方格有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)過6次傳球后球仍然回到了甲的手中.請問：整個(gè)傳球過程共有多少種不同的可能？【答案】89種

【解答】通過遞推，可知0次傳球到甲有1種；1次傳球到甲有0種；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í)，有3×2×1=6種染色方法；當(dāng)一個(gè)圓環(huán)被分成4部分時(shí)，有3×2×2×2－6=24－6=18種染色方法；當(dāng)一個(gè)圓環(huán)被分成5部分時(shí)，有3×2×2×2×2－18=30種染色方法；當(dāng)一個(gè)圓環(huán)被分成6部分時(shí)，有3×25－30=66種染色方法；當(dāng)一個(gè)圓環(huán)被分成7部分時(shí)，有3×26－66=126種染色方法；當(dāng)一個(gè)圓環(huán)被分成8部分時(shí)，有3×27－126=258種染色方法。

例9.圓周上有10個(gè)點(diǎn)A1，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+2×1+2×1+5=14種連接方式；當(dāng)有10個(gè)點(diǎn)時(shí)，有14×2+1×5×2+2×2=42種連接方式；

例10.用10個(gè)1×3的長方形紙片覆蓋一個(gè)10×3的方格表，共有多少種覆蓋方法？【答案】89種

【解答】當(dāng)是1×3的方格表時(shí)，有1種蓋法；當(dāng)是2×3的方格表時(shí)，有1種蓋法；當(dāng)是3×3的方格表時(shí)，有2種蓋法；當(dāng)是4×3的方格表時(shí)，有2+1=3種蓋法；當(dāng)是5×3的方格表時(shí)，有3+1=4種蓋法；當(dāng)是6×3的方格表時(shí)，有4+2=6種蓋法；當(dāng)是7×3的方格表時(shí)，有6+3=9種蓋法；當(dāng)是8×3的方格表時(shí)，有9+4=13種蓋法；當(dāng)是9×3的方格表時(shí)，有13+6=19種蓋法；當(dāng)是10×3的方格表時(shí)，有19+9=28種蓋法.例11.10條直線把平面最多分成多少部分？【答案】56

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

a1=2；a2=4；a3=7……an+1=an+n+1；

因此，a10=a9+10

=a8+9+10

=a7+8+9+10

=……

=a1+2+3+……+8+9+10

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

所以，10條直線把平面最多分成56個(gè)部分。

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

【解答】用an表示n個(gè)圓和1條直線最多把平面分成的區(qū)域數(shù):

an+1=an+2（n+1）.

a1=4；

a2=a1+4=4+4；

a3=a2+6=4+4+6；

a4=a3+8

a5=a4+10=4+4+6+8+10=32.

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

例13.10級(jí)臺(tái)階，每次可以邁1~3級(jí)，那么有多少種邁法？【答案】274

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

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

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

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

所以，an=an-1+an-2+an-3（n≥4）.

a1=1；a2=2；a3=4；a4=7；a5=13；a6=24；a7=44；

a8=81；a9=1