小學奧數計數之遞推法精選練習例題含答案解析附知識點撥及考點

1、7-6-4,計數之遞推法目鄧加教學目標前面在講加法原理、乘法原理、排列組合時已經穿插講解了計數中的一些常用的方法，比如枚舉法、樹形圖法、標數法、捆綁法、排除法、插板法等等，這里再集中學習一下計數中其他常見的方法，主要有歸納法、整體法、對應法、遞推法.對這些計數方法與技巧要做到靈活運用.例題精講對于某些難以發(fā)現其一般情形的計數問題，可以找出其相鄰數之間的遞歸關系，有了這一遞歸關系就可以利用前面的數求出后面未知的數，這種方法稱為遞推法.【例1】每對小兔子在出生后一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來.如果一個人在一月份買了一對小兔子，那么十二月份的時候他共有多少對兔子？【考點】計

2、數之遞推法【難度】3星【題型】解答【解析】第一個月，有1對小兔子；第二個月，長成大兔子，所以還是1對；第三個月，大兔子生下一對小兔子，所以共有2對；第四個月，剛生下的小兔子長成大兔子，而原來的大兔子又生下一對小兔子，共有3對；第五個月，兩對大兔子生下2對小兔子，共有5對；這個特點的說明每月的大兔子數為上月的兔子數，每月的小兔子數為上月的大兔子數，即上上月的兔子數，所以每月的兔子數為上月的兔子數與上上月的兔子數相加.依次類推可以列出下表：經過月數：123456789101112兔子對數：-1-1-2-3-5-8-13-21-34-55-89144,所以十二月份的時候總共有144對兔子.【答案】1

3、44例2樹木生長的過程中，新生的枝條往往需要一段休息”時間供自身生長，而后才能萌發(fā)新枝.一棵樹苗在一年后長出一條新枝，第二年新枝休息”，老枝依舊萌發(fā)新枝；此后，老枝與休息”過一年的枝同時萌發(fā)，當年生的新枝則依次休息”.這在生物學上稱為魯德維格定律”.那么十年后這棵樹上有多少條樹枝？【考點】計數之遞推法【難度】3星【題型】解答【解析】一株樹木各個年份的枝梗數，構成斐波那契數列：1,2,3,5,8,13,21,34,55,89,所以十年后樹上有89條樹枝.【答案】89例3一樓梯共10級，規(guī)定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法？【考點】計數之遞推法【難度】4星【題型】解答A*

4、【解析】登1級2級3級4級.10級1種方法2種3種5種.?我們觀察每級的種數，發(fā)現這么一個規(guī)律：從第三個數開始，每個數是前面兩個數的和；依此規(guī)律我們就可以知道了第10級的種數是89.其實這也是加法的運用：假如我們把這個人開始登樓梯的位置看做Ao,那么登了1級的位置是在A1,2級在A2.A10級就在A10.到A3的前一步有兩個位置；分別是A2和A1.在這里要強調一點，那么A2到A3既然是一步到了，那么A2、A3之間就是一種選擇了；同理A1到A3也是一種選擇了.同時我們假設到n級的選擇數就是An.那么從A。到A3就可以分成兩類了：第一類：A0-A1-A3,那么就可以分成兩步.有A1M種，也就是A1

5、種；（A1-A3是一種選擇）第二類：A0-A2-A3,同樣道理有A2.類類相加原理：A3=A1+A2,依次類推An=An-1+An-2.【答案】89【鞏固】一樓梯共10級，規(guī)定每步只能跨上一級或三級，要登上第10級，共有多少種不同走法？【考點】計數之遞推法【難度】4星【題型】解答AlM【解析】登1級2級3級4級5級10級1種方法1種2種3種4種.?我們觀察每級的種數，發(fā)現這么一個規(guī)律：從第三個數開始，每個數是前面相隔的兩個數的和；依此規(guī)律我們就可以知道了第10級的種數是28.【答案】28例41X2的小長方形（橫的豎白都行）覆蓋2X10的方格網，共有多少種不同的蓋法.【考點】計數之遞推法【難度】

6、4星【題型】解答【解析】如果用1父2的長方形蓋2。的長方形，設種數為an,則a1=1,a2=2,對于n至3,左邊可能豎放1個1父2的，也可能橫放2個1父2的，前者有an-1種，后者有an-2種，所以an=an-1+an-2,所以根據遞推，覆蓋2M10的長方形一共有89種.【答案】89例5用1父3的小長方形覆蓋3父8的方格網，共有多少種不同的蓋法？【考點】計數之遞推法【難度】5星【題型】解答【解析】如果用1父3的長方形蓋3叼的長方形，設種數為%,則q=1,a2=1,a3=2，對于n±4,左邊可能豎放1個1父3的，也可能橫放3個1父3的，前者有an-1種，后者有an一3種，所以an=an

