小學奧數(shù)計數(shù)之遞推法(完整版)

小學奧數(shù)計數(shù)之遞推法小學奧數(shù)計數(shù)之遞推法

7-6-4.計數(shù)之遞推法7-6-4.計數(shù)之遞推法教學目標教學目標前面在講加法原理、乘法原理、排列組合時已經(jīng)穿插講解了計數(shù)中的一些常用的方法，比如枚舉法、樹形圖法、標數(shù)法、捆綁法、排除法、插板法等等，這里再集中學習一下計數(shù)中其他常見的方法，主要有歸納法、整體法、對應(yīng)法、遞推法．對這些計數(shù)方法與技巧要做到靈活運用．例題精講例題精講對于某些難以發(fā)現(xiàn)其一般情形的計數(shù)問題，可以找出其相鄰數(shù)之間的遞歸關(guān)系，有了這一遞歸關(guān)系就可以利用前面的數(shù)求出后面未知的數(shù)，這種方法稱為遞推法．每對小兔子在出生后一個月就長成大兔子，而每對大兔子每個月能生出一對小兔子來．如果一個人在一月份買了一對小兔子，那么十二月份的時候他共有多少對兔子？【考點】計數(shù)之遞推法【難度】3星【題型】解答第一個月，有1對小兔子；第二個月，長成大兔子，所以還是1對；第三個月，大兔子生下一對小兔子，所以共有2對；第四個月，剛生下的小兔子長成大兔子，而原來的大兔子又生下一對小兔子，共有3對；第五個月，兩對大兔子生下2對小兔子，共有5對；……這個特點的說明每月的大兔子數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，即上上月的兔子數(shù)，所以每月的兔子數(shù)為上月的兔子數(shù)與上上月的兔子數(shù)相加．依次類推可以列出下表：經(jīng)過月數(shù)：---1---2---3---4---5---6---7---8---9---10---11---12兔子對數(shù)：---1---1---2---3---5---8--13--21--34--55--89—144，所以十二月份的時候總共有144對兔子．【答案】樹木生長的過程中，新生的枝條往往需要一段“休息”時間供自身生長，而后才能萌發(fā)新枝．一棵樹苗在一年后長出一條新枝，第二年新枝“休息”，老枝依舊萌發(fā)新枝；此后，老枝與“休息”過一年的枝同時萌發(fā)，當年生的新枝則依次“休息”．這在生物學上稱為“魯?shù)戮S格定律”．那么十年后這棵樹上有多少條樹枝？【考點】計數(shù)之遞推法【難度】3星【題型】解答一株樹木各個年份的枝椏數(shù)，構(gòu)成斐波那契數(shù)列：1，2，3，5，8，13，21，34，55，89，……所以十年后樹上有89條樹枝．【答案】一樓梯共10級，規(guī)定每步只能跨上一級或兩級，要登上第10級，共有多少種不同走法？【考點】計數(shù)之遞推法【難度】4星【題型】解答登1級

2級

3級

4級

......

10級1種方法

2種

3種

5種

......

？我們觀察每級的種數(shù)，發(fā)現(xiàn)這么一個規(guī)律：從第三個數(shù)開始，每個數(shù)是前面兩個數(shù)的和；依此規(guī)律我們就可以知道了第10級的種數(shù)是89.其實這也是加法的運用：假如我們把這個人開始登樓梯的位置看做A0，那么登了1級的位置是在A1，2級在A2...A10級就在A10．到A3的前一步有兩個位置；分別是A2和A1．在這里要強調(diào)一點，那么A2到A3

既然是一步到了，那么A2、A3之間就是一種選擇了；同理A1到A3也是一種選擇了．同時我們假設(shè)到n級的選擇數(shù)就是An．那么從A0到A3就可以分成兩類了：第一類：A0----A1------A3，那么就可以分成兩步．有A1×1種，也就是A1

種；(A1------A3是一種選擇)第二類：A0----A2------A3，同樣道理有A2

．類類相加原理：A3=A1＋A2，依次類推An=An-1+An-2．【答案】【鞏固】一樓梯共10級，規(guī)定每步只能跨上一級或三級，要登上第10級，共有多少種不同走法？【考點】計數(shù)之遞推法【難度】4星【題型】解答登1級

2級

3級

4級

5級......

10級1種方法

1種

2種

3種

4種......

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