高斯小學奧數(shù)六年級上冊含答案第03講-遞推計數(shù)

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

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

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

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

練習2、用7個的長方形紙片覆蓋一個的方格表，共有多少種覆蓋方法？

在一個平面上畫出100條直線，最多可以把平面分成幾個部分？

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

練習3、如果在一個圓內畫出50條直線，最多可以把圓分成多少部分？

下面我們來學習一類很經典的遞推計數(shù)問題——傳球問題．

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

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

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

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

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

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

圓周上有10個點A1、A2、、A10，以這些點為端點連接5條線段，要求線段之間沒有公共點，共有多少種連接方式？

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

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

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

用直線把一個平面分成100部分，至少要在平面上畫幾條直線？

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

用8個的長方形紙片覆蓋下面的方格表，共有多少種覆蓋方法？

第五講進位制問題例題：答案：（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詳解：三進制轉九進制從右往左兩位兩位轉換；二進制轉四進制從右往左兩位兩位轉換；二進制轉八進制從右往左三位三位轉換．

答案：15031

詳解：列豎式計算．答案：212．a=5、b=5、c=2

答案：10個

詳解：若要稱量1克的重量必須有1克的砝碼，若要稱量2克的重量必須有2克的砝碼，依次類推可得：1+2+4+8+16+32+64+128+256+512，此時可以稱量1克到1023克的所有重量，此時需要10個砝碼．

答案：12

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

答案：16157

答案：21234

答案：248．a=5、b=0、c=3

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

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

答案：1