小学奥数知识点拨 精讲试题 计数之递推法.学生版

小学奥数计数问题之递推法例题讲解【三篇】分析与解答：这道题我们可以采用分别求出每个数的立方是多少，再求和的方法来解答。

但是，这样计算的工作量比较大，我们可以从简单的情况开始研究。

【第三篇】例题：2000个学生排成一行，依次从左到右编上1～2000号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的离开队伍，…… 按这个规律如此下去，直至当队伍只剩下一人为止。

问：这时一共报了多少次？最后留下的这个人原来的号码是多少？分析与解答：难的不会想简单的，数大的不会想数小的。

我们先从这2000名同学中选出20人代替2000人进行分析，试着找出规律，然后再用这个规律来解题。

这20人第一次报数后共留下10人，因为20÷2＝10 ，这10人开始时的编号依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍数。

第二次报数后共留下5人，因为10÷2＝5 ，这5人开始时的编号依次是：4、8、12、16、20，都是4的倍数，也就是2×2的倍数。

第三次报数后共留下2人，因为5÷2＝2 ……1 ，这2人开始时的编号依次是：8、16，都是8的倍数，也就是2×2×2的倍数。

第四次报数后共留下1人，因为2÷2＝1 ，这1人开始时的编号是：16，都是8的倍数，也就是2×2×2×2的倍数。

由此可以发现，第n次报数后，留下的人的编号就是n个2的连乘积，这是一个规律。

2000名同学，报几次数后才能只留下一个同学呢?第一次：2000÷2＝1000 第二次：1000÷2＝500第三次：500÷2＝250 第四次：250÷2＝125第五次：125÷2＝62 ……1 第六次：62÷2＝31第七次：31÷2＝15 ......1 第八次：15÷2＝7 (1)第九次：7÷2＝3 ......1 第十次：3÷2＝1 (1)所以共需报10次数。

华杯赛计数专题: 归纳与递推基础知识:1.递推的基本思想: 从简单情况出发寻找规律, 逐步找到复杂问题的解法。

2.基本类型: 上楼梯问题、直线分平面问题、传球法、圆周连线问题。

3.递推分析的常用思路: 直接累加、增量分析、从复杂化归简单。

例题：例1.一个楼梯共有10级台阶, 规定每步可以迈一级台阶或二级台阶.走完这10级台阶, 一共可以有多少种不同的走法？【答案】89种【解答】设n级台阶有an种走法, 则an=an-1+an-21级有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种【解答】通过枚举法和递推法: 设n块糖有an种走法, 则an=an-1+an-2+ an-31块糖有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种盖法。

小升初奥数计数问题之递推方法的解题技巧【篇一】递推方法的概述在不少计数问题中，要很快求出结果是比较困难的，有时可先从简单情况入手，然后从某一种特殊情况逐渐推出与以后比较复杂情况之间的关系，找出规律逐步解决问题，这样的方法叫递推方法。

例1、线段AB上共有10个点(包括两个端点)，那么这条线段上一共有多少条不同的线段?分析与解答：从简单情况研究起：AB上共有2个点，有线段：1条AB上共有3个点，有线段：1+2=3(条)AB上共有4个点，有线段：1+2+3=6(条)AB上共有5个点，有线段：1+2+3+4=10(条)……AB上共有10个点，有线段：1+2+3+4+…+9=45(条)一般地，AB上共有n个点，有线段：1+2+3+4+…+(n-1)=n×(n-1)÷2即：线段数=点数×(点数-1)÷2例2、2000个学生排成一行，依次从左到右编上1～2000号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的离开队伍，……按这个规律此下去，直至当队伍只剩下一人为止。

问：这时一共报了多少次?最后留下的这个人原来的号码是多少?分析与解答：难的不会想简单的，数大的不会想数小的。

我们先从这2000名同学中选出20人代替2000人进行分析，试着找出规律，然后再用这个规律来解题。

这20人第一次报数后共留下10人，因为20÷2=10，这10人开始时的编号依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍数。

第二次报数后共留下5人，因为10÷2=5，这5人开始时的编号依次是：4、8、12、16、20，都是4的倍数，也就是2×2的倍数。

第三次报数后共留下2人，因为5÷2=2……1，这2人开始时的编号依次是：8、16，都是8的倍数，也就是2×2×2的倍数。

第四次报数后共留下1人，因为2÷2=1，这1人开始时的编号是：16，都是8的倍数，也就是2×2×2×2的倍数。

