7-6-4 計數(shù)之遞推法.教師版

1、764.計數(shù)之遞推法.題庫教師版page1of9764.764.計數(shù)之遞推法計數(shù)之遞推法教學目標教學目標前面在講加法原理、乘法原理、排列組合時已經穿插講解了計數(shù)中的一些常用的方法，比如枚舉法、樹形圖法、標數(shù)法、捆綁法、排除法、插板法等等，這里再集中學習一下計數(shù)中其他常見的方法，主要有歸納法、整體法、對應法、遞推法對這些計數(shù)方法與技巧要做到靈活運用例題精講例題精講對于某些難以發(fā)現(xiàn)其一般情形的計數(shù)問題，可以找出其相鄰數(shù)之間的遞歸關系，有了這

2、一遞歸關系就可以利用前面的數(shù)求出后面未知的數(shù)，這種方法稱為遞推法【例1】每對小兔子在出生后一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來如果一個人每對小兔子在出生后一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來如果一個人在一月份買了一對小兔子，那么十二月份的時候他共有多少對兔子？在一月份買了一對小兔子，那么十二月份的時候他共有多少對兔子？【考點】計數(shù)之遞推法【難度】3星【題型】解答【【解析解析解析】】第一個月，有1對

3、小兔子；第二個月，長成大兔子，所以還是1對；第三個月，大兔子生下一對小兔子，所以共有2對；第四個月，剛生下的小兔子長成大兔子，而原來的大兔子又生下一對小兔子，共有3對；第五個月，兩對大兔子生下2對小兔子，共有5對；……這個特點的說明每月的大兔子數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，即上上月的兔子數(shù)，所以每月的兔子數(shù)為上月的兔子數(shù)與上上月的兔子數(shù)相加依次類推可以列出下表：經過月數(shù)：123456789101112兔子對數(shù)：112

4、3581321345589—144，所以十二月份的時候總共有144對兔子【答案】144【例2】樹木生長的過程中，新生的枝條往往需要一段樹木生長的過程中，新生的枝條往往需要一段“休息休息”時間供自身生長，而后才能萌發(fā)新枝一棵樹時間供自身生長，而后才能萌發(fā)新枝一棵樹苗在一年后長出一條新枝，第二年新枝苗在一年后長出一條新枝，第二年新枝“休息休息”，老枝依舊萌發(fā)新枝；此后，老枝與，老枝依舊萌發(fā)新枝；此后，老枝與“休息休息”過一年的過一年的枝同時

5、萌發(fā)，當年生的新枝則依次枝同時萌發(fā)，當年生的新枝則依次“休息休息”這在生物學上稱為這在生物學上稱為“魯?shù)戮S格定律魯?shù)戮S格定律”那么十年后這棵樹那么十年后這棵樹上有多少條樹枝？上有多少條樹枝？【考點】計數(shù)之遞推法【難度】3星【題型】解答【【解析解析解析】】一株樹木各個年份的枝椏數(shù)，構成斐波那契數(shù)列：1，2，3，5，8，13，21，34，55，89，……所以十年后樹上有89條樹枝【答案】89【例3】一樓梯共一樓梯共10級，規(guī)定每步只能跨上一

6、級或兩級，要登上第級，規(guī)定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法？級，共有多少種不同走法？【考點】計數(shù)之遞推法【難度】4星【題型】解答764.計數(shù)之遞推法.題庫教師版page3of9【答案】89【例5】用的小長方形覆蓋的小長方形覆蓋的方格網，共有多少種不同的蓋法？的方格網，共有多少種不同的蓋法？13?38?【考點】計數(shù)之遞推法【難度】5星【題型】解答【解析】如果用的長方形蓋的長方形，設種數(shù)為則，對于，左邊可能13?3

7、n?na11a?21a?32a?4n?豎放1個的，也可能橫放3個的，前者有種，后者有種，所以依照13?13?1na3na13nnnaaa??這條遞推公式列表：31?32?33?34?35?36?37?38?112346913所以用的小長方形形覆蓋的方格網，共有13種不同的蓋法13?38?【答案】13【例6】有一堆火柴共有一堆火柴共12根，如果規(guī)定每次取根，如果規(guī)定每次取1～3根，那么取完這堆火柴共有多少種不同取法？根，那么取完這堆火柴共

8、有多少種不同取法？【考點】計數(shù)之遞推法【難度】4星【題型】解答【解析】取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種數(shù)等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完這堆火柴一共有927種方法【答案】927【鞏固鞏固】一堆蘋果共有一堆蘋果共有8個，如果規(guī)定每次取個，如果規(guī)定每次取1

9、～3個，那么取完這堆蘋果共有多少種不同取法？個，那么取完這堆蘋果共有多少種不同取法？【考點】計數(shù)之遞推法【難度】4星【題型】解答【解析】取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以后取任意個蘋果的種數(shù)等于取到前三個蘋果所有情況之和，以此類推，參照上題列表如下：1個2個3個4個5個6個7個8個124713244481取完這堆蘋果一共有81種方法【答案】81【例7】有10枚棋子，每次拿出枚棋子，每次拿出2枚或枚或3枚

10、，要想將枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？枚棋子全部拿完，共有多少種不同的拿法？【考點】計數(shù)之遞推法【難度】4星【題型】解答【【解析解析解析】】本題可以采用遞推法，也可以進行分類討論，當然也可以直接進行枚舉(法1)遞推法假設有枚棋子，每次拿出2枚或3枚，將枚棋子全部拿完的拿法總數(shù)為種nnna則，，21a?31a?41a?由于每次拿出2枚或3枚，所以()32nnnaaa????5n?所以，；；；；；5232aaa???6