Fibonacci數(shù)列在遞歸與動態(tài)規(guī)劃算法教學(xué)中的應(yīng)用

李勝華

摘要：遞歸與動態(tài)規(guī)劃算法是算法設(shè)計與分析課程中培養(yǎng)學(xué)生計算思維、提高解決實際問題能力的兩類主要算法。為了減小學(xué)生理解這兩類抽象算法設(shè)計方法的難度，提高學(xué)習(xí)興趣，文章討論了將同一Fibonacci數(shù)列作為案例應(yīng)用于它們的教學(xué)方案。基于該數(shù)列與這兩個教學(xué)內(nèi)容的內(nèi)部聯(lián)系，通過實施案例分析、討論交流、設(shè)計求解、比較總結(jié)的方法進行教學(xué)。教學(xué)實踐結(jié)果表明：學(xué)生不僅較容易地掌握了這兩個算法設(shè)計方法的基本框架、本質(zhì)區(qū)別及算法分析方法，而且提高了專業(yè)知識理解力及計算思維修養(yǎng)。

關(guān)鍵詞：算法設(shè)計與分析；遞歸；動態(tài)規(guī)劃；案例教學(xué)；Fibonacci序列；計算思維

中圖分類號：G642? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2023）01-0157-03

1 引言

“新工科”背景下，高校越來越多專業(yè)開設(shè)算法設(shè)計類課程，旨在加強計算思維的培養(yǎng)?！坝嬎闼季S”是美國卡內(nèi)基梅隆大學(xué)周以真（Jeannette M. Wing）教授2006年在ACM會刊首次定義[1]：運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計和人類行為理解等覆蓋計算機科學(xué)之廣度的一系列思維活動。從此計算不再只是編程，而是解決問題的思維，每個人必備的基本技能——能運用計算思維更有效率地解決各種問題。一般來說，計算思維中最重要的幾個思維過程是抽象、分解以及組合。遞歸算法和動態(tài)規(guī)劃算法設(shè)計方法是算法設(shè)計與分析課程的兩個基本教學(xué)內(nèi)容[2]，它們能很好地體現(xiàn)計算思維的過程。

計算機算法設(shè)計理論較抽象、實踐綜合能力要求高，學(xué)生在理論、實踐及應(yīng)用三個方面有效融合有很大難度，有畏難情緒。為改善教學(xué)效果，近些年對算法設(shè)計與分析課程的教學(xué)改革研究較多[3-5]。但大部分改革對教學(xué)條件要求較高，有些高?；?qū)I(yè)不具備，實施有難度。毋庸置疑“算法”本身理論要求較高，實踐輔助理論理解和提高。但相當部分同學(xué)課堂上的基本理論理解不夠重視，造成后面應(yīng)用實踐費時甚至錯誤。根據(jù)多年的教學(xué)經(jīng)驗，課堂上采用案例教學(xué)法有助于學(xué)生專業(yè)知識銜接、理論理解、課堂交流和思維創(chuàng)新等。“案例教學(xué)法”于1870年哈佛大學(xué)法學(xué)院提出，1921年在哈佛大學(xué)商學(xué)院正式推行，1986年美國卡內(nèi)基小組（Carnegie Task Force）的報告書特別推薦案例教學(xué)法在師資培育課程的價值[6]。從此，“案例教學(xué)法”被視為一種相當有效的教學(xué)模式，我國也有眾多學(xué)者[7-10]從事這方面的研究和實踐。

“案例教學(xué)法”中選取的案例應(yīng)是學(xué)生有認知基礎(chǔ)的，與教學(xué)內(nèi)容有內(nèi)部聯(lián)系，并有助學(xué)生專業(yè)素質(zhì)培養(yǎng)。遞歸與動態(tài)規(guī)劃兩類算法設(shè)計與遞歸方程有緊密聯(lián)系，本文將選取起源遞歸方程（1）的Fibonacci數(shù)列作為二者的入門教學(xué)案例，重點討論相關(guān)的案例演示、案例分析、案例設(shè)計、歸納總結(jié)等幾個主要環(huán)節(jié)的教學(xué)過程。