7-6-4.計數之遞推法教學目標前面在講加法原理、乘法原理、排列組合時已經穿插講解了計數中的一些常用的方法，比如枚舉法、樹狀圖法、標數法、捆綁法、排除法、插板法等等，這裏再集中學習一下計數中其他常見的方法，主要有歸納法、整體法、對應法、遞推法．對這些計數方法與技巧要做到靈活運用．例題精講對於某些難以發現其一般情形的計數問題，可以找出其相鄰數之間的遞歸關係，有了這一遞歸關係就可以利用前面的數求出後面未知的數，這種方法稱為遞推法．【例 1】每對小兔子在出生後一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來．如果一個人在一月份買了一對小兔子，那麼十二月份的時候他共有多少對兔子？【考點】計數之遞推法【難度】3星【題型】解答【解析】第一個月，有1對小兔子；第二個月，長成大兔子，所以還是1對；第三個月，大兔子生下一對小兔子，所以共有2對；第四個月，剛生下的小兔子長成大兔子，而原來的大兔子又生下一對小兔子，共有3對；第五個月，兩對大兔子生下2對小兔子，共有5對；……這個特點的說明每月的大兔子數為上月的兔子數，每月的小兔子數為上月的大兔子數，即上上月的兔子數，所以每月的兔子數為上月的兔子數與上上月的兔子數相加．依次類推可以列出下表：經過月數：---1---2---3---4---5---6---7---8---9---10---11---12兔子對數：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的時候總共有144對兔子．【答案】144【例 2】樹木生長的過程中，新生的枝條往往需要一段“休息”時間供自身生長，而後才能萌發新枝．一棵樹苗在一年後長出一條新枝，第二年新枝“休息”，老枝依舊萌發新枝；此後，老枝與“休息”過一年的枝同時萌發，當年生的新枝則依次“休息”．這在生物學上稱為“魯德維格定律”．那麼十年後這棵樹上有多少條樹枝？【考點】計數之遞推法【難度】3星【題型】解答【解析】一株樹木各個年份的枝椏數，構成斐波那契數列：1，2，3，5，8，13，21，34，55，89，……所以十年後樹上有89條樹枝．【答案】89【例 3】一樓梯共10級，規定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法？【考點】計數之遞推法【難度】4星【題型】解答【解析】登1級2級3級4級 ...... 10級1種方法 2種3種5種 ...... ？我們觀察每級的種數，發現這麼一個規律：從第三個數開始，每個數是前面兩個數的和；依此規律我們就可以知道了第10級的種數是89.其實這也是加法的運用：假如我們把這個人開始登樓梯的位置看做A0，那麼登了1級的位置是在A1，2級在A2... A10級就在A10．到A3的前一步有兩個位置；分別是A2和A1．在這裏要強調一點，那麼A2到A3 既然是一步到了，那麼A2、A3之間就是一種選擇了；同理A1到A3也是一種選擇了．同時我們假設到n級的選擇數就是An．那麼從A0到A3就可以分成兩類了：第一類：A0 ---- A1 ------ A3 ，那麼就可以分成兩步．有A1×1種，也就是A1 種；(A1 ------ A3 是一種選擇)第二類：A0 ---- A2 ------ A3，同樣道理有A2 ．類類相加原理：A3 = A1 ＋A2，依次類推An = An-1 + An-2．【答案】89【鞏固】一樓梯共10級，規定每步只能跨上一級或三級，要登上第10級，共有多少種不同走法？【考點】計數之遞推法【難度】4星【題型】解答【解析】 登 1級 2級 3級 4級 5級 ...... 10級1種方法 1種 2種 3種 4種...... ？我們觀察每級的種數，發現這麼一個規律：從第三個數開始，每個數是前面相隔的兩個數的和；依此規律我們就可以知道了第10級的種數是28. 【答案】28【例 4】 1×2的小長方形(橫的豎的都行)覆蓋2×10的方格網，共有多少種不同的蓋法．【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 如果用12⨯的長方形蓋2n ⨯的長方形，設種數為n a ,則11a =，22a =,對於3n ≥，左邊可能豎放1個12⨯的，也可能橫放2個12⨯的，前者有-1n a 種，後者有-2n a 種，所以-1-2n n n a a a =+,所以根據遞推，覆蓋210⨯的長方形一共有89種． 【答案】89【例 5】 用13⨯的小長方形覆蓋38⨯的方格網，共有多少種不同的蓋法？【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 如果用13⨯的長方形蓋3n ⨯的長方形，設種數為n a ,則11a =，21a =,32a =,對於4n ≥，左邊可能豎放1個13⨯的，也可能橫放3個13⨯的，前者有-1n a 種，後者有a 種，所以a a a =+,依照這條遞推公式列表：31⨯32⨯33⨯34⨯35⨯36⨯37⨯38⨯1 1234 6 9 13所以用13⨯的小長方形形覆蓋38⨯的方格網，共有13種不同的蓋法． 【答案】13【例 6】 有一堆火柴共12根，如果規定每次取1～3根，那麼取完這堆火柴共有多少種不同取法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以後取任意根火柴的種數等於取到前三根火柴所有情況之和，以此類推，取完這堆火柴一共有927種方法．【答案】927【巩固】 一堆蘋果共有8個，如果規定每次取1～3個，那麼取完這堆蘋果共有多少種不同取法？ 【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以後取任意個蘋果的種數等於取到前三個蘋果所有情況之和，以此類推，取完這堆蘋果一共有81種方法．【答案】81【例 7】 有10枚棋子，每次拿出2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？【考點】計數之遞推法 【難度】4星 【題型】解答 【解析】 本題可以採用遞推法，也可以進行分類討論，當然也可以直接進行枚舉．(法1)遞推法．假設有n 枚棋子，每次拿出2枚或3枚，將n 枚棋子全部拿完的拿法總數為n a 種． 則21a =，31a =，41a =．由於每次拿出2枚或3枚，所以32n n n a a a --=+(5n ≥)．所以，5232a a a =+=；6342a a a =+=；7453a a a =+=；8564a a a =+=；9675a a a =+=；10787a a a =+=．即當有10枚棋子時，共有7種不同的拿法． (法2)分類討論．由於棋子總數為10枚，是個偶數，而每次拿2枚或3枚，所以其中拿3枚的次數也應該是偶數．由於拿3枚的次數不超過3次，所以只能為0次或2次．若為0次，則相當於2枚拿了5次，此時有1種拿法；若為2次，則2枚也拿了2次，共拿了4次，所以此時有246C =種拿法． 根據加法原理，共有167+=種不同的拿法． 【答案】7【例 8】 如下圖，一只蜜蜂從A 處出發，回到家裏B 處，每次只能從一個蜂房爬向右側鄰近的蜂房而不准逆行，共有多少種回家的方法？【考點】計數之遞推法 【難度】4星 【題型】解答BA AB 1357946821235813213455891【解析】 蜜蜂“每次只能從一個蜂房爬向右側鄰近的蜂房而不准逆行”這意味著它只能從小號碼的蜂房爬近相鄰大號碼的蜂房．明確了行走路徑的方向，就可以運用標數法進行計算．如右圖所示，小蜜蜂從A 出發到B 處共有89種不同的回家方法．【答案】89【鞏固】小蜜蜂通過蜂巢房間，規定只能由小號房間進入大號房間問小蜜蜂由A 房間到達B 房間有多少種方法？ 【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 斐波那契數列第八項．21種．【答案】21【例 9】 如下圖，一只蜜蜂從A 處出發，回到家裏B 處，每次只能從一個蜂房爬向右側鄰近的蜂房而不准逆行，共有多少種回家的方法？【考點】計數之遞推法 【難度】4星 【題型】解答BA【解析】 按照蜜蜂只能從小號碼的蜂房爬近相鄰大號碼的蜂房的原則，運用標號法進行計算．如右圖所示，小蜜蜂從A 出發到B 處共有296種不同的回家方法．【答案】296【例 10】對一個自然數作如下操作：如果是偶數則除以2，如果是奇數則加1，如此進行直到得數為1操作停止．問經過9次操作變為1的數有多少個？【考點】計數之遞推法 【難度】4星 【題型】解答 【解析】 可以先嘗試一下，倒推得出下麵的圖：2410131112514302831643215167683421其中經1次操作變為1的1個，即2， 經2次操作變為1的1個，即4，經3次操作變為1的2個，是一奇一偶，以後發現，每個偶數可以變成兩個數，分別是一奇一偶，每個奇數變為一個偶數，於是，經1、2、…次操作變為1的數的個數依次為：1，1，2，3，5，8，…這一串數中有個特點：自第三個開始，每一個等於前兩個的和，即即經過9次操作變為1的數有34個. 為什麼上面的規律是正確的呢？道理也很簡單. 設經過n 次操作變為1的數的個數為n a ,則1a =1，2a =1，3a =2，…從上面的圖看出，1n a +比n a 大.一方面，每個經過n 次操作變為1的數，乘以2，就得出一個偶數，經過1n +次操作變為1；反過來，每個經過1n +次操作變為1的偶數，除以2，就得出一個經過n 次操作變為1的數. 所以經過n 次操作變為1的數與經過1n +次操作變為1的偶數恰好一樣多.前者的個數是n a ,因此後者也是n a 個. 另一方面，每個經過n 次操作變為1的偶數，減去1，就得出一個奇數，它經過1n +次操作變為1，反過來.每個經過1n +次操作變為1的奇數，加上1，就得出一個偶數，它經過n 次操作變為1. 所以經過n 次操作變為1的偶數經過1n +次操作變為1的奇數恰好一樣多.而由上面所說，前者的個數就是1n a -,因此後者也是1n a -.經過n +1次操作變為1的數，分為偶數、奇數兩類，所以11n n n a a a +-=+，即上面所說的規律的確成立. 【答案】34【例 11】有20個石子，一個人分若干次取，每次可以取1個，2個或3個，但是每次取完之後不能留下質數個，有多少種方法取完石子？（石子之間不作區分，只考慮石子個數）【考點】計數之遞推法 【難度】5星 【題型】解答 【解析】 如果沒有剩下的不能使質數這個條件，那麼遞推方法與前面學過的遞推法相似，只不過每次都是前面3個數相加．現在剩下的不能是質數個，可以看作是質數個的取法總數都是0，然後再進行遞推．【答案】25【鞏固】有20個相同的棋子，一個人分若干次取，每次可取1個，2個，3個或4個，但要求每次取之後留下的棋子數不是3或4的倍數，有 種不同的方法取完這堆棋子.【考點】計數之遞推法 【難度】5星 【題型】填空【解析】 把20、0和20以內不是3或4的倍數的數寫成一串，用遞推法把所有的方法數寫出來：【答案】54【例 12】4個人進行籃球訓練，互相傳球接球，要求每個人接球後馬上傳給別人，開始由甲發球，並作為第一次傳球，第五次傳球後，球又回到甲手中，問有多少種傳球方法？【考點】計數之遞推法 【難度】5星 【題型】解答 【解析】 設第n 次傳球後，球又回到甲手中的傳球方法有n a 種．可以想像前1n -次傳球，如果每一次傳球都任選其他三人中的一人進行傳球，即每次傳球都有3種可能，由乘法原理，共有11333333n n --⨯⨯⨯=()个…(種)傳球方法．這些傳球方法並不是都符合要求的，它們可以分為兩類，一類是第1n -次恰好傳到甲手中，這有1n a -種傳法，它們不符合要求，因為這樣第n 次無法再把球傳給甲；另一類是第1n -次傳球，球不在甲手中，第n 次持球人再將球傳給甲，有n a 種傳法．根據加法原理，有11133333n n n n a a ---+=⨯⨯⨯=(个…)．由於甲是發球者，一次傳球後球又回到甲手中的傳球方法是不存在的，所以10a =．利用遞推關係可以得到：2303a =-=，33336a =⨯-=，4333621a =⨯⨯-=，533332160a =⨯⨯⨯-=．這說明經過5次傳球後，球仍回到甲手中的傳球方法有60種． 本題也可以列表求解．由於第n 次傳球後，球不在甲手中的傳球方法，第1n +次傳球後球就可能回到甲手中，所以只需求出第四次傳球後，球不在甲手中的傳法共有多少種．從表中可以看出經過五次傳球後，球仍回到甲手中的傳球方法共有60種．【答案】60【鞏固】五個人互相傳球，由甲開始發球，並作為第一次傳球，經過4次傳球後，球仍回到甲手中．問：共有多少種傳球方式？ 【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 遞推法．設第n 次傳球後球傳到甲的手中的方法有n a 種．由於每次傳球有4種選擇，傳n 次有4n 次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有n a 種，球不在甲的手中的，下一次傳球都可以將球傳到甲的手中，故有1n a +種．所以14n n n a a ++=．由於10a =，所以12144a a =-=，232412a a =-=，343452a a =-=．即經過4次傳球後，球仍回到甲手中的傳球方法有52種．【答案】52【例 13】設A、E為正八邊形ABCDEFGH的相對頂點，頂點A處有一只青蛙，除頂點E外青蛙可以從正八邊形的任一頂點跳到其相鄰兩個頂點中任意一個，落到頂點E時青蛙就停止跳動，則青蛙從頂點A出發恰好跳10次後落到E的方法總數為種．【考點】計數之遞推法【難度】5星【題型】填空【關鍵字】清華附中【解析】可以使用遞推法．回到A跳到B或H跳到C或G跳到D或F停在E1步 12步 2 13步 3 14步 6 4 25步10 46步20 14 87步34 148步68 48 289步116 48其中，第一列的每一個數都等於它的上一行的第二列的數的2倍，第二列的每一個數都等於它的上一行的第一列和第三列的兩個數的和，第三列的每一個數都等於它的上一行的第二列和第四列的兩個數的和，第四列的每一個數都等於它的上一行的第三列的數，第五列的每一個數都等於都等於它的上一行的第四列的數的2倍．這一規律很容易根據青蛙的跳動規則分析得來．所以，青蛙第10步跳到E有48296⨯=種方法．【答案】96【鞏固】在正五邊形ABCDE上，一只青蛙從A點開始跳動，它每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到D點上就停止跳動．青蛙在6次之內(含6次)跳到D點有種不同跳法．【考點】計數之遞推法【難度】5星【題型】填空ABEC D【解析】採用遞推的方法．列表如下：跳到A跳到B跳到C停在D跳到E 1步 1 12步 2 1 13步 3 1 24步 5 3 25步8 3 56步13 8 5其中，根據規則，每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到D 點上就停止跳動．所以，每一步跳到A的跳法數等於上一步跳到B和E的跳法數之和，每一步跳到B的跳法數等於上一步跳到A和C的跳法數之和，每一步跳到C的跳法數等於上一步跳到B的跳法數，每一步跳到E的跳法數等於上一步跳到A的跳法數，每一步跳到D的跳法數等於上一步跳到C或跳到E的跳法數．觀察可知，上面的遞推結果與前面的枚舉也相吻合，所以青蛙在6次之內(含6次)跳到D點共有1123512++++=種不同的跳法．【答案】12【例 14】有6個木箱，編號為1，2，3，……，6，每個箱子有一把鑰匙，6把鑰匙各不相同，每個箱子放進一把鑰匙鎖好．先挖開1，2號箱子，可以取出鑰匙去開箱子上的鎖，如果最終能把6把鎖都打開，則說這是一種放鑰匙的“好”的方法，那麼“好”的方法共有種．【考點】計數之遞推法【難度】5星【題型】填空【關鍵字】迎春杯，中年級組，決賽【解析】(法1)分類討論．如果1，2號箱中恰好放的就是1，2號箱的鑰匙，顯然不是“好”的方法，所以“好”的方法有兩種情況：⑴1，2號箱的鑰匙恰有1把在1，2號箱中，另一箱裝的是3～6箱的鑰匙．⑵1，2號箱的鑰匙都不在1，2號箱中．對於⑴，從1，2號箱的鑰匙中選1把，從3～6號箱的鑰匙中選1把，共有248⨯=(種)⨯=(種)選法，每一種選法放入1，2號箱各有2種放法，共有8216放法．不妨設1，3號箱的鑰匙放入了1，2號箱，此時3號箱不能裝2號箱的鑰匙，有3種選法，依次類推，可知此時不同的放法有3216⨯⨯=(種)．所以，第⑴種情況有“好”的方法16696⨯=(種)．對於⑵，從3～6號箱的鑰匙中選2把放入1，2號箱，有4312⨯=(種)放法．不妨設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號箱中，有224⨯=種放法；如果3，4號箱中有1把5，6號箱的鑰匙，比如3，4號箱中放的是5，1號箱的鑰匙，則只能是5號箱放6號箱的鑰匙，6號箱放2號箱的鑰匙，有212⨯=種放法；同理，3，4號箱放5，2號箱或6，1號箱或6，2號箱的鑰匙，也各有2種放法．所以，第⑵種情況有“好”的放法()1242222144⨯++++=(種)．所以“好”的方法共有96144240+=(種)．(法2)遞推法．設第1，2，3，…，6號箱子中所放的鑰匙號碼依次為1k ，2k ，3k ，…，6k ．當箱子數為n (2n ≥)時，好的放法的總數為n a ．當2n =時，顯然22a =(11k =，22k =或12k =，21k =)．當3n =時，顯然33k ≠，否則第3個箱子打不開，從而13k =或23k =，如果13k =，則把1號箱子和3號箱子看作一個整體，這樣還是鎖著1，2兩號鑰匙，撬開1，2兩號箱子，那麼方法有2a 種；當23k =也是如此．於是2n =時的每一種情況對應13k =或23k =時的一種情況，這樣就有3224a a ==．當4n ≥時，也一定有n k n ≠，否則第n 個箱子打不開，從而1k 、2k 、……、1n k -中有一個為n ，不論其中哪一個是n ，由於必須要把該箱子打開才能打開n 號箱子，所以可以將鎖著這把鑰匙的箱子與第n 號箱子看作1個箱子，於是還是鎖著1k 、2k 、……、1n k -這()1n -把鑰匙，需要撬開1，2兩號箱子，所以每種情況都有1n a -種．所以()11n n a n a -=-．所以，6542554543225!240a a a a ==⨯==⨯⨯⨯=⨯=，即好的方法總數為240種． 【答案】240【鞏固】有10個木箱，編號為1，2，3，……，10，每個箱子有一把鑰匙，10把鑰匙各不相同，每個箱子放進一把鑰匙鎖好．先挖開1，2號箱子，可以取出鑰匙去開箱子上的鎖，如果最終能把10把鎖都打開，則說這是一種放鑰匙的“好”的方法，那麼“好”的方法共有 種．【考點】計數之遞推法 【難度】5星 【題型】填空【解析】 遞推法．設第1，2，3，…，6號箱子中所放的鑰匙號碼依次為1k ，2k ，3k ，…，6k ．當箱子數為n (2n ≥)時，好的放法的總數為n a ．當2n =時，顯然22a =(11k =，22k =或12k =，21k =)．當3n =時，顯然33k ≠，否則第3個箱子打不開，從而13k =或23k =，如果13k =，則把1號箱子和3號箱子看作一個整體，這樣還是鎖著1，2兩號鑰匙，撬開1，2兩號箱子，那麼方法有2a 種；當23k =也是如此．於是2n =時的每一種情況對應13k =或23k =時的一種情況，這樣就有3224a a ==．當4n ≥時，也一定有n k n ≠，否則第n 個箱子打不開，從而1k 、2k 、……、1n k -中有一個為n ，不論其中哪一個是n ，由於必須要把該箱子打開才能打開n 號箱子，所以可以將鎖著這把鑰匙的箱子與第n 號箱子看作1個箱子，於是還是鎖著1k 、2k 、……、1n k -這()1n -把鑰匙，需要撬開1，2兩號箱子，所以每種情況都有1n a -種．所以()11n n a n a -=-．所以，109829989876543229!=725760a a a a ==⨯==⨯⨯⨯⨯⨯⨯⨯=⨯，即好的方法總數為725760種．【答案】725760。

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用． 对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？【例 3】 一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法．【例 5】 用13⨯的小长方形覆盖38⨯的方格网，共有多少种不同的盖法？ 例题精讲教学目标7-6-4.计数之递推法【例 6】有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？【巩固】一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？【例 7】有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？【例 8】如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？AB【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A房间到达B房间有多少种方法？【例 9】如下图，一只蜜蜂从A处出发，回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【例 10】对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？【例 11】有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是3或4的倍数，有种不同的方法取完这堆棋子.【例 12】4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共有多少种传球方式？【例 13】设A、E为正八边形ABCDEFGH的相对顶点，顶点A处有一只青蛙，除顶点E外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶点A出发恰好跳10次后落到E的方法总数为种．【巩固】在正五边形ABCDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．青蛙在6次之内(含6次)跳到D点有种不同跳法．ABEC D【例 14】有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有种．【巩固】有10个木箱，编号为1，2，3，……，10，每个箱子有一把钥匙，10把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把10把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有种．一、现代文阅读1．现代文阅读阅读议论文《精神拾荒三步曲》，回答下列小题。

