C#语言编程求解斐波那契数列--湖北科技职业学院

1、C#语言编程求解斐波那契数列教学设计湖北科技职业学院 宋薇所属学科：计算机科学与技术 99所属专业：计算机应用所属课程：C#程序设计适用对象：高职高专计算机应用专业学生知 识 点： 递归法 迭代法1. 教学背景随着计算机的普及，编写程序来解决现实生活中的一些复杂计算问题越来越受到人们的青睐。大到登月、探火星，小到吃饭、用手机，人类发展到今天已经脱离不开计算机程序。不管我们有没有觉察到，我们每天的生活都至少接触了上百个程序或系统。这两年，在欧美已经掀起了一股编程热，从将编程教育纳入小学正式课程，到CodeSchool、Codecademy等面向大众的编程学习网站出现。大西洋杂志指出，根据美国劳工

2、统计局的数据显示，计算机编程行业的扩张率比所有行业平均扩张率高出30%，2013年平均工资为90,000美元。 C#程序设计作为高职院校计算机应用专业程序设计的入门必修课程，学好本门课程对该专业学生未来的编程生涯起到深远的影响。本节课主要介绍如何利用迭代法和递归法，采用C#语言编程求解斐波拉契数列。首先通过经典的数学问题导入斐波拉契数列，然后从程序分析、设计到实现入手，通过形象生动的流程图、动画及真实的程序代码实现及结果分析，激发学生学习的积极性，引导学生主动学习。2. 教学目标2.1知识目标:了解斐波那契数列的由来与应用、递推公式;掌握迭代法与递归法的求解过程。2.2能力目标:通过斐波那契数

3、列的求解，培养学生分析问题，解决问题的能力，培养学生对实际问题进行分析并抽象出数学模型，再进行算法设计，最后转换为程序的能力。2.3情感目标：通过感受斐波那契数列神奇的性质，以及计算机解决问题的魅力，培养学生学习程序设计的积极性、主动性，让学生觉得编写出程序原来是这么有成就感的事情。3. 教学方法3.1启发式教学：从生活实际出发，以启发学生的思维为核心，调动学生的学习主动性和积极性，把被动的灌输式教学转变为主动的吸取式学习。3.2情景教学：教师有目的地引入一个生动具体的场景，以生动形象的情境激起学生学习情绪，让学生一起探索、体验，从而帮助学生理解知识点。4. 教学思想“微课”是通过精心的信息化

4、教学设计，以流媒体形式展示的围绕某个知识点或教学环节开展的简短、完整的教学活动。高职计算机应用专业学生的教学过程，应该从实际的岗位素质能力、知识需求出发，以培养学生实际动手能力和解决问题能力为目的。遵循高职教育“够用为度“的课堂原则，以项目实现过程来分解复杂的理论知识，结合一个具体的项目为案例，循序渐进，引导学生主动学习。5. 课程设计6.教学步骤教学内容设计意图1问题导入(1分13秒)通过电影了解斐波那契数列吸引学生注意力2问题分析(2分10秒)分析斐波那契数列递推规律引导学生理解递归算法设计思路3编程实现（1分）讲解递归法运行代码介绍递归法应用，引导学生发现递归法的特性4知识拓展（3分30

5、秒）讲解迭代法求解思路介绍迭代法应用，引导学生对不同算法进行比较5小结（40秒）小结课程回顾整节课的内容5.1问题导入(1分13秒)什么是斐波那契数列？这个数列有什么应用的意义，为什么要求解斐波那契数列呢？从nature by numbers工作室制作的微电影中了解这一答案。让我们首先从一个数列开始，它的前面几个数是：1、1、2、3、5、8、13、21、34、55、89、144这个数列的名字叫做“斐波那契数列”，这些数被称为“斐波那斐数”。斐波那契数列是一个非常美丽、和谐的数列，它的形状可以用排成螺旋状的一系列正方形来说明，起始的正方形的边长为1，在它左边的那个正方形的边长也是我，在这两个正方

6、形的上方再放一个正方形，其边长为2，以后顺次加上边长为3、5、8、13、21等等的正方形。这些数字每一个都等于前面两个数这和，它们正好构成了斐波那契数列。以斐波那契数为边的正方形，然后在正方形里面画一个90度的扇形，连起来的弧线就是斐波那契螺旋线。自然界中存在许多斐波那契螺旋线的图案，大到银河系的图形，小到人类耳朵的形状，从树梢的松树果球，到来自大海的海螺都明显的符合斐波那契螺旋线，因此也被称为“黄金螺旋”。如果我们统计相邻两个斐波那契数的比值，我们将发现，这个比值随着序号的增加而逐渐趋于黄金分割比。即(a+b)/a->1.618。刚才的微电影，相信已经让同学们了解了斐波那契数列的神奇魅

