烤蛋糕与计算机算法

有中学同学学了一阵计算机编程后，问了我一个问题：计算机算法与数学的解题方法有什么不同，到底什么是计算机算法呢？本文就对计算机算法做一个基本的解释。

算法指定执行特定计算或任务的一系列步骤。算法最初是作为数学的一部分而诞生的。“算法（Algorithm）”一词来自于某一位阿拉伯作家，但目前这个词与计算机科学密切相关，它用来指挥计算机执行各种任务。

算法类似于食谱。食谱通过执行许多步骤告诉您如何完成任务。例如，烤蛋糕的步骤是：预热烤箱；彻底混合面粉，糖和鸡蛋；倒入烤盘；烘焙直到完成等等。

但是，“算法”是一个技术术语，具有比“食谱”更具体的含义。一般来说，算法必须具备下列属性：

算法是明确的描述，清楚地表明了必须实现的任务。在上述配方的例子中，诸如“烘焙直到完成”之类的步骤是模糊的，因为它不能解释“完成”的含义。必须赋予“完成”更明确的描述，例如“烘烤直到奶酪开始泡沫”、或者“烘烤半小时”，这样才能成为“算法”的一个步骤。再举一个例子，在计算算法中，不能有诸如“选择一个巨大的数字”之类的步骤，因为它是模糊的：什么才是大的数字？ 1万，1亿或100？每次选择的数是否必须不同？或者每次运行时都可以使用相同的数字？

算法可能要求有一组确定的输入。例如，它可能需要两个数字，其中两个数字都大于零。或者它可能需要输入一个单词，或零个或多个数字的列表。

如果算法对其输入有明确要求（称为前置条件），则必须满足该要求。例如，前提条件可能是算法仅接受正数作为输入。如果不满足前提条件，则算法可能会产生错误答案或永不终止而失败。

算法会产生一组期望的输出。它可能会输出两个数字中较大的一个，一个单词的全大写形式，或者数字列表的排序结果。

保证算法能终止并产生结果，并且在有限时间后停止。如果一个算法永远运行，它可能将不会有什么用处，因为你可能永远不会得到答案。大多数算法都能保证产生正确的结果。如果某个算法在99％的时间内可以返回最大数字，但在1％的时间内会失败并返回最小数字，这样的算法一般不会有什么用处。

算法研究是计算机科学的基础部分，它经常会研究下面的问题，例如：

是否实际存在完成某个给定任务的算法？

如果有人提出算法来解决该任务，我们是否确定该算法适用于所有可能的输入?

这个算法需要运行多长时间？它需要多少内存空间？

我们知道可以用该算法解决某个问题，那么这个算法是否是最好的算法？有没有可以更快解决该问题的算法？

......

我们举一个算法的简单例子来说明。

让我们看一个名为find_max（）的非常简单的算法，它可以从一个正数列表L中寻找最大的数字。

问题：给出正数列表，返回列表中的最大数字。

输入：正数列表L，此列表必须至少包含一个数字。

输出：数字n，它是该输入列表中的最大数字。

一个简单的算法描述如下：

将max设置为0。

对于列表L中的每个数字x，将其与max进行比较。如果x较大，则将max设置为x。

max现在设置为列表中的最大数字。

用Python语言来实现：

def find_max (L):

max = 0

for x in L:

if x > max:

max = x

return max

那么这个算法是否符合上述算法的判别标准？

它是否明确无误？是。算法的每一步都包含基本操作，将每一步转换为Python代码非常容易。

它是否定义了输入和输出？是。

是否保证终止？是。列表L具有有限长度，因此在查看列表的每个元素之后，算法将停止。

它能产生正确的结果吗？是。可以给出非常正式的证明。不过，在本文中将只对它的替代递归算法给出一个比较简要的证明（见下文）。

可以有许多不同的算法来解决同样的问题。我们来看用递归实现 find_max（）的另一个版本，下面是find_max（）的替代递归算法：

如果L的长度为1，则返回L的第一项。

将v1设置为L的第一项。

将v2设置为对L的其余部分执行find_max（）的输出。

如果v1大于v2，则返回v1。否则，返回v2。

下面是它的Python语言实现的版本：

def find_max (L):

if len(L) == 1:

return L[0]

v1 = L[0]

v2 = find_max(L[1:])

if v1 > v2:

return v1

else:

return v2

对于上述递归算法，让我们再来问刚才的问题：

它是否明确无误？是。每个步骤都很简单，并且很容易翻译成Python。

它是否定义了输入和输出？是。

是否保证终止？是。如果L的长度为1，则算法显然终止。如果L有多个元素，则调用find_max（），其中列表的一个元素更短，结果用于计算。

对find_max（）的嵌套调用是否总是终止？是。每次调用find_max（）时，列表都会缩短一个元素，因此最终列表的长度为1，嵌套调用将结束。

最后，它会产生正确的结果吗？是。

下面用中学生都会的数学归纳法来证明它。

考虑一个长度为1的列表。在这种情况下，最大的数字也是列表中唯一的数字。 find_max（）返回此数字，因此对于长度为1的列表是正确的。

现在考虑一个较长的长度列表N + 1，其中N是一些任意长度。假设我们已经证明find_max（）对于所有长度为N的列表都是正确的。因此，v2的值将是列表其余部分中的最大值。有两种情况需要考虑：

情况1：列表的第一项v1是最大的项目。在这种情况下，列表中没有大于v1的其他值。我们假设find_max（）在列表的其余部分执行时是正确的，因此它返回的值将小于v1。因此，if v1> v2比较将为真，因此将采用第一个分支，返回v1。这是列表中最大的项目，因此在这种情况下算法是正确的。

情况2：列表的第一项v1不是最大的项目。在这种情况下，列表中至少有一个值大于v1。 find_max（）对于列表其余部分的缩短版本是正确的，返回它包含的最大值，因此该值必须大于v1。因此，if v1> v2比较将为false，因此将采用else分支，返回v2，列表其余部分中的最大值。这种情况假设v1不是最大值，因此v2因此是最大值，并且在这种情况下算法也是正确的。

在这两种情况下，我们现在已经证明，如果find_max（）对于长度为N的列表是正确的，那么它对于长度为N + 1的列表也是正确的。在我们的论证的第一部分中，我们已经证明find_max（）对于长度为1的列表是正确的。因此，它对于2个元素长，3个元素和4,5,6，...等更多数字的列表也是正确的。

我们发现它对于单元素列表的简单情况是正确的，然后表明它对于一定大小的问题是正确的，这种证明称为归纳证明，它是众所周知的一种数学证明方法。当然并非所有算法都适合归纳证明方式，我们只是用它来举例而已。