前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法． 【例 1】 每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？ 【考点】计数之递推法 【难度】3星 【题型】解答【解析】 第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加． 依次类推可以列出下表： 经过月数：---1---2---3---4---5---6---7---8---9---10---11---12兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的时候总共有144对兔子．【答案】144【例 2】 树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？ 【考点】计数之递推法 【难度】3星 【题型】解答【解析】 一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，……所以十年后树上有89条树枝．【答案】89【例 3】 一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？ 【考点】计数之递推法 【难度】4星 【题型】解答例题精讲教学目标7-6-4.计数之递推法【解析】 登 1级 2级 3级 4级 ...... 10级1种方法 2种 3种 5种 ...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A 0，那么登了1级的位置是在A 1，2级在A 2... A 10级就在A 10．到A 3的前一步有两个位置；分别是A 2 和A 1 ．在这里要强调一点，那么A 2 到A 3 既然是一步到了，那么A 2 、A 3之间就是一种选择了；同理A 1 到A 3 也是一种选择了．同时我们假设到n 级的选择数就是An ．那么从A 0 到A 3 就可以分成两类了：第一类：A 0 ---- A 1 ------ A 3 ，那么就可以分成两步．有A 1×1种，也就是A 1 种；(A 1 ------ A 3 是一种选择)第二类：A 0 ---- A 2 ------ A 3， 同样道理 有A 2 ．类类相加原理：A 3 = A 1 ＋A 2，依次类推An = An -1 + An -2．【答案】89【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？ 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 登 1级 2级 3级 4级 5级 ...... 10级1种方法 1种 2种 3种 4种...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.【答案】28【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法． 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 如果用12⨯的长方形盖2n ⨯的长方形，设种数为n a ,则11a =，22a =,对于3n ≥，左边可能竖放1个12⨯的，也可能横放2个12⨯的，前者有-1n a 种，后者有-2n a 种，所以-1-2n n n a a a =+,所以根据递推，覆盖210⨯的长方形一共有89种．【例 5】 用13⨯的小长方形覆盖38⨯的方格网，共有多少种不同的盖法？ 【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果用13⨯的长方形盖3n ⨯的长方形，设种数为n a ,则11a =，21a =,32a =,对于4n ≥，左边可能竖放1个13⨯的，也可能横放3个13⨯的，前者有-1n a 种，后者有-3n a 种，所以-1-3n n n a a a =+,依照这【答案】13【例 6】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？ 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种【答案】927【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？ 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种【答案】81【例 7】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？ 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举．(法1)递推法．假设有n 枚棋子，每次拿出2枚或3枚，将n 枚棋子全部拿完的拿法总数为n a 种． 则21a =，31a =，41a =．由于每次拿出2枚或3枚，所以32n n n a a a --=+(5n ≥)．所以，5232a a a =+=；6342a a a =+=；7453a a a =+=；8564a a a =+=；9675a a a =+=；10787a a a =+=．即当有10枚棋子时，共有7种不同的拿法． (法2)分类讨论．由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次． 若为0次，则相当于2枚拿了5次，此时有1种拿法；若为2次，则2枚也拿了2次，共拿了4次，所以此时有246C =种拿法． 根据加法原理，共有167+=种不同的拿法．【例 8】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？ 【考点】计数之递推法 【难度】4星 【题型】解答BA AB 1357946821235813213455891【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有89种不同的回家方法．【答案】89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A 房间到达B 房间有多少种方法？ 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 斐波那契数列第八项．21种．【答案】21【例 9】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？ 【考点】计数之递推法 【难度】4星 【题型】解答【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有296种不同的回家方法．【答案】296【例 10】 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？ 【考点】计数之递推法 【难度】4星 【题型】解答 【解析】 可以先尝试一下，倒推得出下面的图：2410131112514302831643215167683421其中经1次操作变为1的1个，即2， 经2次操作变为1的1个，即4， 经3次操作变为1的2个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.为什么上面的规律是正确的呢？道理也很简单. 设经过n 次操作变为1的数的个数为n a ,则1a =1，2a =1，3a =2，… 从上面的图看出，1n a +比n a 大.一方面，每个经过n 次操作变为1的数，乘以2，就得出一个偶数，经过1n +次操作变为1；反过来，每个经过1n +次操作变为1的偶数，除以2，就得出一个经过n 次操作变为1的数. 所以经过n 次操作变为1的数与经过1n +次操作变为1的偶数恰好一样多.前者的个数是n a ,因此后者也是n a 个. 另一方面，每个经过n 次操作变为1的偶数，减去1，就得出一个奇数，它经过1n +次操作变为1，反过来.每个经过1n +次操作变为1的奇数，加上1，就得出一个偶数，它经过n 次操作变为1. 所以经过n 次操作变为1的偶数经过1n +次操作变为1的奇数恰好一样多. 而由上面所说，前者的个数就是1n a -,因此后者也是1n a -.经过n +1次操作变为1的数，分为偶数、奇数两类，所以11n n n a a a +-=+，即上面所说的规律的确成立.【答案】34【例 11】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数） 【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．【答案】25【考点】计数之递推法 【难度】5星 【题型】填空【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：【答案】54【例 12】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？ 【考点】计数之递推法 【难度】5星 【题型】解答【解析】 设第n 次传球后，球又回到甲手中的传球方法有n a 种．可以想象前1n -次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有11333333n n --⨯⨯⨯=()个…(种)传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第1n -次恰好传到甲手中，这有1n a -种传法，它们不符合要求，因为这样第n 次无法再把球传给甲；另一类是第1n -次传球，球不在甲手中，第n 次持球人再将球传给甲，有n a 种传法．根据加法原理，有11133333n n n n a a ---+=⨯⨯⨯=(个…)．由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以10a =．利用递推关系可以得到：2303a =-=，33336a =⨯-=，4333621a =⨯⨯-=，533332160a =⨯⨯⨯-=．这说明经过5次传球后，球仍回到甲手中的传球方法有60种． 本题也可以列表求解．由于第n 次传球后，球不在甲手中的传球方法，第1n +次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．【答案】60【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共有多少种传球方式？ 【考点】计数之递推法 【难度】5星 【题型】解答【解析】 递推法．设第n 次传球后球传到甲的手中的方法有n a 种．由于每次传球有4种选择，传n 次有4n 次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有n a 种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有1n a +种．所以14n n n a a ++=．由于10a =，所以12144a a =-=，232412a a =-=，343452a a =-=．即经过4次传球后，球仍回到甲手中的传球方法有52种．【答案】52点A出发恰好跳10次后落到E的方法总数为种．【考点】计数之递推法【难度】5星【题型】填空【关键词】清华附中【解析】可以使用递推法．回到A跳到B或H跳到C或G跳到D或F停在E 1步 12步 2 13步 3 14步 6 4 25步10 46步20 14 87步34 148步68 48 289步116 48其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来．所以，青蛙第10步跳到E有48296⨯=种方法．【答案】96【巩固】在正五边形ABCDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．青蛙在6次之内(含6次)跳到D点有种不同跳法．【考点】计数之递推法【难度】5星【题型】填空ABEC D【解析】采用递推的方法．列表如下：跳到A跳到B跳到C停在D跳到E1步 1 12步 2 1 13步 3 1 24步 5 3 25步8 3 56步13 8 5其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．所以，每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和，每一步跳到B的跳法数等于上一步跳到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到B的跳法数，每一步跳到E的跳法数等于上一步跳到A的跳法数，每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数．【答案】12【例 14】 有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种． 【考点】计数之递推法 【难度】5星 【题型】填空 【关键词】迎春杯，中年级组，决赛【解析】 (法1)分类讨论．如果1，2号箱中恰好放的就是1，2号箱的钥匙，显然不是“好”的方法，所以“好”的方法有两种情况：⑴1，2号箱的钥匙恰有1把在1，2号箱中，另一箱装的是3～6箱的钥匙． ⑵1，2号箱的钥匙都不在1，2号箱中．对于⑴，从1，2号箱的钥匙中选1把，从3～6号箱的钥匙中选1把，共有248⨯=(种)选法，每一种选法放入1，2号箱各有2种放法，共有8216⨯=(种)放法．不妨设1，3号箱的钥匙放入了1，2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可知此时不同的放法有3216⨯⨯=(种)． 所以，第⑴种情况有“好”的方法16696⨯=(种)．对于⑵，从3～6号箱的钥匙中选2把放入1，2号箱，有4312⨯=(种)放法．不妨设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号箱中，有224⨯=种放法；如果3，4号箱中有1把5，6号箱的钥匙，比如3，4号箱中放的是5，1号箱的钥匙，则只能是5号箱放6号箱的钥匙，6号箱放2号箱的钥匙，有212⨯=种放法；同理，3，4号箱放5，2号箱或6，1号箱或6，2号箱的钥匙，也各有2种放法． 所以，第⑵种情况有“好”的放法()1242222144⨯++++=(种)． 所以“好”的方法共有96144240+=(种)．(法2)递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-． 所以，6542554543225!240a a a a ==⨯==⨯⨯⨯=⨯=，即好的方法总数为240种．【答案】240开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．【考点】计数之递推法 【难度】5星 【题型】填空【解析】 递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-． 所以，109829989876543229!=725760a a a a ==⨯==⨯⨯⨯⨯⨯⨯⨯=⨯，即好的方法总数为725760种．【答案】725760。

