烤蛋糕与计算机算法

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

算法指定执行特定计算或任务的一系列步骤。算法最初是作为数学的一部分而诞生的。“算法(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,...等更多数字的列表也是正确的。

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181028G0XO4E00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券