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

【通联编辑：王力】