五年级下册奥数知识点：递推方法计数方法与技巧递推法概念计数方法与技巧递推法例题例1：的乘积中有多少个数字是奇数分析与解答：如果我们通过计算找到答案比较麻烦;因此我们先从最简单的情况入手..9×9＝81;有1个奇数；99×99＝99×100－1＝9900－99＝9801;有2个奇数；999×999＝999×1000－1＝99900－999＝998001;有3个奇数；……从而可知;999…999×999…999的乘积中共有10个奇数..例题2：分析与解答：这道题我们可以采用分别求出每个数的立方是多少;再求和的方法来解答..但是;这样计算的工作量比较大;我们可以从简单的情况开始研究..例题3： 2000个学生排成一行;依次从左到右编上1～2000号;然后从左到右按一、二报数;报一的离开队伍;剩下的人继续按一、二报数;报一的离开队伍;…… 按这个规律如此下去;直至当队伍只剩下一人为止..问：这时一共报了多少次最后留下的这个人原来的号码是多少分析与解答：难的不会想简单的;数大的不会想数小的..我们先从这2000名同学中选出20人代替2000人进行分析;试着找出规律;然后再用这个规律来解题..这20人第一次报数后共留下10人;因为20÷2＝10 ;这10人开始时的编号依次是：2、4、6、8、10、12、14、16、18、20;都是2的倍数..第二次报数后共留下5人;因为10÷2＝5 ;这5人开始时的编号依次是： 4、8、12、16、20;都是4的倍数;也就是2×2的倍数..第三次报数后共留下2人;因为5÷2＝2 ……1 ;这2人开始时的编号依次是： 8、16;都是8的倍数;也就是2×2×2的倍数..第四次报数后共留下1人;因为2÷2＝1 ;这1人开始时的编号是：16;都是8的倍数;也就是2×2×2×2的倍数..由此可以发现;第n次报数后;留下的人的编号就是n个2的连乘积;这是一个规律..2000名同学;报几次数后才能只留下一个同学呢第一次：2000÷2＝1000 第二次：1000÷2＝500第三次：500÷2＝250 第四次：250÷2＝125第五次：125÷2＝62 ……1 第六次：62÷2＝31第七次：31÷2＝15 ......1 第八次：15÷2＝7 (1)第九次：7÷2＝3 ......1 第十次：3÷2＝1 (1)所以共需报10次数..那么;最后留下的同学在一开始时的编号应是：2×2×2×…×2＝1024号例题4：平面上有10个圆;最多能把平面分成几部分分析与解答：直接画出10个圆不是好办法;先考虑一些简单情况..一个圆最多将平面分为2部分；二个圆最多将平面分为4部分；三个圆最多将平面分为8部分；当第二个圆在第一个圆的基础上加上去时;第二个圆与第一个圆有2个交点;这两个交点将新加的圆弧分为2段;其中每一段圆弧都将所在平面的一分为二;所以所分平面部分的数在原有的2部分的基础上增添了2部分..因此;二个圆最多将平面分为2＋2＝4部分..同样道理;三个圆最多分平面的部分数是二个圆分平面为4部分的基础上增加4部分..因此;三个圆最多将平面分为2＋2＋4＝8部分..由此不难推出：画第10个圆时;与前9个圆最多有9×2＝18个交点;第10个圆的圆弧被分成18段;也就是增加了18个部分..因此;10个圆最多将平面分成的部分数为：2＋2＋4＋6＋…＋18＝2＋2×1＋2＋3＋…＋9＝2＋2×9×9＋1÷2＝92类似的分析;我们可以得到;n个圆最多将平面分成的部分数为：2＋2＋4＋6＋…＋2n－1＝2＋2×1＋2＋3＋…＋n－1＝2＋nn－1＝n2－n＋2一、填空题1.将一个数做如下运算:乘以4;再加上112;减去20;最后除以4;这时得100.那么这个数是 .2.李白提壶去买酒;遇店加一倍;见花喝一斗;三遇店和花;喝光壶中酒;壶中原有斗酒.3.甲、乙两个车站共停135辆汽车;如果从甲站开36辆到乙站;从乙站开45辆到甲站;这时乙站车是甲站的1.5倍.乙原来停辆车.4.农业站有一批化肥;第一天卖出一半又多15吨;第二次卖出余下的一半多8吨;第三次卖出180吨;正好卖完;这批化肥原来有吨.5.四个袋子共有168粒棋子;小红过来一看;把棋子作如下的调整;把丁袋调3粒到丙袋;丙调6粒到乙袋;乙又调6粒到甲袋;甲袋调2粒到丁袋;这时;四个袋子的棋子一样多;乙袋原来有粒棋子.6.一筐桔子;把它四等分后多一个;取走3份又一个;剩下的四等分后又剩一个;再取走3份又一个;剩下的四等分又剩一个;那么原来至少有个桔子.7.袋子里有若干个球;小华每次拿出其中的一半再放回一个球;这样共操作了5次;袋中还有3个球;那么;袋中原来共有个球.8.3÷7的小数点后面第1999位上的数是 .9.已知A;B;C;D四数之和为45;且A+2=B-2=C×2=D÷2;那么;这四个数依次是 .10.两个小于1000的质数之积是一个偶数;这个偶数最大可能是.二、解答题11.池塘的水面上生长着浮萍;浮萍所占面积每天增加一倍;经过15天把池溏占满了;求它几天占池塘的12.一条幼虫长成成虫;每天长大一倍;40天长到20厘米;问第36天长多少厘米13.某人去银行取款;第一次取了存款的一半多5元;第二次取了余下的一半多10元;最后剩下125元;求他原来有多少元14.王大爷把他所有西瓜的一半又半个卖给第一个顾客;把余下的一半又半个卖给第二个顾客;……这样一直到他卖给第六个人以后;他一个西瓜也没有;求他原来有西瓜多少个---------------答案----------------------一、填空题1. 100×4+20-112÷4=772. 斗第三次见花前应有一斗;第三次遇店前应有斗;第二次见花前应有斗;第二次遇店前应有斗;第一次见花前应有斗;第一次遇店前应有斗.3. 甲:45辆;乙:90辆.把后来甲站所停汽车的辆数看为"1"的倍数;那么乙站所停的是1.5倍;那么"135"辆就是2.5倍;这样甲站后来有:135÷2.5=54辆乙站后来有:54×1.5=81辆甲原有:54+36-45=45辆乙原有:81+45-36=90辆4. 782吨.180+8×2+15×2=782吨5. 甲38粒;乙42粒;丙45粒;丁43粒. 现各有168÷4=42粒.甲:42-6+2=38乙:42-6+6=42丙:42-3+6=45 丁:42-2+3=43 6. 85个.1×4+1=5个5×4+1=21个21×4+1=85个7. 34个.3-1×2=4个4-1×2=6个6-1×2=10个10-1×2=18个18-1×2=34个8. 43÷……6位1999÷6=333 (1)所以是4.9. 设C数为M;则A=2M-2B=2M+2C=MD=4M9M=45;M=5∴A=8;B=12;C=5;D=20.10. 1994由于质数除2以外便都是奇数;奇数×奇数=奇数.所以其中一个质数定是2;1000以最大的质数是:997.997×2=1994二、解答题11. 第14天占 ;第13天占 .12. 39天长:40÷2=20厘米; 38天长:20÷2=10厘米;37天长:10÷2=5厘米;36天长:5÷2=2.5厘米.13. 125+10×2+5×2=550元14. 第七个人:0个;第六个人:0.5+0×2=1个; 第五个人:1+0.5×2=3个; 第四个人:3+0.5×2=7个; 第三个人:7+0.5×2=15个; 第二个人:15+0.5×2=31个; 第一个人:31+0.5×2=63个; 一共有:63+0.5×2=127个.。

