1.1 开始学习算法

在大学期间学编程的时候，简单的问题可以很容易地使用编程解决，例如简单的数学运算和输出语句。到后来随着知识点的深入，面对复杂问题时总是不知道从何下手。例如一个简单的俄罗斯方块游戏，我不知道该如何实现方块的旋转和排列功能。后来步入职场，面对的项目越来越大，解决的问题越来越复杂，我更加不知道该如何实现了。幸亏我只是一名普通的程序员，在我上面有项目经理和软件工程师在前面冲锋陷阵。他们会告诉我具体的实现方法，我只需要遵循他们的方案进行编码就可以了。

直到后来有一天，一位前辈告诉我说程序的“灵魂”是算法，只有掌握了算法，才能轻松地驾驭程序。原来编程不是按部就班，正确的做法是选择一种算法去实现功能，这个算法正是解决问题的有力武器，也是对一个项目“下手”的第一步。算法能够告诉我在面对一个应用时用什么思路去实现，有了这个思路，编码工作只需遵循该思路去实现即可。算法是一个程序的编码思路，是程序员解决问题的“指路明灯”。

1.1.1 算法的特征和发展由来

算法的英文名称是Algorithm，这个词在1957年之前在《韦氏新世界词典》中还未出现，只能找到带有它的古代含义的较老形式的“Algorism”（算术），是指用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。

在一本早期的德文数学词典《数学大全辞典》中给出了算法的详细定义：

“在这个名称之下，组合了4种类型的算术计算的概念，即加法、乘法、减法、除法。”拉丁短语Algorithmus Infinitesimalis（无限小方法），在当时就用来表示Leibnitz（莱布尼兹）所发明的以无限小量进行计算的微积分方法。

在1950年，Algorithm一词经常同欧几里得算法联系在一起。这个算法就是在欧几里得的《几何原本》中所阐述的求两个数的最大公约数的过程，即辗转相除法。从此以后，Algorithm这一叫法一直沿用至今。

长期以来，算法这门科学得到了长足的发展。根据经验和发展结论得出，算法应该具有如下5个重要的特征。

（1）有穷性：保证执行有限步骤之后结束。

（2）确切性：每一步骤都有确切的定义。

（3）输入：每个算法有零个或多个输入，以刻画运算对象的初始情况。所谓零个输入是指算法本身舍弃了初始条件。

（4）输出：每个算法有一个或多个输出，显示对输入数据加工后的结果。没有输出的算法是毫无意义的。

（5）可行性：在原则上算法能够精确地运行，进行有限次运算后即可完成一种运算。

1.1.2 何为算法

为了理解什么是算法，先看一道有趣的智力题。

“烧水泡茶”有如下五道工序：

1. 烧开水，2. 洗茶壶，3. 洗茶杯，4. 拿茶叶，5. 泡茶。

烧开水、洗茶壶、洗茶杯、拿茶叶是泡茶的前提。其中烧开水需要15分钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需要1分钟。

下面是两种“烧水泡茶”的方法。

方法1

第1步：烧水。

第2步：水烧开后，洗茶具，拿茶叶。

第3步：沏茶。

方法2

第1步：烧水。

第2步：在烧水的过程中，洗茶具，拿茶叶。

第3步：水烧开后沏茶。

问题：比较这两种方法有何不同，并分析哪种方法更优。

上述两种方法都能最终实现“烧水泡茶”的功能，每种方法的3个步骤就是一种“算法”。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。