一个增强算法学习兴趣的算法实验设计.docVIP

一个增强算法学习兴趣的算法实验设计 　　摘要：算法是计算机科学领域最重要的基石之一，但却受到了国内高校相关专业及学生的冷落。他们认为学习计算机就是学习各种编程语言，对算法学习没有兴趣。但是算法的学习更加重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法。本文论述一个增强学生算法学习兴趣的算法实验设计方法。让学生在实验中体验算法学习的重要性，通过实验发现问题，分析问题出现的原因，寻找解决问题的办法，从而将原来的被动学习转化为主动学习。 　　关键字：算法；实验设计；动态规划 　　中图分类号：G642.4 文献标志码：A 文章编号：1674-9324（2017）16-0215-02 　　一、引言 　　算法是计算机科学领域的最重要的基石之一，但在国内却受到了高校及学生的冷落[1]。许多公司招聘往往要求Java，C#及C++等相关语言及相关平台。因而许多学生认为，学习计算机就是学习各种编程语言及相关平台，对算法的学习不感兴趣。计算机语言和开发平台日新月异，PowerBuilder，Visual Basic，Dephi及Visual Foxpro都曾经很流行，但现在使用的人很少。现在流行的是Java，C#，C++等语言，十几年后他们是否还流行？实际上，不管编程语言及相关平台如何变化，万变不离其宗的是算法。许多计算机领域的创新实质是算法的创新。真正学懂计算机的人，不只是“编程匠”，他们既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题――而这种思维和手段的最佳演绎就是“算法”[1]。因而，有人地把算法等基本课程比拟为“内功”，把语言、平台及相关技术与标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的[1]。 　　本文论述一种利用实验增强学生算法学习兴趣的方法。在实验中，让学生体验算法学习的重要性，明白改进算法比升级计算机重要得多；让学生通过实验发现问题，分析问题出现的原因，寻找解决问题的办法，从而将原来的被动学习转化为主动学习[3]。 　　二、实验设计 　　有的学生觉得算法不重要，因为他们平时编写的程序都能在几秒时间内完成，甚至认为他们现有的计算机足够的快，根本就没有改进算法的必要。因而第一实验，我让学生首先实现Fibonacci数列的递归算法（以及插入排序算法），并统计程序运行时间与问题的规模即n的关系（n～100）。其算法如算法1[2]： 　　算法1 　　过程 FibonacciRec（n） 　　1.if （n=1） or （n=2） then 　　2. return 1 　　3.else 　　4. return FibonacciRec（n-1）+FibonacciRec（n-2） 　　5.end if 　　学生们非常高兴，觉得实验足够简单，还给出了算法。他们很快就编写好程序，并开始运行，刚开始程序运行很快，当n为42以下，基本能在1秒内完成。并观察到，运行时间随n增长很快。当n为60时需要1个多小时才能完成，图1为学生统计的Fibnonacci运行时间与n之间的关系。由此可以推算当n为70时需要约3天的时间，n为80时需要计算约250天，n为90时，需要约203年才能完成。显然，即使把你的计算机速度升级100倍对，当n80时，也是不可接受的。 　　然后我让学生编程实现Fibonacci的非递归算法，算法2[2，4]： 　　算法2 　　1.input n 　　2.FA[1]←1 　　3.FA[2]←1 　　4.for i←3 to n 　　5. FA[i]←FA[i-1]+FA[i-2] 　　6.end for 　　7.output FA[n] 　　//若n=1或n=2，则循环不执行。 　　学生发现，算法2执行速很快，当n=90时，在I3计算机运行只需要0.056秒的时间。然后我引导学生寻找为什么算法2运行速度快，而算法1运行速慢的原因。刚开始学生认为，算法1慢是因递归的原因。确实递归对程序速度有影响，但是影响不是太大。这是我让学生对比递归与非递归的插入排序学生自己得出的结论。学生经过深入的分析发现，算法1中隐藏着大量的重复计算，例如求7的Fibonacci数（Fibonacci（7），以下Fibonacci函数简称F（7））需要求2次F（5），3次F（4），5次F（3），8次F（2）的计算，如图2。因而算法1运行的速度较慢。然后让学生分析算法的时间复杂度，设求F（n）所需的时间为T（n）。 　　根据算法1可得 　　T（n）= 1 n=1 or n=2T（n-1）+T（n-2） n2 （1） 　　求解该递归方程可得T（n）=（■）n=1.61803n。由此可知算1是指数时间复杂度算法，算法运行的时间随n增长非常快，当n为