遞推法

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

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

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

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

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

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

時間一分一秒地過去，嶺童小子一點兒都不覺得累，終于——

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

哈哈，嶺童小子真聰明，還會用表格分析數據。

從初始的一個或若干個數據出發，通過遞推關系逐步推進，從而得到最終結果，這種求解問題的方法叫“遞推法”。在遞推問題中，每個數據都和它前面或后面的若干個數據有一定關聯，這種關聯可以通過“遞推關系式”來表示。

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

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

第一步，將第1個月的兔子數量1加入“當月兔子總數”這個列表中。代碼見圖1。

第二步，將第2個月的兔子數量1繼續加入“當月兔子總數”這個列表中。代碼見圖2。

第三步，把上個月的兔子總數與上上個月的兔子總數相加，將它們的和加入“當月兔子總數”這個列表里。代碼見圖3。

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

同學們，你們看懂了嗎？掃描下方的小程序碼，看看長沙市芙蓉區馬坡嶺小學的優秀作品吧！

曹曉敏：湖南省特級教師，湖南省優秀科技輔導員，長沙市首批卓越教師，長沙市骨干教師，長沙市芙蓉區馬坡嶺小學信息技術教師。