2? Fibonacci序列

3 遞歸算法設(shè)計教學(xué)過程

遞歸是一種重要的算法設(shè)計方法，遞歸算法結(jié)構(gòu)簡潔清晰、便于算法正確性證明和算法分析。教學(xué)目標是能抽象實際問題的遞歸關(guān)系，掌握遞歸設(shè)計模型和遞歸算法分析。與此相關(guān)的知識點為問題遞歸轉(zhuǎn)化、遞歸算法框架、遞歸方程求解。

3.1 案例演示

提出兔子問題。Fibonacci序列在小學(xué)生找數(shù)列規(guī)律及中學(xué)生寫數(shù)列通項時遇到過，但該數(shù)列來源的實際問題大部分學(xué)生并不了解。通過上述有趣故事的引入，激發(fā)學(xué)生學(xué)習(xí)興趣。

3.2 案例分析

分析每月兔子來源，引導(dǎo)學(xué)生建立遞歸模型求解，培養(yǎng)計算思維：抽象——數(shù)列，分解——新老兔子數(shù)，組合——相加。學(xué)生通過自主學(xué)習(xí)或相互交流得出Fibonacci序列和遞歸方程（1）?；趯W(xué)生“高級語言程序設(shè)計”的基礎(chǔ)，先鼓勵學(xué)生利用循環(huán)結(jié)構(gòu)進行算法設(shè)計，見算法1。在課堂上能順利寫出算法1的同學(xué)并不多，原因是相當部分同學(xué)對程序變量的理解不透徹，導(dǎo)致循環(huán)修改部分容易出錯。進而提出該問題遞歸算法的設(shè)計和分析要求。

算法1? int Fib1（int n）

{if（n<=2）return 1;

int? i， a，b， c;

a=1， b=1; //循環(huán)初值部分

for（i=3; i<=n; i++）

{? ?c=a+b; //循環(huán)工作部分

a=b; b=c;? //循環(huán)修改部分

}return c;

}

3.3 案例設(shè)計

程序設(shè)計高級語言都支持遞歸函數(shù)，將問題抽象成數(shù)學(xué)遞歸方程，再由遞歸方程轉(zhuǎn)換遞歸函數(shù)相對于循環(huán)算法邏輯清晰簡單。

1） 遞歸算法框架

根據(jù)方程（1）講解遞歸模型：遞歸出口、遞歸轉(zhuǎn)換，以及遞歸函數(shù)的算法框架。學(xué)生通過相互交流，能很好地將遞歸方程與遞歸函數(shù)統(tǒng)一，得到算法2。

算法2? int Fib2（int n）

{if（n<=2） rerun 1; //遞歸出口

return Fib2（n-1）+Fib2（n-2）; //遞歸轉(zhuǎn)換

}

2） 遞歸方程求解

遞歸算法分析必定產(chǎn)生遞歸方程，算法2的時間復(fù)雜性分析產(chǎn)生的遞歸方程類同方程（1），故以此方程為例介紹常用的遞歸方程解法[11]：特征方程法和生成函數(shù)方法。課堂分小組探究學(xué)習(xí)任務(wù)。

①特征方程法。介紹線性齊次的遞歸關(guān)系概念，以及利用特征方程及特征根的方法求解線性齊次遞歸方程的步驟：首先根據(jù)遞歸關(guān)系列出對應(yīng)的特征方程，求出其特征根，得到含待定系數(shù)的通解形式；然后利用初值得到定解。通過小組合作，學(xué)生得出遞歸方程（1）的解為：

3.4 歸納總結(jié)

將算法1與算法2理論分析對比：算法1中循環(huán)[n-2]次，時間復(fù)雜性為[Ο（n）]；由（2），算法2的時間復(fù)雜性為[Ο（2n）]。利用C語言實現(xiàn)，[n=46]運行時算法2有明顯的等待時間，兩者運行時間如圖1所示。提問：為什么如此大的區(qū)別？利用遞歸樹分析遞歸的執(zhí)行過程，得出原因為問題的重復(fù)性求解，為后面的動態(tài)規(guī)劃算法求解打下埋伏。

