算法研究在算法教学中的应用

摘要：在算法教学中补充讲解一些综合实例，通过提出问题，分析问题，讲解问题，将算法研究的思想贯穿其中，可以培养学生的研究意识以及培养学生的发散式思维。

关键词：算法；教学；时间复杂性

中图分类号：G642文献标识码：A文章编号：1009-3044(2007)05-11471-02

1 引言

简单地说，一步一步解问题的过程称为算法。求解同一个问题Q通常有若干种算法，在算法研究中我们要问：什么是解问题Q的“好”算法？为回答这个问题，我们需要比较不同算法的效率，也就是算法的复杂性。算法的复杂性是算法运行所需要的计算机资源的量，算法的复杂性有时间复杂性和空间复杂性。那末针对具体的算法，算法的时间复杂性该如何求？我们还能否设计出效率更高的算法吗?不同的算法各有什么优缺点等等。这是我们在研究算法中常常要考虑，要解决的问题。算法教材有一个特点，就是一个章节论述一个独立的问题。有的教材侧重理论分析，而有的教材侧重算法描述。在算法研究中往往涉及许多共同的问题，那末我们在算法教学中，应如何将算法研究中的思路贯穿其中呢?我们可以针对性地补充一些我们在算法研究中曾经研究过的问题或一些综合性强的问题，作为综合实例讲解给学生。这样既讲解了解决问题的具体方法和设计思路。又培养学生提出问题，分析问题，解决问题的能力，传授给学生一种研究思路。

2 实例讲解

在计算机算法设计与分析中，递归是一种非常有力的工具。递归方法贯穿整个算法教程。从经典递归，如Hanoi问题，Fibonacci数列等，到分治法，回溯法以及动态规划法等等，这些常用的算法设计技术都离不开递归。使用递归方法往往使函数的定义和算法的描述简洁且易于理解，且使设计出的算法易于分析。尤其在复杂算法的描述中递归技术被经常采用。[1]递归算法结构清晰，可读性强。然而，递归算法的运行效率低，若在程序中消除算法的递归调用，则其运行时间可大大节省。

如何使学生对递归算法的优缺点有一个直观的认识，对算法的效率有更深刻的理解，以及如何求复杂递归算法的时间复杂度，又可以采用什么方法将递归算法转化为非递归算法等等。针对递归问题以及与递归问题相关的一些算法概念和算法问题，在课堂教学中，我们可以针对性地提出一系列问题，然后通过一个实例，将所提问题综合在例子中，通过这个综合实例的分析和讲解，即给出了一种思考问题的思路，教学生如何提出问题，又通过具体分析，讲解给出解决具体问题的方法和思想。

例：有5个人坐在一起，问第5个人多少岁？他说比第4 个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2 个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大？

显然，这是一个递归问题，可表示为：

上述递归过程可设计出递归算法为：

算法1 递归算法：

上述递归算法的时间复杂度可用母函数法计算如下：

设母函数为：

代入递推关系，得

整理得

所以，age(n)等于xn的系数

age(n)=8+2n

因此，上述递归算法的时间复杂度为O(n)

另外，利用上述求得的非递归式ago(n)=8+2n，可设计上述问题的非递归算法如下：

算法2 非递归算法：

age(int n)

{return(8+2n);}

由此可知，非递归算法的时间复杂度与问题规模无关。

通过此实例我们可以让学生知道：

(1)针对递归我们可以提出许多问题。

(2)递归算法具有算法简洁，可读性强的特性。

(3)对于递归算法我们可以采用母函数法计算其时间复杂度，同时还可得到该递归算法的非递归表示式，由此可设计出高效的组合算法。这样不仅介绍了如何用母函数法计算递归算法的时间复杂度以及如何将递归转化为非递归，如何根据递归和非递归式设计算法，而且又引出了组合算法的概念。让学生了解组合算法虽然比较抽象，但它的效率却很高。

(4)对于一个问题我们可设计出不同的算法。对于不同的算法，其算法的复杂性是不同的。有时往往相差很大。对于上述问题，一个算法的时间复杂度是线性阶的，而另一个算法与问题的输入规模无关。这说明我们为什么要研究算法效率，即算法的复杂性。

上面的实例是一个相对简单的例子，可能会使学生对算法效率的理解还不够更深刻，对递归转化为非递归可能还感觉不以为然。因此，在讲完这个实例之后应该马上留一道练习题让学生练习，此题的类型与例题的类型完全相同但稍微复杂一点，且此题的递归算法的时间复杂度是指数阶，而非递归化后的算法的复杂度与问题的规模无关。通过练习既让学生练习掌握了具体方法，同时也让学生切身体会到同一个问题设计不同的算法，效率会相差如此之大。因此懂得算法设计与分析的重要性。

我们可以让学生练习下面的练习题：核反应堆中α、β两种粒子，每单位时间，1个α粒子分裂为3个β粒子，1个β粒子分裂为2个β粒子和1个α粒子，假设t=0时刻，反应堆中有1个α粒子，求在t时刻的反应堆中α、β粒子数？

3 结束语

算法研究是一种创造性的思维工作。算法课程是计算机专业本科高年级或是研究生开设的一门专业课，在算法的教学中，要引导学生学会提出问题，再想办法去解决问题。注意培养学生的发散式思维，为今后学生从事研究工作打下基础。因此，在教学过程中根据教学内容补充一些综合实例，通过提出问题，分析问题，最后讲解问题，不仅使学生对一些抽象的思想，概念，方法，有一个直观的认识，掌握具体的方法。使学生对算法设计与分析有一些综合理解，而且还培养了学生的发散式思维及研究意识。以最终达到提高算法教学质量的目的。

参考文献：

[1] 王晓东. 算法设计与分析[M]. 北京：清华大学出版社，2002.

[2] 卢开澄. 计算机算法导引设计与分析[M]. 北京：清华大学出版社，2003.

[3] 郑宗汉，郑晓明. 算法设计与分析[M]. 北京：清华大学出版社,2005.

[4] 孙淑玲，许胤龙. 组合数学引论[M]. 合肥：中国科学技术大学出版社，2004.

[5] T H Cormen, CE Leisersen, R LRivest, C Stein. Introduction to Algorithms[M]. 2nd ed. New York:McGraw-Hill,2001.

[6] Kunth D E. The art of computer programming[M]. volume 1/Fundamental Algorithms, volume3/Sorting and Searching, Addison2Wesley Publishing Company, Inc.,1993.

[7] E Horowitz, S Sahni, S Rajasekeran. Computer Algorithms/C++[M]. Rockville, Md:Computer Science Press,1996.

[8] A. Nijenhuis and H. Wilf. Combinatorial Algorithms for Computers and Calculators[M]. Academic Press, Orlando FL, second edition, 1978.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。