7、.I+an一3,依照這條遞推公式列表：3x13x23x33x43x53x63x73x8112346913所以用1父3的小長方形形覆蓋3M8的方格網，共有13種不同的蓋法.【答案】13例6有一堆火柴共12根，如果規(guī)定每次取13根，那么取完這堆火柴共有多少種不同取法？【考點】計數之遞推法【難度】4星【題型】解答【解析】取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種數等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完這堆火柴一共有927種方法.【

8、答案】927【鞏固】一堆蘋果共有8個，如果規(guī)定每次取13個，那么取完這堆蘋果共有多少種不同取法？【考點】計數之遞推法【難度】4星【題型】解答【解析】取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以后取任意個蘋果的種數等于取到前三個蘋果所有情況之和，以此類推，參照上題列表如下：1個2個3個4個5個6個7個8個124713244481取完這堆蘋果一共有81種方法.【答案】81【例7】有10枚棋子，每次拿出2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？【考點】計數之遞推法【難度】4星【題型】解答【解析】本題可以采用遞推法，也可以進行分類討論，當然也可以直接進行枚舉.

9、（法1）遞推法.假設有n枚棋子，每次拿出2枚或3枚，將n枚棋子全部拿完的拿法總數為an種.貝Ua2=1,a3=1,a4=1.由于每次拿出2枚或3枚，所以an=an4+an“（n之5）.所以，a5=a2+a3=2%=a3+a42a7=a4+a5=3；a8=a5+a6=4；a9=%+a75；a10=a7+a8=7.即當有10枚棋子時，共有7種不同的拿法.（法2）分類討論.由于棋子總數為10枚，是個偶數，而每次拿2枚或3枚，所以其中拿3枚的次數也應該是偶數.由于拿3枚的次數不超過3次，所以只能為0次或2次.若為0次，則相當于2枚拿了5次，此時有1種拿法；若為2次，則2枚也拿了2次，共拿了4次，所以此

10、時有C：=6種拿法.根據加法原理，共有1+6=7種不同的拿法.【答案】7例8如下圖，一只蜜蜂從A處出發(fā)，回到家里B處，每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆行，共有多少種回家的方法？【考點】計數之遞推法【難度】4星【題型】【解析】蜜蜂每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆行”這意味著它只能從小號碼的蜂房爬近相鄰大號碼的蜂房.明確了行走路徑的方向，就可以運用標數法進行計算.如右圖所示，小蜜蜂從A出發(fā)到B處共有89種不同的回家方法.【答案】89A房間到達B房間有多少種【鞏固】小蜜蜂通過蜂巢房間，規(guī)定只能由小號房間進入大號房間問小蜜蜂由方法？【考點】計數之遞推法【難度】4星【題型】解答【

11、解析】斐波那契數列第八項.21種.【答案】21例9如下圖，一只蜜蜂從A處出發(fā),行，共有多少種回家的方法？回到家里B處，每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆【解析】按照蜜蜂只能從小號碼的蜂房爬近相鄰大號碼的蜂房的原則，運用標號法進行計算.如右圖所示，小蜜蜂從A出發(fā)到B處共有296種不同的回家方法.【答案】296【例10】對一個自然數作如下操作：如果是偶數則除以2,如果是奇數則加1,如此進行直到得數為1操作停止.問經過9次操作變?yōu)?的數有多少個？【考點】計數之遞推法【難度】4星【題型】解答【解析】可以先嘗試一下，倒推得出下面的圖:510其中經1次操作變?yōu)?的1個，即2,經2次操作變?yōu)?的1

12、個，即4,經3次操作變?yōu)?的2個，是一奇一偶，以后發(fā)現，每個偶數可以變成兩個數，分別是一奇一偶，每個奇數變?yōu)橐粋€偶數，于是，經1、2、次操作變?yōu)?的數的個數依次為：1,1,2,3,5,8,這一串數中有個特點：自第三個開始，每一個等于前兩個的和，即即經過9次操作變?yōu)?的數有34個.為什么上面的規(guī)律是正確的呢？道理也很簡單.設經過n次操作變?yōu)?的數的個數為an,a1=1,a2=1,83=2,從上面的圖看出，an書比an大.一方面，每個經過n次操作變?yōu)?的數，乘以2,就得出一個偶數，經過n+1次操作變?yōu)?;反過來，每個經過n+1次操作變?yōu)?的偶數，除以2,就得出一個經過n次操作變?yōu)?的數.所以經過n