總結(jié)：遞歸算法模型結(jié)構(gòu)，遞歸算法優(yōu)缺點。當子問題相互獨立時，建議使用遞歸算法。

4 動態(tài)規(guī)劃算法教學(xué)過程

動態(tài)規(guī)劃[12]算法是基于美國數(shù)學(xué)家R. Bellman1957年在研究多階段決策過程的優(yōu)化問題時提出的著名的最優(yōu)化原理，它基于一個遞歸方程——動態(tài)規(guī)劃函數(shù)方程和初始狀態(tài)，需要最優(yōu)值數(shù)組將子問題的解存儲起來，當求解稍大問題時就查找其子問題的值，不用重復(fù)計算。動態(tài)規(guī)劃算法有兩個難點：動態(tài)規(guī)劃函數(shù)的建立和子問題的求解。雖然有很多諸如0-1背包問題、最長公共子序列等經(jīng)典優(yōu)化實例，但為了分解知識難點并和前面遞歸算法設(shè)計對比，使用Fibonacci序列作為引例教學(xué)很有必要。

4.1 提出設(shè)計要求

如果使用數(shù)組數(shù)據(jù)類型存儲各項Fibonacci數(shù)，F(xiàn)ibonacci序列的第[n]項怎樣求？學(xué)生根據(jù)已有的基礎(chǔ)，容易得出算法3。

算法3? int Fib3（int n）

{int *f; //最優(yōu)值數(shù)組

f=new int[n];

f[1]=f[2]=1;

for（int i=3;i<=n;i++）f[n]=f[n-1]+f[n-2];

return f[n];

}

4.2 設(shè)計總結(jié)——動態(tài)規(guī)劃算法

雖然學(xué)生能設(shè)計出算法3，感受使用數(shù)組實現(xiàn)遞歸方程（1）求解的方便，但不會從算法設(shè)計方法歸類。以算法3引出動態(tài)規(guī)劃算法的相關(guān)概念：求第[n]項轉(zhuǎn)化為求每一項——問題分解，每個子問題的值保留——最優(yōu)值數(shù)組，循環(huán)計算（保證小的問題先計算）——子問題求解不重復(fù)。

由于子問題計算不重復(fù)，動態(tài)規(guī)劃算法效率高。算法3時間復(fù)雜性同算法1，為[Ο（n）]。

4.3 動態(tài)規(guī)劃算法的變形——備忘錄方法

根據(jù)遞歸方程（1）很容易設(shè)計算法2，但直接遞歸實現(xiàn)會造成很多問題重復(fù)計算，時間復(fù)雜度達到[Ο（2n）]，效率極低。提問：遞歸算法能否避免子問題重復(fù)計算？在遞歸框架中增加備忘錄（最優(yōu)值數(shù)組）可以解決。討論備忘錄的作用及使用方法：備忘錄保留了已計算子問題的答案，在遞歸調(diào)用之前檢查該問題是否求解過，如果求解過直接使用答案，不必重新計算；如果沒求解，則遞歸求解，求解完后答案填入備忘錄，保證以后不會再做此問題。小組討論修改算法2，得算法4。

算法4? int f[101]; //全局變量f，記載子問題的答案，0表示沒求解過

int Fib4（int n）

{if（n<=2） rerun 1; //遞歸出口

//保證每個子問題只求解1次

if（！f[n]） //檢查f，沒求解過

{n1=Fib4（n-1）;

n2=Fib4（n-2）;

return f[n]=n1+n2; //保存答案返回;

}}

算法4雖然是遞歸，但子問題本質(zhì)上只計算了一次，故算法效率大大提高了，時間復(fù)雜度等同算法1，為[Ο（n）]。與直接遞歸算法2對比實驗截圖如圖2所示。