7、力，当然，不仅仅只有影片所介绍的自然生物领域，斐波那契数列广泛应用于现代物理、化学与经济学领域。那么，既然这个数列如此重要，我们又应该如何计算这个数列呢？5.2问题分析(2分10秒)公元1200年，意大利数学家列昂纳多.斐波那契在计算之书中第一次将斐波那契数列推上了历史的舞台。在数学上，费波那契数列是这样来定义的：（1） 分析手工计算数列的难度仔细观察一下数列，你会发现当数列中的数据增长得越来越快时，仅用手工计算的方法就会表现的越来越困难。(例如，你愿意用列表的方法求出第40个数吗？)我们需要研究计算规律，找出一般的方法，利用计算机解决这个问题。（2） 通过PPT动画演示斐波那契数列的求解过程

8、，引导学生发现在前进中规模缩小与回退中得到最终结果的求解思路。（3） 介绍递归法的应用与条件递归有两个基本条件：1、是把规模大的问题转化为规模小的相似的子问题来解决。2、在函数实现时，这个解决问题的函数必须有明显的结束条件，否则就会产生无限递归的情况。让我们来看看斐波那契数列是如何满足递归的两个条件的：1、对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是说规模为n的问题，转化成了规模更小的问题；2、对于n=0和n=1，存在着简单情境：f(0) = 0, f(1) = 1。5.3编程实现(1分)（1） 介绍用迭代法求解的完整源程序,并运行程序分析结果。这里我们希望统计

9、程序运行时间，因此我们使用了System.Diagnostics命名空间，通过调用StopWatch类来监视代码，统计程序运行的时间，并以毫秒为单位。int fibRE(n) if(n <2) return n; else return f(n-1) + f(n-2);编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归，否则，你的函数可能会永不停息的在那里递归调用了(2) 运行代码，引导学生发现问题，递归算法的计算效率较低。分析讨论产生这一问题的原因。PPT动画演示，利用递归算法计算Fib(5)的过程中，Fib(1)计算了

10、两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。事实上，用递归法求解斐波那契数列的复杂度为指数级。这个Fibonacci的递归实现在计算值时，每次递归调用都触发另外两个递归，而这两个递归在调用的时候每个都还要触发两外的两个递归调用，再接下去的调用也是如此。现在，我们知道，这个冗余的递归调用是以几何级数增长的。例如，在递归计算Fibonacci(10)时，Fibonacci(3)的值被计算了21次。而在递归计算Fibonacci(30)，这个调用的次数是骇人的317811次！这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再

11、可接受的时间内算出。随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45)参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年。计算需要时间，复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它不是万能，有些事情“不能”做。大量的递归调用会建立函数的副本， 耗费大量的时间和内存，因此，对于要求执行效率较高的问题，比如大规模的斐波那契数列求解，并不适合递归法求解。5.4问题拓展递归(3分30秒)（1）介绍递归到非递归算法的转换方法递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此

12、，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题。把递归算法转化为非递归算法有如下两种基本方法：a直接转换法。直接求值，不需要回溯，使用一些变量保存中间结果，直接用循环结构实现求值过程。b间接转换法。不能直接求值，需要回溯。利用堆栈的后进先出特性模拟递归算法的执行过程, 使用堆栈保存中间结果，从而用非递归算法替代递归算法。（2）采用第一种方法为大家讲解递归算法的非递归变换。我们现在已经得到了迭代公式，那么如何用程序来求解斐波那契数列呢？首先，我们总结出斐波那契数列的特点：第1，2个数都是1，从第3个数开始，每个数都是它前面两个数之和。然后，我们可以看出，这是一个迭代问题，不

13、断用变量的新值取代变量的旧值。当一个问题的求解过程能够由一个初值使用一个迭代表达式进行反复的迭代时，就可以由重复程序描述，即由循环结构来实现。下面我们用N-S流程图来描述求解斐波拉契数列的过程。i=1 ,f1=1 ,f2=1输入 n 的值当i<=n时假真i<=2f=1f=f1+f2输出f的值f1=f2f2=f5.5总结(40秒)了解斐波那契数列的由来与应用、递推公式;掌握迭代法与递归法的求解过程。对于这样有规律的数列问题，我们应该总结出规律，计算出通用公式，然后进行算法分析，找出求解方法，再用程序语句来实现。7. 教学特色在教学过程中，遵循“提出问题-分析问题-解决问题”的步骤，让学生在一个具体的学习情境中掌握知识点，提高思维分析能力。(1)引用斐波那契数列这个充满神奇色彩的数学问题，激发了学生的学习积极性。多媒体课件与动画等表达方式丰富多彩，形象逼真。(2)运用程序设计中经典的两种算法：迭代法和递归法，诠释了分析问题、算法设计和程序实现的全过程。8. 教学小结 传统的程序设计课程存在着各种弊端，在讲课时大段代码令学生摸不着头脑。本课程采用项目式教学，在课堂从需求到实现，逐步引导学生发现问题、解决问题，让学生主动思考，从而使得学生对知