1.1 算法的基础

知识点讲解：光盘：视频讲解\第1章\算法的基础.avi

自然界中的很多事物并不是独立存在的，而是和许多其他事物有着千丝万缕的联系。就拿算法和编程来说，两者之间就有着必然的联系。在编程界有一个不成文的原则，要想学好编程就必须学好算法。要想获悉这一说法的原因，先看下面对两者的定义。

（1）算法：是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。

（2）编程：是让计算机为解决某个问题而使用某种程序设计语言编写程序代码，并最终得到结果的过程。为了使计算机能够理解人的意图，人类就必须将需要解决的问题的思路、方法和手段通过计算机能够理解的形式“告诉”计算机，使计算机能够根据人的指令一步一步去工作，完成某种特定的任务。编程的目的是实现人和计算机之间的交流，整个交流过程就是编程。

在上述对编程的定义中，核心内容是思路、方法和手段等，这都需要用算法来实现。由此可见，编程的核心是算法，只要算法确定了，后面的编程工作只是实现算法的一个形式而已。

1.1.1 算法的特征

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

随着时间的推移，算法这门科学得到了长足的发展，算法应该具有如下5个重要的特征。

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

② 确切性：每一步骤都有确切的定义。

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

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

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

1.1.2 何为算法

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

“烧水泡茶”有如下5道工序：①烧开水、②洗茶壶、③洗茶杯、④拿茶叶、⑤泡茶。

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

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

1．方法1

第一步：烧水。

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

第三步：沏茶。

2．方法2

第一步：烧水。

第二步：烧水过程中，洗刷茶具，拿茶叶。

第三步：水烧开后沏茶。

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

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