4.4 歸納總結(jié)

動態(tài)規(guī)劃算法的步驟是：1） 劃分階段確定子問題，確定子問題最優(yōu)值的遞歸關(guān)系。子問題往往是重復(fù)且具有最優(yōu)子結(jié)構(gòu)（原問題的解包含子問題的解）。2） 求解子問題的最優(yōu)值，并記載決策信息。子問題最優(yōu)值的計算保證不重復(fù)，有兩種方法：自底向上法和備忘錄法。3） 利用決策信息構(gòu)造最優(yōu)解。后續(xù)實際多階段決策問題實例重點理解第1）步和第3）步。

備忘錄方法在遞歸算法框架中增加最優(yōu)值數(shù)組，一方面避免子問題重復(fù)計算，另一方面解決了子問題循環(huán)求解時確定順序的難題。

5 結(jié)束語

選取了能很好培養(yǎng)計算思維、通俗易懂的Fibonacci序列實例設(shè)計了算法設(shè)計與分析課程兩個重要算法設(shè)計方法：遞歸算法和動態(tài)規(guī)劃算法的教學(xué)。教學(xué)實踐后，學(xué)生課堂表現(xiàn)活躍、學(xué)生原來兩個較抽象的算法設(shè)計方法難理解區(qū)分的問題解決了，具備進一步學(xué)習(xí)算法應(yīng)用的熱情和能力，課程成績有明顯的提高?？梢钥闯?，“基于合適的案例提出問題——學(xué)生討論解決問題——老師梳理關(guān)鍵知識點”的教學(xué)方式對學(xué)生建立知識框架、培養(yǎng)計算思維及后續(xù)進一步主動學(xué)習(xí)幫助很大，效果較好。當然要很好的運用這兩個算法設(shè)計技術(shù)，還需逐步提高問題的難度進行訓(xùn)練。我們將挖掘一些圖論與大數(shù)據(jù)領(lǐng)域中的案例進行后續(xù)教學(xué)，并探索“案例教學(xué)法”的教學(xué)評價改革。

參考文獻：

[1] Wing J M. Computational thinking[J].Communications of the ACM， 2006，49（3）：33-35.

[2] 王曉東.計算機算法設(shè)計與分析[M].5版.北京：電子工業(yè)出版社，2018.

[3] 袁培森，任守綱，朱淑鑫，等.新工科背景下基于開源的“算法設(shè)計與分析”實踐教學(xué)探索[J].高校實驗室工作研究，2018（4）：10-12.

[4] 舒清錄，廖明梅.以培養(yǎng)計算思維為核心的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革研究[J].微型電腦應(yīng)用，2020，36（6）：21-23，28.

[5] 李晉麗，孫春娟，張學(xué)波.多措并舉提升算法設(shè)計與分析課程教學(xué)質(zhì)量[J].電腦知識與技術(shù)，2019，15（10）：111-113.

[6] Rigden J S.Editorial：the Carnegie report， ''a nation prepared：teachers for the 21st century''[J].American Journal of Physics，1986，54（8）：683.

[7] 李芒，蔣科蔚，李師.信息化學(xué)習(xí)方式案例教學(xué)[M].北京：北京師范大學(xué)出版社，2014.

[8] 黃宏濤.基于計算思維的Excel案例教學(xué)研究[J].計算機光盤軟件與應(yīng)用，2014，17（19）：239-240.

[9] 謝永，劉薇.云計算關(guān)鍵技術(shù)案例教學(xué)方法研究[J].電腦知識與技術(shù)，2021，17（31）：277-278.

[10] 劉亞，姒宏明.案例教學(xué)在信息安全課程中運用策略研究[J].計算機時代，2019（2）：98-100，104.

[11] 馮榮權(quán)，宋春偉.組合數(shù)學(xué)[M].北京：北京大學(xué)出版社，2015.

[12] Bellman R E.Dynamic programming[M].Princeton，N.J.：Princeton University Press，1957

【通聯(lián)編輯：王力】