13、次操作變?yōu)?的數與經過n+1次操作變?yōu)?的偶數恰好一樣多.前者的個數是為，因此后者也是an個.另一方面，每個經過n次操作變?yōu)?的偶數，減去1,就得出一個奇數，它經過n+1次操作變?yōu)?,反過來.每個經過n+1次操作變?yōu)?的奇數，加上1,就得出一個偶數，它經過n次操作變?yōu)?.所以經過n次操作變?yōu)?的偶數經過n+1次操作變?yōu)?的奇數恰好一樣多.而由上面所說，前者的個數就是%,因此后者也是%.經過n+1次操作變?yōu)?的數，分為偶數、奇數兩類，所以an=an+an，即上面所說的規(guī)律的確成立.【答案】34【例11】有20個石子，一個人分若干次取，每次可以取1個，2個或3個，但是每次取完之后不能留下質數個，有

14、多少種方法取完石子？（石子之間不作區(qū)分，只考慮石子個數）【考點】計數之遞推法【難度】5星【題型】解答【解析】如果沒有剩下的不能使質數這個條件，那么遞推方法與前面學過的遞推法相似，只不過每次都是前【鞏固】有20個相同的棋子，一個人分若干次取，每次可取1個，2個，3個或4個，但要求每次取之后留下的棋子數不是3或4的倍數，有種不同的方法取完這堆棋子.【考點】計數之遞推法【難度】5星【題型】填空【解析】把20、0和20以內不是3或4的倍數的數寫成一串，用遞推法把所有的方法數寫出來:20191714131110752rr0112246121813183654【答案】54【例12】4個人進行籃球訓練，互相

15、傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方法？【考點】計數之遞推法【難度】5星【題型】解答【解析】設第n次傳球后，球又回到甲手中的傳球方法有an種.可以想象前n1次傳球，如果每一次傳球都任選其他三人中的一人進行傳球，即每次傳球都有3種可能，由乘法原理，共有,3333nT（種）（n）個3傳球方法.這些傳球方法并不是都符合要求的，它們可以分為兩類，一類是第n-1次恰好傳到甲手中，這有an種傳法，它們不符合要求，因為這樣第n次無法再把球傳給甲；另一類是第n-1次傳球，球不在甲手中，第n次持球人再將球傳給甲，有an種傳法.根據

16、加法原理，有n1an。+an三3M3M父3=3（n小個3由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方法是不存在的，所以a二0.利用遞推關系可以得到：a2=3-0=3,a3=3M33=6,a4=33x3-6=21,a5=3x3x3x3-21=60.這說明經過5次傳球后，球仍回到甲手中的傳球方法有60種.本題也可以列表求解.由于第n次傳球后，球不在甲手中的傳球方法，第n+1次傳球后球就可能回到甲手中，所以只需求出第四次傳球后，球不在甲手中的傳法共有多少種.第n次傳球傳球的方法球在甲手中的傳球方法球不雇甲手中的傳球方法13Q3293;327fi2148121524360133從表中可以看出經過五

17、次傳球后，球仍回到甲手中的傳球方法共有60種.【答案】60【鞏固】五個人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經過4次傳球后，球仍回到甲手中.問：共有多少種傳球方式？【考點】計數之遞推法【難度】5星【題型】解答【解析】遞推法.設第n次傳球后球傳到甲的手中的方法有an種.由于每次傳球有4種選擇，傳n次有4n次可能.其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有an種，球不在甲的手中的，下一次傳球都可以將球傳到甲的手中，故有an引種.所以an+an+=4n.12_3由于a1=0,所以a2=4-ai=4,a3=4a2=12,a4=4-a3=52.即經過4次傳球后，球仍回到甲手中的傳球

18、方法有52種.【答案】52【例13】設A、E為正八邊形ABCDEFGH的相對頂點，頂點A處有一只青蛙，除頂點E外青蛙可以從正八邊形的任一頂點跳到其相鄰兩個頂點中任意一個，落到頂點E時青蛙就停止跳動，則青蛙從頂點A出發(fā)恰好跳10次后落到E的方法總數為種.【考點】計數之遞推法【難度】5星【題型】填空【關鍵詞】清華附中【解析】可以使用遞推法.回到A跳到B或H跳到C或G跳到D或FE1步12步213步314步6425步1046步201487步34148步6848289步11648其中，A列的每個數都等于它的上一行的第二列的數的2倍，第二列的每一個數都等于它的上一行的第一列和第三列的兩個數的和，第三列的每

