第三講遞推計(jì)數(shù)有許多計(jì)數(shù)問(wèn)題很復(fù)雜，直接處理比較困難，此時(shí)硬碰硬是不行的．一個(gè)比較有效的策略是退而求其次：先考慮該問(wèn)題的簡(jiǎn)單情形，看看簡(jiǎn)單情形如何處理；在解決了簡(jiǎn)單情形后，再考慮如何利用簡(jiǎn)單情形的結(jié)論來(lái)解決更復(fù)雜的問(wèn)題……這個(gè)由簡(jiǎn)單到復(fù)雜的推導(dǎo)過(guò)程就叫“遞推”．那如何利用“遞推法”來(lái)解決計(jì)數(shù)問(wèn)題呢？下面我們就來(lái)看幾個(gè)例子．老師給小高布置了12篇作文，規(guī)定他每天至少寫(xiě)1篇．如果小高每天最多能寫(xiě)3篇，那么共有多少種不同的完成方法？（小高每天只能寫(xiě)整數(shù)篇）

「分析」從簡(jiǎn)單情況入手，看看能否找到合適的突破口．如果老師只布置1篇作文，小高有多少種不同的完成方法？如果老師布置2篇作文，小高有多少種不同的完成方法？如果老師布置3篇、4篇、……小高又分別有多少種不同的完成方法？篇數(shù)由少到多，完成方法數(shù)也會(huì)逐漸變多，這其中有什么規(guī)律呢？

練習(xí)1、一個(gè)樓梯共有12級(jí)臺(tái)階，規(guī)定每步可以邁二級(jí)臺(tái)階或三級(jí)臺(tái)階．走完這12級(jí)臺(tái)階，共有多少種不同的走法？

用10個(gè)的長(zhǎng)方形紙片覆蓋一個(gè)的方格表，共有多少種覆蓋方法？「分析」與例1的類(lèi)似，我們還是從簡(jiǎn)單情形入手找遞推關(guān)系．可具體從什么樣的情形入手呢？

練習(xí)2、用7個(gè)的長(zhǎng)方形紙片覆蓋一個(gè)的方格表，共有多少種覆蓋方法？

在一個(gè)平面上畫(huà)出100條直線(xiàn)，最多可以把平面分成幾個(gè)部分？

「分析」當(dāng)直線(xiàn)數(shù)量不多時(shí)，畫(huà)圖數(shù)一數(shù)即可．但現(xiàn)在有100條，畫(huà)圖數(shù)并不現(xiàn)實(shí)．我們不妨在紙上將直線(xiàn)逐一畫(huà)出，并在畫(huà)的過(guò)程中仔細(xì)觀(guān)察：每增加一條直線(xiàn)，平面被分成的部分會(huì)增加多少？這個(gè)增量有什么變化規(guī)律？

練習(xí)3、如果在一個(gè)圓內(nèi)畫(huà)出50條直線(xiàn)，最多可以把圓分成多少部分？

下面我們來(lái)學(xué)習(xí)一類(lèi)很經(jīng)典的遞推計(jì)數(shù)問(wèn)題——傳球問(wèn)題．

四個(gè)人分別穿著紅、黃、綠、藍(lán)四種顏色的球衣練習(xí)傳球，每人都可以把球傳給另外三個(gè)人中的任意一個(gè)．先由紅衣人發(fā)球，并作為第1次傳球，經(jīng)過(guò)8次傳球后球仍然回到紅衣人手中．請(qǐng)問(wèn)：整個(gè)傳球過(guò)程共有多少種不同的可能？

「分析」看到這個(gè)問(wèn)題，很多同學(xué)可能想通過(guò)樹(shù)形圖來(lái)求解，我們不妨來(lái)試一試．設(shè)穿著紅、黃、綠、藍(lán)四種顏色球衣的人分別是A、B、C、D．如下圖，最開(kāi)始時(shí)，球在A(yíng)手上，第一次傳球由A傳給B、C、D，也就是第一層有三個(gè)字母就夠了．然后B、C、D都會(huì)繼續(xù)往下傳球，各有3種傳法，傳到第二層需要9個(gè)字母．再傳到第三層，需要27個(gè)字母……每一層需要的字母增加迅猛！如果傳8次球，到最后一層會(huì)用到個(gè)字母，這要多大的一個(gè)樹(shù)形圖啊！

BCBCDACDABDABCABCDABDABCBCDACDABCBCDACDABD可見(jiàn)畫(huà)樹(shù)形圖的方案不可行．但樹(shù)形圖對(duì)這道題就沒(méi)有用了嗎？并非如此．它可以幫助我們找出傳球過(guò)程中所隱藏的遞推關(guān)系．事實(shí)上，我們并不關(guān)心樹(shù)形圖長(zhǎng)啥樣，我們關(guān)心的是數(shù)量——樹(shù)形圖每一層分支的數(shù)量．因此，只要知道每一層各字母出現(xiàn)的次數(shù)就可以了，我們不妨制作一個(gè)表格來(lái)統(tǒng)計(jì)這個(gè)次數(shù)．如下表，我們用第一列來(lái)表示層數(shù)，第一行來(lái)表示每個(gè)人，其余空格用于填寫(xiě)字母在該層中出現(xiàn)的次數(shù)．請(qǐng)你從上方的樹(shù)形圖中數(shù)一數(shù)，填出表格中的前幾行．然后思考一下：這其中隱藏著什么樣的遞推關(guān)系？ABCD012345678ABCD012345678解傳球問(wèn)題的方法稱(chēng)為“傳球法”．“傳球法”是遞推法的一種特殊形式，是一種極其實(shí)用的數(shù)表累加計(jì)數(shù)法．