7-6-4.计数之递推法教学目标前面在讲加法原理、乘法原理、排列组合时已经穿插讲解了计数中的一些常用的方法，比如枚举法、树形图法、标数法、捆绑法、排除法、插板法等等，这里再集中学习一下计数中其他常见的方法，主要有归纳法、整体法、对应法、递推法．对这些计数方法与技巧要做到灵活运用．例题精讲对于某些难以发现其一般情形的计数问题，可以找出其相邻数之间的递归关系，有了这一递归关系就可以利用前面的数求出后面未知的数，这种方法称为递推法．【例 1】每对小兔子在出生后一个月就长成大兔子，而每对大兔子每个月能生出一对小兔子来．如果一个人在一月份买了一对小兔子，那么十二月份的时候他共有多少对兔子？【考点】计数之递推法【难度】3星【题型】解答【解析】第一个月，有1对小兔子；第二个月，长成大兔子，所以还是1对；第三个月，大兔子生下一对小兔子，所以共有2对；第四个月，刚生下的小兔子长成大兔子，而原来的大兔子又生下一对小兔子，共有3对；第五个月，两对大兔子生下2对小兔子，共有5对；……这个特点的说明每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，所以每月的兔子数为上月的兔子数与上上月的兔子数相加．依次类推可以列出下表：经过月数：---1---2---3---4---5---6---7---8---9---10---11---12兔子对数：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的时候总共有144对兔子．【答案】144【例 2】树木生长的过程中，新生的枝条往往需要一段“休息”时间供自身生长，而后才能萌发新枝．一棵树苗在一年后长出一条新枝，第二年新枝“休息”，老枝依旧萌发新枝；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则依次“休息”．这在生物学上称为“鲁德维格定律”．那么十年后这棵树上有多少条树枝？【考点】计数之递推法【难度】3星【题型】解答【解析】一株树木各个年份的枝桠数，构成斐波那契数列：1，2，3，5，8，13，21，34，55，89，……所以十年后树上有89条树枝．【答案】89【例 3】一楼梯共10级，规定每步只能跨上一级或两级，要登上第10级，共有多少种不同走法？【考点】计数之递推法【难度】4星【题型】解答【解析】 登 1级 2级 3级 4级 ...... 10级1种方法 2种 3种 5种 ...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面两个数的和；依此规律我们就可以知道了第10级的种数是89.其实这也是加法的运用：假如我们把这个人开始登楼梯的位置看做A 0，那么登了1级的位置是在A 1，2级在A 2... A 10级就在A 10．到A 3的前一步有两个位置；分别是A 2 和A 1 ．在这里要强调一点，那么A 2 到A 3 既然是一步到了，那么A 2 、A 3之间就是一种选择了；同理A 1 到A 3 也是一种选择了．同时我们假设到n 级的选择数就是An ．那么从A 0 到A 3 就可以分成两类了：第一类：A 0 ---- A 1 ------ A 3 ，那么就可以分成两步．有A 1×1种，也就是A 1 种；(A 1 ------ A 3 是一种选择)第二类：A 0 ---- A 2 ------ A 3， 同样道理 有A 2 ．类类相加原理：A 3 = A 1 ＋A 2，依次类推An = An -1 + An -2． 【答案】89【巩固】一楼梯共10级，规定每步只能跨上一级或三级，要登上第10级，共有多少种不同走法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 登 1级 2级 3级 4级 5级 ...... 10级1种方法 1种 2种 3种 4种...... ？我们观察每级的种数，发现这么一个规律：从第三个数开始，每个数是前面相隔的两个数的和；依此规律我们就可以知道了第10级的种数是28.【答案】28【例 4】 1×2的小长方形(横的竖的都行)覆盖2×10的方格网，共有多少种不同的盖法．【考点】计数之递推法 【难度】4星 【题型】解答【解析】 如果用12⨯的长方形盖2n ⨯的长方形，设种数为n a ,则11a =，22a =,对于3n ≥，左边可能竖放1个12⨯的，也可能横放2个12⨯的，前者有-1n a 种，后者有-2n a 种，所以-1-2n n n a a a =+,所以根据递推，覆盖210⨯的长方形一共有89种．【答案】89【例 5】 用13⨯的小长方形覆盖38⨯的方格网，共有多少种不同的盖法？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果用13⨯的长方形盖3n ⨯的长方形，设种数为n a ,则11a =，21a =,32a =,对于4n ≥，左边可能竖放1个13⨯的，也可能横放3个13⨯的，前者有-1n a 种，后者有a 种，所以a a a =+,依照这条递推公式列表：【答案】13【例 6】 有一堆火柴共12根，如果规定每次取1～3根，那么取完这堆火柴共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1根火柴有1种方法，取2根火柴有2种方法，取3根火柴有4种取法，以后取任意根火柴的种数等于取到前三根火柴所有情况之和，以此类推，参照上题列表如【答案】927【巩固】 一堆苹果共有8个，如果规定每次取1～3个，那么取完这堆苹果共有多少种不同取法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 取1个苹果有1种方法，取2个苹果有2种方法，取3个苹果有4种取法，以后取任意个苹果的种数等于取到前三个苹果所有情况之和，以此类推，参照上题列表如【答案】81【例 7】 有10枚棋子，每次拿出2枚或3枚，要想将10枚棋子全部拿完，共有多少种不同的拿法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 本题可以采用递推法，也可以进行分类讨论，当然也可以直接进行枚举． (法1)递推法．假设有n 枚棋子，每次拿出2枚或3枚，将n 枚棋子全部拿完的拿法总数为n a 种．则21a =，31a =，41a =．由于每次拿出2枚或3枚，所以32n n n a a a --=+(5n ≥)．所以，5232a a a =+=；6342a a a =+=；7453a a a =+=；8564a a a =+=；9675a a a =+=；10787a a a =+=．即当有10枚棋子时，共有7种不同的拿法．(法2)分类讨论．由于棋子总数为10枚，是个偶数，而每次拿2枚或3枚，所以其中拿3枚的次数也应该是偶数．由于拿3枚的次数不超过3次，所以只能为0次或2次．若为0次，则相当于2枚拿了5次，此时有1种拿法；若为2次，则2枚也拿了2次，共拿了4次，所以此时有246C =种拿法． 根据加法原理，共有167+=种不同的拿法．【答案】7【例 8】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答BAA B 1357946821235813213455891【解析】 蜜蜂“每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行”这意味着它只能从小号码的蜂房爬近相邻大号码的蜂房．明确了行走路径的方向，就可以运用标数法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有89种不同的回家方法．【答案】89【巩固】小蜜蜂通过蜂巢房间，规定只能由小号房间进入大号房间问小蜜蜂由A 房间到达B房间有多少种方法？【考点】计数之递推法 【难度】4星 【题型】解答【解析】 斐波那契数列第八项．21种．86427531【答案】21【例 9】 如下图，一只蜜蜂从A 处出发，回到家里B 处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？【考点】计数之递推法 【难度】4星 【题型】解答BA【解析】 按照蜜蜂只能从小号码的蜂房爬近相邻大号码的蜂房的原则，运用标号法进行计算．如右图所示，小蜜蜂从A 出发到B 处共有296种不同的回家方法．【答案】296【例 10】 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1，如此进行直到得数为1操作停止．问经过9次操作变为1的数有多少个？【考点】计数之递推法 【难度】4星 【题型】解答【解析】可以先尝试一下，倒推得出下面的图：2410131112514302831643215167683421其中经1次操作变为1的1个，即2，经2次操作变为1的1个，即4，经3次操作变为1的2个，是一奇一偶，以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.为什么上面的规律是正确的呢？道理也很简单. 设经过n 次操作变为1的数的个数为n a ,则1a =1，2a =1，3a =2，… 从上面的图看出，1n a +比n a 大.一方面，每个经过n 次操作变为1的数，乘以2，就得出一个偶数，经过1n +次操作变为1；反过来，每个经过1n +次操作变为1的偶数，除以2，就得出一个经过n 次操作变为1的数. 所以经过n 次操作变为1的数与经过1n +次操作变为1的偶数恰好一样多.前者的个数是n a ,因此后者也是n a 个.另一方面，每个经过n 次操作变为1的偶数，减去1，就得出一个奇数，它经过1n +次操作变为1，反过来.每个经过1n +次操作变为1的奇数，加上1，就得出一个偶数，它经过n 次操作变为1. 所以经过n 次操作变为1的偶数经过1n +次操作变为1的奇数恰好一样多. 而由上面所说，前者的个数就是1n a -,因此后者也是1n a -.经过n +1次操作变为1的数，分为偶数、奇数两类，所以11n n n a a a +-=+，即上面所说的规律的确成立.【答案】34【例 11】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数）【考点】计数之递推法 【难度】5星 【题型】解答【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．【答案】25【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留下的棋子数不是3或4的倍数，有 种不同的方法取完这堆棋子.【考点】计数之递推法 【难度】5星 【题型】填空【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：【答案】54【例 12】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 设第n 次传球后，球又回到甲手中的传球方法有n a 种．可以想象前1n -次传球，如果每一次传球都任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有11333333n n --⨯⨯⨯=144424443()个…(种)传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第1n -次恰好传到甲手中，这有1n a -种传法，它们不符合要求，因为这样第n 次无法再把球传给甲；另一类是第1n -次传球，球不在甲手中，第n 次持球人再将球传给甲，有n a 种传法．根据加法原理，有11133333n n n n a a ---+=⨯⨯⨯=14444244443(个…)． 由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以10a =． 利用递推关系可以得到：2303a =-=，33336a =⨯-=，4333621a =⨯⨯-=，533332160a =⨯⨯⨯-=．这说明经过5次传球后，球仍回到甲手中的传球方法有60种．本题也可以列表求解．由于第n 次传球后，球不在甲手中的传球方法，第1n +次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．【答案】60【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共有多少种传球方式？【考点】计数之递推法 【难度】5星 【题型】解答【解析】 递推法．设第n 次传球后球传到甲的手中的方法有n a 种．由于每次传球有4种选择，传n 次有4n 次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有n a 种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有1n a +种．所以14n n n a a ++=．由于10a =，所以12144a a =-=，232412a a =-=，343452a a =-=．即经过4次传球后，球仍回到甲手中的传球方法有52种．【答案】52【例 13】 设A 、E 为正八边形ABCDEFGH 的相对顶点，顶点A 处有一只青蛙，除顶点E 外青蛙可以从正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E 时青蛙就停止跳动，则青蛙从顶点A 出发恰好跳10次后落到E 的方法总数为 种．【考点】计数之递推法 【难度】5星 【题型】填空【关键词】清华附中【解析】 可以使用递推法．回到A 跳到B 或H 跳到C 或G 跳到D 或F 停在E 1步 12步 2 13步 3 14步 6 4 25步 10 46步 20 14 87步 34 148步 68 48 289步 116 48其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来．所以，青蛙第10步跳到E 有48296⨯=种方法．【答案】96【巩固】在正五边形ABCDE 上，一只青蛙从A 点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D 点上就停止跳动．青蛙在6次之内(含6次)跳到D 点有 种不同跳法．【考点】计数之递推法 【难度】5星 【题型】填空AB C D E【解析】 采用递推的方法．列表如下：跳到A 跳到B 跳到C 停在D 跳到E1步 1 12步 2 1 13步 3 1 24步 5 3 25步 8 3 56步 13 8 5其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D 点上就停止跳动．所以，每一步跳到A 的跳法数等于上一步跳到B 和E 的跳法数之和，每一步跳到B 的跳法数等于上一步跳到A 和C 的跳法数之和，每一步跳到C 的跳法数等于上一步跳到B 的跳法数，每一步跳到E 的跳法数等于上一步跳到A 的跳法数，每一步跳到D 的跳法数等于上一步跳到C 或跳到E 的跳法数．观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内(含6次)跳到D 点共有1123512++++=种不同的跳法．【答案】12【例 14】 有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．【考点】计数之递推法 【难度】5星 【题型】填空【关键词】迎春杯，中年级组，决赛【解析】 (法1)分类讨论．如果1，2号箱中恰好放的就是1，2号箱的钥匙，显然不是“好”的方法，所以“好”的方法有两种情况：⑴1，2号箱的钥匙恰有1把在1，2号箱中，另一箱装的是3～6箱的钥匙．⑵1，2号箱的钥匙都不在1，2号箱中．对于⑴，从1，2号箱的钥匙中选1把，从3～6号箱的钥匙中选1把，共有248⨯=(种)选法，每一种选法放入1，2号箱各有2种放法，共有8216⨯=(种)放法．不妨设1，3号箱的钥匙放入了1，2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可知此时不同的放法有3216⨯⨯=(种)．所以，第⑴种情况有“好”的方法16696⨯=(种)．对于⑵，从3～6号箱的钥匙中选2把放入1，2号箱，有4312⨯=(种)放法．不妨设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号箱中，有224⨯=种放法；如果3，4号箱中有1把5，6号箱的钥匙，比如3，4号箱中放的是5，1号箱的钥匙，则只能是5号箱放6号箱的钥匙，6号箱放2号箱的钥匙，有212⨯=种放法；同理，3，4号箱放5，2号箱或6，1号箱或6，2号箱的钥匙，也各有2种放法． 所以，第⑵种情况有“好”的放法()1242222144⨯++++=(种)．所以“好”的方法共有96144240+=(种)．(法2)递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-． 所以，6542554543225!240a a a a ==⨯==⨯⨯⨯=⨯=L ，即好的方法总数为240种．【答案】240【巩固】有10个木箱，编号为1，2，3，……，10，每个箱子有一把钥匙，10把钥匙各不相同，每个箱子放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把10把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种．【考点】计数之递推法 【难度】5星 【题型】填空【解析】 递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为1k ，2k ，3k ，…，6k ．当箱子数为n (2n ≥)时，好的放法的总数为n a ．当2n =时，显然22a =(11k =，22k =或12k =，21k =)．当3n =时，显然33k ≠，否则第3个箱子打不开，从而13k =或23k =，如果13k =，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有2a 种；当23k =也是如此．于是2n =时的每一种情况对应13k =或23k =时的一种情况，这样就有3224a a ==．当4n ≥时，也一定有n k n ≠，否则第n 个箱子打不开，从而1k 、2k 、……、1n k -中有一个为n ，不论其中哪一个是n ，由于必须要把该箱子打开才能打开n 号箱子，所以可以将锁着这把钥匙的箱子与第n 号箱子看作1个箱子，于是还是锁着1k 、2k 、……、1n k -这()1n -把钥匙，需要撬开1，2两号箱子，所以每种情况都有1n a -种．所以()11n n a n a -=-． 所以，109829989876543229!=725760a a a a ==⨯==⨯⨯⨯⨯⨯⨯⨯=⨯L ，即好的方法总数为725760种．【答案】725760。

