Fibonacci數列在遞歸與動態規劃算法教學中的應用

李勝華

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

關鍵詞：算法設計與分析；遞歸；動態規劃；案例教學；Fibonacci序列；計算思維

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

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

1 引言

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

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

“案例教學法”中選取的案例應是學生有認知基礎的，與教學內容有內部聯系，并有助學生專業素質培養。遞歸與動態規劃兩類算法設計與遞歸方程有緊密聯系，本文將選取起源遞歸方程（1）的Fibonacci數列作為二者的入門教學案例，重點討論相關的案例演示、案例分析、案例設計、歸納總結等幾個主要環節的教學過程。

2? Fibonacci序列

3 遞歸算法設計教學過程

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

3.1 案例演示

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

3.2 案例分析

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

算法1? int Fib1（int n）

{if（n<=2）return 1;

int? i， a，b， c;

a=1， b=1; //循環初值部分

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

{? ?c=a+b; //循環工作部分

a=b; b=c;? //循環修改部分

}return c;

}

3.3 案例設計

程序設計高級語言都支持遞歸函數，將問題抽象成數學遞歸方程，再由遞歸方程轉換遞歸函數相對于循環算法邏輯清晰簡單。

1） 遞歸算法框架

根據方程（1）講解遞歸模型：遞歸出口、遞歸轉換，以及遞歸函數的算法框架。學生通過相互交流，能很好地將遞歸方程與遞歸函數統一，得到算法2。

算法2? int Fib2（int n）

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

return Fib2（n-1）+Fib2（n-2）; //遞歸轉換

}

2） 遞歸方程求解

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

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

3.4 歸納總結

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

總結：遞歸算法模型結構，遞歸算法優缺點。當子問題相互獨立時，建議使用遞歸算法。

4 動態規劃算法教學過程

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

4.1 提出設計要求

如果使用數組數據類型存儲各項Fibonacci數，Fibonacci序列的第[n]項怎樣求？學生根據已有的基礎，容易得出算法3。

算法3? int Fib3（int n）

{int *f; //最優值數組

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 設計總結——動態規劃算法

雖然學生能設計出算法3，感受使用數組實現遞歸方程（1）求解的方便，但不會從算法設計方法歸類。以算法3引出動態規劃算法的相關概念：求第[n]項轉化為求每一項——問題分解，每個子問題的值保留——最優值數組，循環計算（保證小的問題先計算）——子問題求解不重復。

由于子問題計算不重復，動態規劃算法效率高。算法3時間復雜性同算法1，為[Ο（n）]。

4.3 動態規劃算法的變形——備忘錄方法

根據遞歸方程（1）很容易設計算法2，但直接遞歸實現會造成很多問題重復計算，時間復雜度達到[Ο（2n）]，效率極低。提問：遞歸算法能否避免子問題重復計算？在遞歸框架中增加備忘錄（最優值數組）可以解決。討論備忘錄的作用及使用方法：備忘錄保留了已計算子問題的答案，在遞歸調用之前檢查該問題是否求解過，如果求解過直接使用答案，不必重新計算；如果沒求解，則遞歸求解，求解完后答案填入備忘錄，保證以后不會再做此問題。小組討論修改算法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雖然是遞歸，但子問題本質上只計算了一次，故算法效率大大提高了，時間復雜度等同算法1，為[Ο（n）]。與直接遞歸算法2對比實驗截圖如圖2所示。

4.4 歸納總結

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

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

5 結束語

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

參考文獻：

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

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

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

[4] 舒清錄，廖明梅.以培養計算思維為核心的數據結構課程教學改革研究[J].微型電腦應用，2020，36（6）：21-23，28.

[5] 李晉麗，孫春娟，張學波.多措并舉提升算法設計與分析課程教學質量[J].電腦知識與技術，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] 李芒，蔣科蔚，李師.信息化學習方式案例教學[M].北京：北京師范大學出版社，2014.

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

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

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

[11] 馮榮權，宋春偉.組合數學[M].北京：北京大學出版社，2015.

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

【通聯編輯：王力】