一個(gè)七位數(shù)，每一位都是1、2或者3，而且沒(méi)有連續(xù)的兩個(gè)1，這樣的七位數(shù)一共有多少個(gè)？

「分析」這道題與前面兩道題有何異同？應(yīng)該如何求解呢？

前面的計(jì)數(shù)問(wèn)題，遞推關(guān)系都表現(xiàn)為數(shù)列、數(shù)表的簡(jiǎn)單累加，但這不是遞推的全部．簡(jiǎn)單累加只是遞推的一種表現(xiàn)形式，遞推還有很多其它形式．下面我們就來(lái)看一道無(wú)法通過(guò)簡(jiǎn)單累加求解的計(jì)數(shù)問(wèn)題．

圓周上有10個(gè)點(diǎn)A1、A2、、A10，以這些點(diǎn)為端點(diǎn)連接5條線(xiàn)段，要求線(xiàn)段之間沒(méi)有公共點(diǎn)，共有多少種連接方式？

「分析」圓周上10個(gè)點(diǎn)，連5條線(xiàn)段，連法很多，很難直接畫(huà)出來(lái)枚舉．像這類(lèi)問(wèn)題，我們同樣還是從簡(jiǎn)單的情況入手．那么是應(yīng)該按1個(gè)點(diǎn)、2個(gè)點(diǎn)、3個(gè)點(diǎn)、……這樣依次計(jì)數(shù)，來(lái)找遞推關(guān)系嗎？神奇的漢諾塔神奇的漢諾塔一位法國(guó)數(shù)學(xué)家曾編寫(xiě)過(guò)一個(gè)印度的古老傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針．印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔．不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面．僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡．不管這個(gè)傳說(shuō)的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序．這需要多少次移動(dòng)呢?這里需要遞歸的方法．假設(shè)有n片，移動(dòng)次數(shù)是．顯然，，，且．此后不難證明．時(shí)，．假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，計(jì)算一下，18446744073709551615/31556952=584554049253.855年．這表明移完這些金片需要5845億年以上，而地球存在至今不過(guò)45億年，太陽(yáng)系的預(yù)期壽命據(jù)說(shuō)也就是數(shù)百億年．真的過(guò)了5845億年，不說(shuō)太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅．課堂內(nèi)外

作業(yè)有10個(gè)蛋黃派，萱萱每天吃1個(gè)或2個(gè)，那么共有多少種不同的吃法？

甲、乙兩人玩抓石子游戲，共有12個(gè)石子，甲先乙后輪流抓?。看慰梢宰ト∑渲械?個(gè)、3個(gè)或4個(gè)，直到最后抓取完畢為止．那么共有多少種抓取石子的方案？

用直線(xiàn)把一個(gè)平面分成100部分，至少要在平面上畫(huà)幾條直線(xiàn)？

一個(gè)七位數(shù)，它由數(shù)字0、1、2、3、4組成，相鄰位置上的數(shù)字不相同，并且個(gè)位數(shù)字是2．這樣的七位數(shù)有多少個(gè)？

用8個(gè)的長(zhǎng)方形紙片覆蓋下面的方格表，共有多少種覆蓋方法？

第五講進(jìn)位制問(wèn)題例題：答案：（1）31023、3735、11B9、7DD；（2）257；（3）1742詳解：（1）

52013……35402……2580……1516……52013……35402……2580……1516……053……382013……28251……3831……783……3122013……912167……121213……1121……1162013……1316125……13167……7答案：（1）5；（2）13121、731詳解：三進(jìn)制轉(zhuǎn)九進(jìn)制從右往左兩位兩位轉(zhuǎn)換；二進(jìn)制轉(zhuǎn)四進(jìn)制從右往左兩位兩位轉(zhuǎn)換；二進(jìn)制轉(zhuǎn)八進(jìn)制從右往左三位三位轉(zhuǎn)換．

答案：15031

詳解：列豎式計(jì)算．答案：212．a(chǎn)=5、b=5、c=2

答案：10個(gè)

詳解：若要稱(chēng)量1克的重量必須有1克的砝碼，若要稱(chēng)量2克的重量必須有2克的砝碼，依次類(lèi)推可得：1+2+4+8+16+32+64+128+256+512，此時(shí)可以稱(chēng)量1克到1023克的所有重量，此時(shí)需要10個(gè)砝碼．

答案：12

詳解：所看頁(yè)數(shù)列為1、1、2、4、8、……、256、512、989．練習(xí)：答案：554；2781；195；722

答案：16157

答案：21234

答案：248．a(chǎn)=5、b=0、c=3

作業(yè)：答案：（1）354；（2）458；（3）C30；（4）14443；（5）433；（6）85

答案：（1）1131；（2）12312

答案：1