遞推法

“琦琦養(yǎng)了1對小兔子，2個(gè)月之后小兔子就具備了繁殖能力，算是‘成年兔了。假設(shè)成年兔每個(gè)月生育1對幼崽，且兔子們都健康地活著，那么100個(gè)月后，一共生出了多少對大大小小的兔子呢？”嶺童小子一邊念題目，一邊抓腦袋——計(jì)算量這么大，啥時(shí)候才能算出來呀！

面對難題，他沒有放棄，而是繼續(xù)思考：1個(gè)月后幼崽1對，成年兔0對，兔子一共只有1對。2個(gè)月后幼崽剛成年，還不能生育小兔子，此時(shí)幼崽0對，成年兔1對，兔子總數(shù)為1對。3個(gè)月后，成年兔生育出1對幼崽，兔子總數(shù)為2對……

算到這里，嶺童小子開始“暈”了。

“能不能請星空幫忙呢？他的特點(diǎn)不就是運(yùn)算速度快嗎？”嶺童小子一邊嘟噥著一邊看向星空。星空默不作聲地看著他，似乎在說：“你怎么才想到我呀！”

有了小幫手，嶺童小子立刻拿出草稿紙，開始列表分析。

咦！嶺童小子從表格里發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象：從第3個(gè)月開始，每個(gè)月的兔子總數(shù)是前面2個(gè)月兔子總數(shù)的和。有辦法了！按捺住內(nèi)心的激動，嶺童小子開始敲打鍵盤——編程開始了！

時(shí)間一分一秒地過去，嶺童小子一點(diǎn)兒都不覺得累，終于——

“嘿嘿，我真聰明！一下子就計(jì)算出了兔子100個(gè)月后的總數(shù)。而且，不管你想知道哪個(gè)月的兔子總數(shù)，我都可以隨時(shí)告訴你！咱編寫的程序就是這么牛！”嶺童小子得意極了。

哈哈，嶺童小子真聰明，還會用表格分析數(shù)據(jù)。

從初始的一個(gè)或若干個(gè)數(shù)據(jù)出發(fā)，通過遞推關(guān)系逐步推進(jìn)，從而得到最終結(jié)果，這種求解問題的方法叫“遞推法”。在遞推問題中，每個(gè)數(shù)據(jù)都和它前面或后面的若干個(gè)數(shù)據(jù)有一定關(guān)聯(lián)，這種關(guān)聯(lián)可以通過“遞推關(guān)系式”來表示。

嶺童小子列出了每個(gè)月的兔子總數(shù)分別為：1、1、2、3、5、8、13、21、34……從中可以看出，它的遞推關(guān)系式為：當(dāng)月兔子總數(shù)=上個(gè)月的兔子總數(shù)+上上個(gè)月的兔子總數(shù)。

從第三項(xiàng)開始，每一項(xiàng)都是前兩項(xiàng)的和，這就形成了一個(gè)著名的數(shù)列——斐波那契數(shù)列。在編寫程序時(shí)，我們需要用到列表，用來存放每個(gè)月的兔子總數(shù)。嶺童小子很聰明，建立了一個(gè)名為“當(dāng)月兔子總數(shù)”的列表。

第一步，將第1個(gè)月的兔子數(shù)量1加入“當(dāng)月兔子總數(shù)”這個(gè)列表中。代碼見圖1。

第二步，將第2個(gè)月的兔子數(shù)量1繼續(xù)加入“當(dāng)月兔子總數(shù)”這個(gè)列表中。代碼見圖2。

第三步，把上個(gè)月的兔子總數(shù)與上上個(gè)月的兔子總數(shù)相加，將它們的和加入“當(dāng)月兔子總數(shù)”這個(gè)列表里。代碼見圖3。

將第三步循環(huán)，一步一步遞推，直到你需要知道的月份為止。這樣，我們就能得到最終的結(jié)果。

同學(xué)們，你們看懂了嗎？掃描下方的小程序碼，看看長沙市芙蓉區(qū)馬坡嶺小學(xué)的優(yōu)秀作品吧！

曹曉敏：湖南省特級教師，湖南省優(yōu)秀科技輔導(dǎo)員，長沙市首批卓越教師，長沙市骨干教師，長沙市芙蓉區(qū)馬坡嶺小學(xué)信息技術(shù)教師。