小学奥数之递推法(总19页) -CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除五年级下册奥数知识点：递推方法计数方法与技巧（递推法概念）计数方法与技巧（递推法例题）例1：的乘积中有多少个数字是奇数？分析与解答：如果我们通过计算找到答案比较麻烦，因此我们先从最简单的情况入手。

9×9＝81，有1个奇数；99×99＝99×(100－1)＝9900－99＝9801，有2个奇数；999×999＝999×(1000－1)＝99900－999＝998001，有3个奇数；……从而可知，999…999×999…999的乘积中共有10个奇数。

例题2：分析与解答：这道题我们可以采用分别求出每个数的立方是多少，再求和的方法来解答。

但是，这样计算的工作量比较大，我们可以从简单的情况开始研究。

例题3： 2000个学生排成一行，依次从左到右编上1～2000号，然后从左到右按一、二报数，报一的离开队伍，剩下的人继续按一、二报数，报一的离开队伍，…… 按这个规律如此下去，直至当队伍只剩下一人为止。

问：这时一共报了多少次最后留下的这个人原来的号码是多少分析与解答：难的不会想简单的，数大的不会想数小的。

我们先从这2000名同学中选出20人代替2000人进行分析，试着找出规律，然后再用这个规律来解题。

这20人第一次报数后共留下10人，因为20÷2＝10 ，这10人开始时的编号依次是：2、4、6、8、10、12、14、16、18、20，都是2的倍数。

第二次报数后共留下5人，因为10÷2＝5 ，这5人开始时的编号依次是： 4、8、12、16、20，都是4的倍数，也就是2×2的倍数。

第三次报数后共留下2人，因为5÷2＝2 ……1 ，这2人开始时的编号依次是： 8、16，都是8的倍数，也就是2×2×2的倍数。