19、一個數都等于它的上一行的第二列和第四列的兩個數的和，第四列的每一個數都等于它的上一行的第三列的數，第五列的每一個數都等于都等于它的上一行的第四列的數的2倍.這一規(guī)律很容易根據青蛙的跳動規(guī)則分析得來.所以，青蛙第10步跳到E有482=96種方法.【答案】96【鞏固】在正五邊形ABCDE上，一只青蛙從A點開始跳動，它每次可以隨意跳到相鄰兩個頂點中的一個上,一旦跳到D點上就停止跳動.青蛙在6次之內（含6次）跳到D點有種不同跳法.【考點】計數之遞推法【難度】5星【題型】填空【解析】采用遞推的方法.列表如下:跳到A跳到B跳到C彳口D跳到E1步112步2113步3124步5325步8356步1385其中，

20、根據規(guī)則，每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到D點上就停止跳動.所以，每一步跳到A的跳法數等于上一步跳到B和E的跳法數之和，每一步跳到B的跳法數等于上一步跳到A和C的跳法數之和，每一步跳到C的跳法數等于上一步跳到B的跳法數，每一步跳到E的跳法數等于上一步跳到A的跳法數，每一步跳到D的跳法數等于上一步跳到C或跳到E的跳法數.觀察可知，上面的遞推結果與前面的枚舉也相吻合，所以青蛙在6次之內（含6次）跳到D點共有1+1+2+3+5=12種不同的跳法.【答案】12【例14】有6個木箱，編號為1,2,3,，6,每個箱子有一把鑰匙，6把鑰匙各不相同，每個箱子放進一把鑰匙鎖好.先挖開1,2號箱子

21、，可以取出鑰匙去開箱子上的鎖，如果最終能把6把鎖都打開，則說這是一種放鑰匙的好”的方法，那么好”的方法共有種.【考點】計數之遞推法【難度】5星【題型】填空【關鍵詞】迎春杯，中年級組，決賽【解析】（法1）分類討論.如果1,2號箱中恰好放的就是1,2號箱的鑰匙，顯然不是好”的方法，所以好”的方法有兩種情況：（1）1,2號箱的鑰匙恰有1把在1,2號箱中，另一箱裝的是36箱的鑰匙.1,2號箱的鑰匙都不在1,2號箱中.對于，從1,2號箱的鑰匙中選1把，從36號箱的鑰匙中選1把，共有2M4=8（種）選法，每一種選法放入1,2號箱各有2種放法，共有8M2=16（種）放法.不妨設1,3號箱的鑰匙放入了1,2號

22、箱，此時3號箱不能裝2號箱的鑰匙，有3種選法，依次類推，可知此時不同的放法有3父2父1=6（種）.所以，第種情況有好”的方法16M6=96（種）.對于，從36號箱的鑰匙中選2把放入1,2號箱，有4父3=12（種）放法.不妨設3,4號箱的鑰匙放入了1,2號箱.此時1,2號箱的鑰匙不可能都放在3,4號箱中，也就是說3,4號箱中至少有1把5,6號箱的鑰匙.如果3,4號箱中有2把5,6號箱的鑰匙，也就是說3,4號箱中放的恰好是5,6號箱的鑰匙，那么1,2號箱的鑰匙放在5,6號箱中，有2父2=4種放法；如果3,4號箱中有1把5,6號箱的鑰匙，比如3,4號箱中放的是5,1號箱的鑰匙，則只能是5號箱放6號箱

23、的鑰匙，6號箱放2號箱的鑰匙，有2M1=2種放法；同理，3,4號箱放5,2號箱或6,1號箱或6,2號箱的鑰匙，也各有2種放法.所以，第種情況有好”的放法12秋4+2+2+2+2）=144（種）.所以好”的方法共有96+144=240（種）.（法2）遞推法.設第1,2,3,，6號箱子中所放的鑰匙號碼依次為k1，k2,k3,，k6.當箱子數為n（n22）時，好的放法的總數為an.當n=2時，顯然a2=2（k1二1,k2=2或k1=2,k2=1）.當n=3時，顯然k3#3,否則第3個箱子打不開，從而幻=3或卜2=3,如果k1=3,則把1號箱子和3號箱子看作一個整體，這樣還是鎖著1,2兩號鑰匙，撬開1,2兩號箱子，那么方法有a2種；當k2=3也是如此.于是n=2時的每一種情況對應k1=3或k2=3時的一種情況，這樣就有a32a24.當n24時，也一定有kn#n,否則第n個箱子打不開，從而k1、k2、發(fā)中有一個為n,不論其中哪一個是n,由