1、信息化与计算机教育本栏目责任编辑：王力Computer Knowledge and Technology电脑知识与技术第19卷第1期(2023年1月）第19卷第1期(2023年1月）Fibonacci数列在递归与动态规划算法教学中的应用李胜华（湖北大学 网络空间安全学院，湖北 武汉 430062)摘要：递归与动态规划算法是算法设计与分析课程中培养学生计算思维、提高解决实际问题能力的两类主要算法。为了减小学生理解这两类抽象算法设计方法的难度，提高学习兴趣，文章讨论了将同一Fibonacci数列作为案例应用于它们的教学方案。基于该数列与这两个教学内容的内部联系，通过实施案例分析、讨论交流、设计求解
2、、比较总结的方法进行教学。教学实践结果表明：学生不仅较容易地掌握了这两个算法设计方法的基本框架、本质区别及算法分析方法，而且提高了专业知识理解力及计算思维修养。关键词：算法设计与分析；递归；动态规划；案例教学；Fibonacci序列；计算思维中图分类号：G642文献标识码：A文章编号：1009-3044(2023)01-0157-03开放科学（资源服务）标识码(OSID)：1 引言“新工科”背景下，高校越来越多专业开设算法设计类课程，旨在加强计算思维的培养。“计算思维”是美国卡内基梅隆大学周以真(Jeannette M.Wing)教授2006年在ACM会刊首次定义1：运用计算机科学的基础概念进
3、行问题求解、系统设计和人类行为理解等覆盖计算机科学之广度的一系列思维活动。从此计算不再只是编程，而是解决问题的思维，每个人必备的基本技能能运用计算思维更有效率地解决各种问题。一般来说，计算思维中最重要的几个思维过程是抽象、分解以及组合。递归算法和动态规划算法设计方法是算法设计与分析课程的两个基本教学内容2，它们能很好地体现计算思维的过程。计算机算法设计理论较抽象、实践综合能力要求高，学生在理论、实践及应用三个方面有效融合有很大难度，有畏难情绪。为改善教学效果，近些年对算法设计与分析课程的教学改革研究较多3-5。但大部分改革对教学条件要求较高，有些高校或专业不具备，实施有难度。毋庸置疑“算法”本
4、身理论要求较高，实践辅助理论理解和提高。但相当部分同学课堂上的基本理论理解不够重视，造成后面应用实践费时甚至错误。根据多年的教学经验，课堂上采用案例教学法有助于学生专业知识衔接、理论理解、课堂交流和思维创新等。“案例教学法”于1870年哈佛大学法学院提出，1921年在哈佛大学商学院正式推行，1986年美国卡内基小组(Carnegie Task Force)的报告书特别推荐案例教学法在师资培育课程的价值6。从此，“案例教学法”被视为一种相当有效的教学模式，我国也有众多学者7-10从事这方面的研究和实践。“案例教学法”中选取的案例应是学生有认知基础的，与教学内容有内部联系，并有助学生专业素质培养。
5、递归与动态规划两类算法设计与递归方程有紧密联系，本文将选取起源递归方程(1)的Fibonacci数列作为二者的入门教学案例，重点讨论相关的案例演示、案例分析、案例设计、归纳总结等几个主要环节的教学过程。Fn=Fn-1+Fn-2n 3,F1=F2=1.(1)2 Fibonacci序列著名中世纪意大利数学家Leonardo Fibonacci在其1202年著作Liber Abaci(计算之书)提出一个兔子问题：已知兔子出生2个月后具备繁殖能力，以后每月都能繁殖一对小兔子。假设第1个月初有1对刚诞生的兔子，不考虑兔子死亡情况，问过n个月后有多少对兔子。设Fn为过n个月后兔子的对数。由于不考虑死亡，则
6、Fn由上个月的兔子对数Fn-1累加新繁殖的小兔子对数，而新繁殖的小兔子对数等于前两个月的兔子对数Fn-2（有繁殖能力），所以有递归程(1)成立。从而产生兔子序列：Fn=1,1,2,3,5,8,13,，即Fibonacci序列。3 递归算法设计教学过程递归是一种重要的算法设计方法，递归算法结构收稿日期：2022-03-21基金项目：教育部产学合作协同育人项目(202101349004)；国家自然基金项目(11871053)作者简介：李胜华(1972)，女，湖北麻城人，副教授，博士，主要研究方向为信息安全和算法设计。E-mail：http：/Tel：+86-551-65690963 6569096
7、4ISSN 1009-3044Computer Knowledge and Technology电脑知识与技术Vol.19,No.1,January2023157DOI:10.14004/ki.ckt.2023.0031本栏目责任编辑：王力信息化与计算机教育Computer Knowledge and Technology电脑知识与技术第19卷第1期(2023年1月）第19卷第1期(2023年1月）简洁清晰、便于算法正确性证明和算法分析。教学目标是能抽象实际问题的递归关系，掌握递归设计模型和递归算法分析。与此相关的知识点为问题递归转化、递归算法框架、递归方程求解。3.1 案例演示提出兔子问题。
8、Fibonacci序列在小学生找数列规律及中学生写数列通项时遇到过，但该数列来源的实际问题大部分学生并不了解。通过上述有趣故事的引入，激发学生学习兴趣。3.2 案例分析分析每月兔子来源，引导学生建立递归模型求解，培养计算思维：抽象数列，分解新老兔子数，组合相加。学生通过自主学习或相互交流得出Fibonacci序列和递归方程(1)。基于学生“高级语言程序设计”的基础，先鼓励学生利用循环结构进行算法设计，见算法1。在课堂上能顺利写出算法1的同学并不多，原因是相当部分同学对程序变量的理解不透彻，导致循环修改部分容易出错。进而提出该问题递归算法的设计和分析要求。算法1 int Fib1(int n)i
9、f(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);/
10、递归转换2)递归方程求解递归算法分析必定产生递归方程，算法2的时间复杂性分析产生的递归方程类同方程(1)，故以此方程为例介绍常用的递归方程解法11：特征方程法和生成函数方法。课堂分小组探究学习任务。特征方程法。介绍线性齐次的递归关系概念，以及利用特征方程及特征根的方法求解线性齐次递归方程的步骤：首先根据递归关系列出对应的特征方程，求出其特征根，得到含待定系数的通解形式；然后利用初值得到定解。通过小组合作，学生得出递归方程(1)的解为：Fn=15(n-n)(2)这里，=(1+5)/2,=(1-5)/2。生成函数法。利用数列 ann=1对应的普通生成函数f(x)=n=1anxn可以求解an的通式。
11、介绍利用生成函数求解递归方程的通用步骤：根据递归关系求其生成函数的解析式；将解析式幂级数展开，通项即为所求。通过小组合作，学生也得出递归方程(1)的解为方程(2)。3.4 归纳总结将算法1与算法2理论分析对比：算法1中循环n-2次，时间复杂性为(n)；由(2)，算法2的时间复杂性为(2n)。利用C语言实现，n=46运行时算法2有明显的等待时间，两者运行时间如图1所示。提问：为什么如此大的区别？利用递归树分析递归的执行过程，得出原因为问题的重复性求解，为后面的动态规划算法求解打下埋伏。图1n=46算法1和算法2运行截图总结：递归算法模型结构，递归算法优缺点。当子问题相互独立时，建议使用递归算法。
12、4 动态规划算法教学过程动态规划12算法是基于美国数学家 R.Bellman1957年在研究多阶段决策过程的优化问题时提出的著名的最优化原理，它基于一个递归方程动态规划函数方程和初始状态，需要最优值数组将子问题的解存储起来，当求解稍大问题时就查找其子问题的值，不用重复计算。动态规划算法有两个难点：动态规划函数的建立和子问题的求解。虽然有很多诸如0-1背包问题、最长公共子序列等经典优化实例，但为了分解知识难点并和前面递归算法设计对比，使用Fibonacci序列作为引例教学很有必要。4.1 提出设计要求如果使用数组数据类型存储各项Fibonacci 数，Fibonacci序列的第n项怎样求？学生根
13、据已有的基础，容易得出算法3。算法3 int Fib3(int n)int*f;/最优值数组158信息化与计算机教育本栏目责任编辑：王力Computer Knowledge and Technology电脑知识与技术第19卷第1期(2023年1月）第19卷第1期(2023年1月）f=new intn;f1=f2=1;for(int i=3;i=n;i+)fn=fn-1+fn-2;return fn;4.2 设计总结动态规划算法虽然学生能设计出算法3，感受使用数组实现递归方程(1)求解的方便，但不会从算法设计方法归类。以算法3引出动态规划算法的相关概念：求第n项转化为求每一项问题分解，每个子问题
14、的值保留最优值数组，循环计算（保证小的问题先计算）子问题求解不重复。由于子问题计算不重复，动态规划算法效率高。算法3时间复杂性同算法1，为(n)。4.3 动态规划算法的变形备忘录方法根据递归方程(1)很容易设计算法2，但直接递归实现会造成很多问题重复计算，时间复杂度达到(2n)，效率极低。提问：递归算法能否避免子问题重复计算？在递归框架中增加备忘录（最优值数组）可以解决。讨论备忘录的作用及使用方法：备忘录保留了已计算子问题的答案，在递归调用之前检查该问题是否求解过，如果求解过直接使用答案，不必重新计算；如果没求解，则递归求解，求解完后答案填入备忘录，保证以后不会再做此问题。小组讨论修改算法2，
15、得算法4。算法4 int f101;/全局变量f，记载子问题的答案，0表示没求解过int Fib4(int n)if(n=2)rerun 1;/递归出口/保证每个子问题只求解1次if(!fn)/检查f，没求解过n1=Fib4(n-1);n2=Fib4(n-2);return fn=n1+n2;/保存答案返回;算法4虽然是递归，但子问题本质上只计算了一次，故算法效率大大提高了，时间复杂度等同算法1，为(n)。与直接递归算法2对比实验截图如图2所示。图2n=46算法4和算法2运行截图4.4 归纳总结动态规划算法的步骤是：1)划分阶段确定子问题，确定子问题最优值的递归关系。子问题往往是重复且具有最优
16、子结构（原问题的解包含子问题的解）。2)求解子问题的最优值，并记载决策信息。子问题最优值的计算保证不重复，有两种方法：自底向上法和备忘录法。3)利用决策信息构造最优解。后续实际多阶段决策问题实例重点理解第1)步和第3)步。备忘录方法在递归算法框架中增加最优值数组，一方面避免子问题重复计算，另一方面解决了子问题循环求解时确定顺序的难题。5 结束语选取了能很好培养计算思维、通俗易懂的Fibonacci序列实例设计了算法设计与分析课程两个重要算法设计方法：递归算法和动态规划算法的教学。教学实践后，学生课堂表现活跃、学生原来两个较抽象的算法设计方法难理解区分的问题解决了，具备进一步学习算法应用的热情和能力，课程成绩有明显的提高。可以看出，“基于合适的案例提出问题学生讨论解决问题老师梳理关键知识点”的教学方式对学生建立知识框架、培养计算思维及后续进一步主动学习帮助很大，效果较好。当然要很好的运用这两个算法设计技术，还需逐步提高问题的难度进行训练。我们将挖掘一些图论与大数据领域中的案例进行后续教学，并探索“案例教学法”的教学评价改革。参考文献：1 Wing J M.Computational th
