【正文】 級，規(guī)定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 登 1級 ...... ...... ？我們觀察每級的種數，發(fā)現(xiàn)這么一個規(guī)律：從第三個數開始，每個數是前面兩個數的和；：假如我們把這個人開始登樓梯的位置看做A0，那么登了1級的位置是在A1，2級在A2... A10級就在A10．到A3的前一步有兩個位置；分別是A2 和A1 ．在這里要強調一點，那么A2 到A3 種；(A1 A3 是一種選擇)第二類：A0 A2 A3， 同樣道理 有A2 5級 ...... 4種...... ？我們觀察每級的種數，發(fā)現(xiàn)這么一個規(guī)律：從第三個數開始，每個數是前面相隔的兩個數的和；依此規(guī)律我們就可以知道了第10級的種數是28.【答案】【例 4】 12的小長方形(橫的豎的都行)覆蓋210的方格網，共有多少種不同的蓋法．【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 如果用的長方形蓋的長方形，設種數為,則，,對于，左邊可能豎放1個的，也可能橫放2個的，前者有種，后者有種，所以,所以根據遞推，覆蓋的長方形一共有89種．【答案】【例 5】 用的小長方形覆蓋的方格網，共有多少種不同的蓋法？【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 如果用的長方形蓋的長方形，設種數為,則，,對于，左邊可能豎放1個的，也可能橫放3個的，前者有種，后者有種，所以,依照這條遞推公式列表：112346913所以用的小長方形形覆蓋的方格網，共有13種不同的蓋法．【答案】【例 6】 有一堆火柴共12根，如果規(guī)定每次取1～3根，那么取完這堆火柴共有多少種不同取法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 取1根火柴有1種方法，取2根火柴有2種方法，取3根火柴有4種取法，以后取任意根火柴的種數等于取到前三根火柴所有情況之和，以此類推，參照上題列表如下：1根2根3根4根5根6根7根8根9根10根11根12根124713244481149274504927取完這堆火柴一共有927種方法．【答案】【鞏固】 一堆蘋果共有8個，如果規(guī)定每次取1～3個，那么取完這堆蘋果共有多少種不同取法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 取1個蘋果有1種方法，取2個蘋果有2種方法，取3個蘋果有4種取法，以后取任意個蘋果的種數等于取到前三個蘋果所有情況之和，以此類推，參照上題列表如下：1個2個3個4個5個6個7個8個124713244481取完這堆蘋果一共有81種方法．【答案】【例 7】 有10枚棋子，每次拿出2枚或3枚，要想將10枚棋子全部拿完，共有多少種不同的拿法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 本題可以采用遞推法，也可以進行分類討論，當然也可以直接進行枚舉．(法1)遞推法．假設有枚棋子，每次拿出2枚或3枚，將枚棋子全部拿完的拿法總數為種．則，．由于每次拿出2枚或3枚，所以()．所以，；；；；；．即當有10枚棋子時，共有7種不同的拿法．(法2)分類討論．由于棋子總數為10枚，是個偶數，而每次拿2枚或3枚，所以其中拿3枚的次數也應該是偶數．由于拿3枚的次數不超過3次，所以只能為0次或2次．若為0次，則相當于2枚拿了5次，此時有1種拿法；若為2次，則2枚也拿了2次，共拿了4次，所以此時有種拿法．根據加法原理，共有種不同的拿法．【答案】【例 8】 如下圖，一只蜜蜂從處出發(fā)，回到家里處，每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆行，共有多少種回家的方法？【考點】計數之遞推法 【難度】4星 【題型】解答 【解析】 蜜蜂“每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆行”這意味著它只能從小號碼的蜂房爬近相鄰大號碼的蜂房．明確了行走路徑的方向，就可以運用標數法進行計算．如右圖所示，小蜜蜂從A出發(fā)到B處共有89種不同的回家方法．【答案】【鞏固】小蜜蜂通過蜂巢房間，規(guī)定只能由小號房間進入大號房間問小蜜蜂由房間到達 房間有多少種方法？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 斐波那契數列第八項．21種．【答案】【例 9】 如下圖，一只蜜蜂從A處出發(fā)，回到家里B處，每次只能從一個蜂房爬向右側鄰近的蜂房而不準逆行，共有多少種回家的方法？【考點】計數之遞推法 【難度】4星 【題型】解答 【解析】 按照蜜蜂只能從小號碼的蜂房爬近相鄰大號碼的蜂房的原則，運用標號法進行計算．如右圖所示，小蜜蜂從A出發(fā)到B處共有296種不同的回家方法．【答案】【例 10】 對一個自然數作如下操作：如果是偶數則除以2，如果是奇數則加1，如此進行直到得數為1操作停止．問經過9次操作變?yōu)?的數有多少個？【考點】計數之遞推法 【難度】4星 【題型】解答【解析】 可以先嘗試一下，倒推得出下面的圖：其中經1次操作變?yōu)?的1個，即2，經2次操作變?yōu)?的1個，即4，經3次操作變?yōu)?的2個，是一奇一偶，以后發(fā)現(xiàn)，每個偶數可以變成兩個數，分別是一奇一偶，每個奇數變?yōu)橐粋€偶數，于是，經…次操作變?yōu)?的數的個數依次為：1，1，2，3，5，8，… 這一串數中有個特點：自第三個開始，每一個等于前兩個的和，即即經過9次操作變?yōu)?的數有34個.為什么上面的規(guī)律是正確的呢？道理也很簡單. 設經過次操作變?yōu)?的數的個數為,則1，1，2，…從上面的圖看出，比大. 一方面，每個經過次操作變?yōu)?的數，乘以2，就得出一個偶數，經過次操作變?yōu)?；反過來，每個經過次操作變?yōu)?的偶數，除以2，就得出一個經過次操作變?yōu)?的數. ,因此后者也是個.另一方面，每個經過次操作變?yōu)?的偶數，減去1，就得出一個奇數，它經過次操作變?yōu)?，加上1，就得出一個偶數，它經過次操作變?yōu)?. 所以經過次操作變?yōu)?的偶數經過次操作變?yōu)?的奇數恰好一樣多.而由上面所說，前者的個數就是,因此后者也是.經過1次操作變?yōu)?的數，分為偶數、奇數兩類，所以，即上面所說的規(guī)律的確成立.【答案】【例 11】 有20個石子，一個人分若干次取，每次可以取1個，2個或3個，但是每次取完之后不能留下質數個，有多少種方法取完石子？（石子之間不作區(qū)分，只考慮石子個數）【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 如果沒有剩下的不能使質數這個條件，那么遞推方法與前面學過的遞推法相似，只不過每次都是前面3個數相加．現(xiàn)在剩下的不能是質數個，可以看作是質數個的取法總數都是0，然后再進行遞推．【答案】【鞏固】有20個相同的棋子，一個人分若干次取，每次可取1個，2個，3個或4個，但要求每次取之后留下的棋子數不是3或4的倍數，有 種不同的方法取完這堆棋子. 【考點】計數之遞推法 【難度】5星 【題型】填空【解析】 把0和20以內不是3或4的倍數的數寫成一串，用遞推法把所有的方法數寫出來：【答案】【例 12】 個人進行籃球訓練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方法？【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 設第次傳球后，球又回到甲手中的傳球方法有種．可以想象前次傳球，如果每一次傳球都任選其他三人中的一人進行傳球，即每次傳球都有種可能，由乘法原理，共有(種)傳球方法．這些傳球方法并不是都符合要求的，它們可以分為兩類，一類是第次恰好傳到甲手中，這有種傳法，它們不符合要求，因為這樣第次無法再把球傳給甲；另一類是第次傳球，球不在甲手中，第次持球人再將球傳給甲，有種傳法．根據加法原理，有．由于甲是發(fā)球者，一次傳球后球又回到甲手中的傳球方法是不存在的，所以．利用遞推關系可以得到：，．這說明經過次傳球后，球仍回到甲手中的傳球方法有種．本題也可以列表求解．由于第次傳球后，球不在甲手中的傳球方法，第次傳球后球就可能回到甲手中，所以只需求出第四次傳球后，球不在甲手中的傳法共有多少種．從表中可以看出經過五次傳球后，球仍回到甲手中的傳球方法共有種．【答案】【鞏固】五個人互相傳球，由甲開始發(fā)球，并作為第一次傳球，經過次傳球后，球仍回到甲手中．問：共有多少種傳球方式？【考點】計數之遞推法 【難度】5星 【題型】解答【解析】 遞推法．設第次傳球后球傳到甲的手中的方法有種．由于每次傳球有4種選擇，傳次有次可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有種，球不在甲的手中的，下一次傳球都可以將球傳到甲的手中，故有種．所以．由于，所以，．即經過次傳球后，球仍回到甲手中的傳球方法有52種．【答案】【例 13】 設、為正八邊形的相對頂點，頂點處有一只青蛙，除頂點外青蛙可以從正八邊形的任一頂點跳到其相鄰兩個頂點中任意一個，落到頂點時青蛙就停止跳動，則青蛙從頂點出發(fā)恰好跳次后落到的方法總數為 種．【考點】計數之遞推法 【難度】5星 【題型】填空【關鍵詞】清華附中【解析】 可以使用遞推法． 回到 跳到或 跳到或 跳到或 停在1步 12步 2 13步 3 14步 6 4 25步 10 46步 20 14 87步 34 148步 68 48 289步 116 48其中，第一列的每一個數都等于它的上一行的第二列的數的2倍，第二列的每一個數都等于它的上一行的第一列和第三列的兩個數的和，第三列的每一個數都等于它的上一行的第二列和第四列的兩個數的和，第四列的每一個數都等于它的上一行的第三列的數，第五列的每一個數都等于都等于它的上一行的第四列的數的2倍．這一規(guī)律很容易根據青蛙的跳動規(guī)則分析得來．所以，青蛙第10步跳到有種方法．【答案】【鞏固】在正五邊形上，一只青蛙從點開始跳動，它每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到點上就停止跳動．青蛙在6次之內(含6次)跳到點有 種不同跳法．【考點】計數之遞推法 【難度】5星 【題型】填空【解析】 采用遞推的方法．列表如下： 跳到 跳到 跳到 停在 跳到1步 1 12步 2 1 13步 3 1 24步 5 3 25步 8 3 56步 13 8 5其中，根據規(guī)則，每次可以隨意跳到相鄰兩個頂點中的一個上，一旦跳到點上就停止跳動．所以，每一步跳到的跳法數等于上一步跳到和的跳法數之和，每一步跳到的跳法數等于上一步跳到和的跳法數之和，每一步跳到的跳法數等于上一步跳到的跳法數，每一步跳到的跳法數等于上一步跳到的跳法數，每一步跳到的跳法數等于上一步跳到或跳到的跳法數．觀察可知，上面的遞推結果與前面的枚舉也相吻合，所以青蛙在6次之內(含6次)跳到點共有種不同的跳法．【答案】【例 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把，共有(種)選法，每一種選法放入1，2號箱各有2種放法，共有(種)放法．不妨設1，3號箱的鑰匙放入了1，2號箱，此時3號箱不能裝2號箱的鑰匙，有3種選法，依次類推，可知此時不同的放法有(種)．所以，第⑴種情況有“好”的方法(種)．對于⑵，從3～6號箱的鑰匙中選2把放入1，2號箱，有(種)放法．不妨設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號箱中，有種放法；如果3，4號箱中有1把5，6號箱的鑰匙，比如3，4號箱中放的是5，1號箱的鑰匙，則只能是5號箱放6號箱的鑰匙，6號箱放2號箱的鑰匙，有種放法；同理，3，4號箱放5，2號箱或6，1號箱或6，2號箱的鑰匙，也各有2種放法．所以，第⑵種情況有“好”的放法(種)．所以“好”的方法共有(種)．(法2)遞推法．設第1，2，3，…，6號箱子中所放的鑰匙號碼依次為，…，．當箱子數為()時，好的放法的總數為．當時，顯然(，或，)．當時，顯然，否則第3個箱子打不開，從而或，如果，則把1號箱