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

摘要：算法是计算机科学领域最重要的基石之一，但却受到了国内高校相关专业及学生的冷落。他们认为学习计算机就是学习各种编程语言，对算法学习没有兴趣。但是算法的学习更加重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法。本文论述一个增强学生算法学习兴趣的算法实验设计方法。让学生在实验中体验算法学习的重要性，通过实验发现问题，分析问题出现的原因，寻找解决问题的办法，从而将原来的被动学习转化为主动学习。

关键字：算法；实验设计；动态规划

中图分类号：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倍对，当n>80时，也是不可接受的。

然后我让学生编程实现Fibonacci的非递归算法，算法2[2，4]：

算法2

1.input n

2.FA[1]1

3.FA[2]1

4.for i3 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） n>2 （1）

求解该递归方程可得T（n）=（■）n=1.61803n。由此可知算1是指数时间复杂度算法，算法运行的时间随n增长非常快，当n为90时，需要几百年的时间才求出他的解，这显然是无法接受的。

而算法2采用自底向上的方式进行计算，并用数组FA把求得的解存储起来，避免了重复计算，算法而的时间复杂度是线性的，为O（n），因而算法执行的速度很快。当n=90时在I3计算机上运行只需要0.056秒的时间。算法2是一种用空间换时间的动态规划的设计方法，从算法1和算法2的比较中，学生体会了设计高效的算法比升级计算机重要得多。同时，该实验也为动态规划的引入做了铺垫。

三、结论

本文用简单的Fibonacci递归算法与非递归算法设计了一个算法实验。通过该实验，让学生体验了指数时间复杂度算法运行时间与数据规模的关系，让学生明白，对于规模稍大的问题，指数时间复杂度算法是不可接受的；通过对比两个算法，让学生体验了改进算法比升级计算机要重要得多，而算法设计策略是改进算法的关键；通过该实验，学生对算法产生浓厚的兴趣，从原来的被动学习转变化了主动学习。

参考文献：

[1]李开复.算法的力量[J].程序员，2006，（2）.

[2]M.H.Alsuwaiyel.算法设计技巧与分析[M].电子工业出版社，2012.

[3]Alfieri，L.，Brooks，P. J.，Aldrich，N.J.，& Tenenbaum，H. R.. Does discovery-based instruction enhance learning？. Journal of Educational Psychology，2011，103（1）.

[4]Thomas H.Cormen，Charles E.Leiserson，Ronald，L.Rivest，Clifford Stein，著.算法导论（原书第3版）[M].殷建平，徐云，王，等，译.北京：机械工业出版社，2013.