算法在身边——学习算法从妈妈的菜谱开始

听到“算法（Algorithm）”这个词，大部分人都觉得好像很艰深晦涩。的确，这不是一个常常能听到的词。事实上，在数学、计算机等理工科领域，所谓的算法，指的就是“对特定问题的解决步骤”。而这里说的特定问题，通常有：

• 对信息进行排序

• 搜索目标信息

等不同的问题。

此外，如果说“算法是解决问题的步骤”，那么撇开计算机的数据处理不论，现实生活中也有很多问题的解决方法蕴含了算法的思想。这其中的代表就是菜谱。

我们都知道，记录做出各色各样的菜品所需步骤的东西就是菜谱。

例如：

• 鸡肉咖喱

• 马铃薯炖肉

以上两个菜品的菜谱里，会把制作菜品所必需的材料种类、量标记清楚，并且把做菜的过程、每一步需要的时间等正确地记述下来。遵从这样的步骤，无论是谁都可以做出一道不错的鸡肉咖喱或者马铃薯炖肉。

像这样对给定问题（做一道鸡肉咖喱等）给出可行解法的菜谱，也就是“解决问题的步骤”，正可以称得上是不错的算法范例。

• 算法和菜谱

算法是人类智慧的结晶

按照菜谱指定的方法做菜，有时候也不一定能做出好吃的菜。如果分毫不差地遵照一份菜谱，结果做出来的菜并不好吃，那么我们可以说那一份菜谱“不是很好的菜谱”。于是很自然地，那份菜谱也就渐渐地没什么人用了。

而可以做出大家都觉得美味的菜的菜谱，会有越来越多的人重复使用。这样的菜谱也就成了“好的菜谱”。而好的菜谱在越来越多人使用的情况下，会被慢慢地改善，可以指导人做出越来越美味的菜。像这样，好的菜谱上就聚集了为了做出美味的菜而付出的前人的智慧的结晶。

在程序中应用的算法也是一样。自计算机面世，在利用计算机解决各种各样的“问题”时，无数解法、步骤被人们提出来。“是不是可以更好地复用”、“是不是可以更高效”、“是不是可以花费更少的空间代价”等，很多研究者会从这些方面对现存的算法进行改善。而历经时间的洗炼，那些优雅的算法正在被应用到各种计算机程序中去。像这样，算法也一样，聚集了为了编写优雅的程序而付出的前人的智慧的结晶。

• 好的菜谱正是优秀的算法

了解算法对玩游戏有帮助吗

优秀的算法是编写程序的范本，能帮助我们巧妙地解决问题。这和玩游戏时用的攻略异曲同工。

在游戏对战的时候，采取更好的战略往往容易获得胜利。曾经有这么一款射击游戏，它的玩法是：“用移动的炮台把从游戏画面上方不断迫近的敌人击落”。在这款游戏的设计中，甚至还有直接写成招式名称的游戏定式，譬如“○○式”、“△△攻击”等。依照定式所指示的步骤来操作，无论谁每次都可以打倒同样的敌人。这种为游戏通关设计的定式，也算是不错的算法。

所谓的“定式”，原本是围棋术语，指的是“在某种局面下，最优的固定下法”。在将棋1 或者国际象棋中，同等的东西被称为“棋式”，在英文里叫“theory”。在下围棋的时候，在某种局面下只要知道相应的定式，就可以在没有“思考往后几步的下法，在各种下法中找出最好的下法”的情况下，直接下出最好的一步棋。定式中汇集了无数前人的智慧，因此知道的定式越多，下赢不知道定式的对手就越简单。

而计算机中的算法也是如此。一个学习过算法的人，即便没有多高的天份，在编写同样功能的程序时，完成度比没有学习过算法的人有明显的优势。

• 汇集前人智慧的定式也是优秀的算法

算法有两个必要条件

作为“解决问题的处理顺序”的算法，必须要具备下述两个重要的条件。

1．准确性

对相应的问题，算法必须能够得出正确的结果。这正是算法的准确性。所谓算法的准确性，指的是“输入符合指定条件的值，一定要保证能得到正确的输出”。算法准确性的证明事实上并不简单。乍看之下能够得出正确结果的算法，很可能在多了某些特别的边界输入值的情况下就会发生谬误。证明算法准确性的其中一个方法是，“对于算法中的任意一个步骤，输入当前步骤满足条件的值，看看是否能得到当前步骤产生的准确的结果，以此细分并判定。”这种方法叫断言（Assertion）。

2．可停止性

算法必须是最终可停止的。也就是说，一直重复，永远也不能返回结果的操作步骤（也叫死循环）是不能被称作算法的。算法的可停止性也就是“保证无论什么样的输入，也一定可以在有限时间内正确地停止”。

• 算法的两大支柱

要特别了解的重要算法

编写程序时必要的算法浩如烟海，而其中有些是要特别了解的重要的算法。本书将介绍一些比较有代表性的算法。

1．专用于数论计算的算法

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

• 求解联立方程的高斯消元法

• 求解定积分近似值的梯形公式

• 计算质数的埃拉托斯特尼筛法

2．对一组乱序的数据进行升序或者降序排序的算法（sort）

• 选择排序

• 冒泡排序

• 插入排序

• 希尔排序

• 归并排序

• 快速排序

3．在大量数据中找出目标数据的搜索算法（search）

• 线性搜索（linear search）

• 二分搜索（binary search）

4．在一个字符串中找到符合特定模式的子串（子字符串）的匹配算法

• 简单字符串搜索

• KMP 算法

• BM 算法

• 有代表性的算法