Question

建议从事编程工作的人手中要有一本能作为算法辞典的书（可以作为算法辞典使用的书有《算法技术手册》（George T. Heineman、Gary Pollice、Stanley Sellkow）、《算法精解：C语言描述》（Kyle Loudon）等）。虽然算法应该由自己思考，但如果遇到了不知道从哪里下手才好的问题，也可以利用这类辞典查查已经发明发来的算法

作为程序员的修养，表5.1列出了笔者认为最低限度应该了解的典型算法。这些算法包括刚刚介绍过的求解最大公约数的“辗转相除法”，判定素数的“埃拉托斯尼筛选法”（将在后面介绍），检索数据的三种算法以及排列数据的两种算法。记住了这些典型算法固然好，但请注意绝不要丢掉自己思考算法的习惯。

表5.1 主要的典型算法

名称                用途

辗转相除法            求解最大公约数

埃拉托斯特尼筛选法    判定素数

顺序查找              检索数据

二分查找              检索数据

哈希查找              检索数据

冒泡排序              数据排序

快速排序              数据排序

再试着思考一个具体问题吧。这次请思考一下解决“求解12和42的最小公倍数”这个问题的算法。所谓最小公倍数就是指两个整数的公共倍数（是一个数几倍的数）中最小的那个数。最小公倍数的求解方法在中学的数学课上应该学过了，但很可惜求解步骤是依赖人类的直觉的。请再思考一个适用于计算机的机械的算法。说不定会想“反正会有经典算法的吧，比如‘某某法’，然后就纠结于是否还要自己思考。

但即使查了算法辞典之类的书，也还是找不到求解最小公倍数的算法。为什么呢？因为我们可以通过以下方法求解最小公倍数 – 用两个整数的乘积除以这两个整数的最大公约数，因此12和42的最小公倍数就是12*42/6=84了。如此简单的算法不能算典型算法，这个例子说明先自己思考算法，再云应用典型算法这一点很重要。