本文转自《中小学教材教学》2019年6月（总第54期）算法园地

编者按：随着我们进入信息化社会，计算机科学成为中小学教学内容的显学，将只是时间问题。2018 年教育部颁布的高中新课标朝这个方向迈出了重要一步。计算机科学在中小学的重要性，近期要比肩物理、化学、生物，长期将类同语文和数学。其中，体会并追求这一门课的科学性（而不满足于其工具性）是一个关键。从事相关教学工作的教师们，应当不断提高自己以适应新的形势要求。也只有当教师具备了必要的素养，计算机科学才更有希望在基础教育中发挥与时代相适应的作用。

北京大学计算机系原系主任李晓明教授、南京大学计算机系原系主任陈道蓄教授商议在我刊开办一个关于计算机算法的专栏，旨在为在中小学从事信息技术课教学的教师提供一些既有思想性，也有实用性的材料，希望有助于相关教师的工作和计算机科学素养的提高。

专栏的读者定位是对算法问题有兴趣的中小学教师，内容的铺陈将努力做到通俗性、趣味性和严谨性相结合。每期的算法独立成篇，每月介绍一个算法，大体按照如下六个方面展开：应用背景、算法描述、实例模拟、性质分析、思考问题、参考代码。如果你以前学过算法，在这里会看到一种不同的视野；如果你以前没学过算法，则可以通过对每月一个算法的学习，既领悟到算法思想的精髓，又形成算法实战的能力。

本刊编辑部建有专栏的讨论社区，跟踪专栏的读者群，并每年组织一次工作坊，与两位教授及更多计算机界大家面对面交流。

设想有人给你两只桶，容积分别是9 升和6 升，但没有刻度，要求你只能通过在它们之间倒腾，量出3 升水来。怎么办？那应该很容易：

1. 把9 升桶装满；

2. 用9 升桶里的水装满6 升桶；

3. 9 升桶中剩下的水即为3 升。

这没有什么悬念。如果给你一只7 升、一只5 升的桶，要求量出1 升的水来呢？你大概需要想一想了，但也不难，很快就能给出一个“操作序列”———也就是人们通常说的算法了。不过我们下面要讨论的是，如果给你一只a 升、一只b 升的桶，要求倒出t 升的水来，是否有可能？如果可能，其实施的步骤如何？这就成为一个计算机算法问题了。

下面，我们还是从具体的情形开始，逐步得到一般的解。

假设有两只桶，容积分别是9 升和6 升，但桶没有刻度，所以只有当桶全满时，我们才能直接判定其中的水量。很容易推想出如果并非全满，只有在很有限的条件下才能间接判定某个桶中的水量。

我们假设有足够的水源，可以向某个桶中倒水（确保不溢出），也可以从一个桶中将水倒入另一个桶，或者倒回水源。

我们的第一个问题是，利用这两个桶能够精确量出的最小水量是多少？显然只需要考虑正整数值。由于9 和6 的最大公约数是3，我们不妨定义一个可称之为“超升”的单位，每“超升”等于普
通的3 升。于是原来的两个桶容量分别是3 “超升”和2 “超升”。可以精确量出的最小水量是1 “超升”，即3 升。

我们来回顾一下简单的数论知识：任给两个正整数a、b，表达式

ax＋by （x、y 为整数）

称为a、b 的线性组合。既然式子中每项均可被a、b 的最大公约数整除，显然这个式子的最小正值就是a、b 的最大公约数。这就说明不可能量出少于3 升（即1 超升）的水来。（为什么上述线性组合可以看作在两个桶之间倒水的任意过程的抽象，留给读者考虑。）

接下来我们进一步考虑：如果任给一个正整数t，你是否能利用这两个没有刻度的桶量出恰好t升水。

乍看上去这个问题有点复杂。可稍微细想一下便可知，只要能量出恰好1 升水，只要将量出1 升的过程重复若干次便可以量出任意正整数升水。

那么是否能量出1 升水呢？我们先看一个简单的例子：假设有A、B 两个桶，其容积分别为a＝7升，b＝5 升。略试一下就可能给出如下操作序列：

1. B 充满，现在B 中有5 升水，A 为空；

2. 从B 向A 中倒5 升，现在B 又恢复为空，A 中有5 升；

3. 再将B 充满；

4. 从B 向A 中倒2 升（A 已满），现在B 尚余3 升，随即将A 出空；

5. 将B 中剩下的3 升水全部倒入A，现在A 中有3 升，B 又恢复为空；

6. 再将B 充满；

7. 从B 向A 中倒4 升（A 已满），随即将A 出空；

8. 此时B 中的水恰好为1 升。

其实第7 步中是否将A 出空对结果没有影响，但这使我们能清楚地看出在这个过程中我们总是在B 空时将其充满（3 次），而A 满时随即出空（2 次），其数学模型即：5×3－7×2＝1。

回到我们前面一般的情况，任给两个正整数a、b （对应两个水桶的容积），如果我们能找到两个整数x、y，满足ax＋by＝1，我们就能量出1 升水（实施过程我们后面再说）。那么这样的x、y 一定有吗？根据前面提到的数论知识我们知道，只要a、b 的最大公约数是1 （即它们互质）。我们就一定能找到适当的x、y，使上面的线性组合式值为1。

现在我们就将问题归结到：

1. 任给两个非负整数，它们的最大公约数是什么，是1 吗？

2. 如果是1，那么需要的x、y 是什么？

怎样能让计算机帮我们解这个问题呢？计算机通过算法解题，首先得明确什么是“问题”，或者更具体地说什么是“算法问题”。

在小学数学课上，我们可能会让同学们计算“18 和27 的最大公约数是多少”。对于计算机算法来说这不是“问题”，而是“求最大公约数问题”的一个实例。最大公约数问题是包含无穷多个这样

实例的集合。那么问题究竟该如何表述呢？

我们将问题表述为对条件和结果的精确描述，称之为输入／输出。输入说明所有允许的实例必须满足的条件，而输出则给出对任一合法输入算法给出的结果必须满足的条件（注意：这里隐含地要求算法必须给出结果）。

这样，上面归结出的问题可表述为：

问题1：

输入：两个不全为零的非负整数a、b （在水桶的例子中只会出现正整数，我们的模型扩展为非负整数）

输出：整数d＝gcd （a，b）

问题2：

输入：两个非负整数，且gcd （a，b）＝1

输出：两个整数x、y，满足ax＋by＝1

对于任给的两个非负整数，如果其中一个是0，我们立刻就知道最大公约数就等于另一个数。

如果a、b 都不是0，很容易理解，x、y 中一定有一个是负值。这一点使我们一定可以给出一个上述倒水问题的实施序列。

为了更容易解释我们的算法，我们先解第一个问题。然后只需稍加拓展就可以用一个算法同时解上述两个问题。

那么如果两个数都不是0 呢？我们用gcd （a，b）表示a，b 的最大公约数，a mod b 表示a 除以b 的余数（注意：如果a＜b，则a 除以b 商为0，余数就是b）。考虑到a mod b 可以表示为a－qb，这里q 是一个整数，即b 整除a 的商，我们很容易证明：gcd （a，b）可以整除gcd （b，a mod b），反之，gcd （b，a mod b）也可以整除gcd （a，b）。这就意味着这两个最大公约数相等。

这个数学结论的算法意义何在呢？其实，既然gcd （a，b）＝gcd （b，a mod b），而且a mod b一定小于b，我们就可以用递归的方法计算gcd （a，b）。

下面的算法称为欧几里得算法，是公元前300 年前后古希腊的欧几里得提出的计算最大公约数的方法（计算机历史学者认为这是我们知道的最古老的算法）：

Euclid （a，b） ／／a、b 是不全为0 的非负整数

1.if b＝0

2.then return a ／／递归的终止条件

3.else return Euclid （b，a mod b） ／／递归，用gcd （b，a mod b）作为结果

如果输入的是前面水桶问题中提到的7 和5，则计算过程如下：

gcd （7，5）＝gcd （5，2）＝gcd （2，1）＝gcd （1，0）＝1

这里执行递归调用3 次。读者可以考虑一下，为什么这个算法并不要求输入a 大于b。

前面的分析可能已经使读者相信这个算法一定是正确的。当真如此吗？

所谓算法正确是指：如果输入满足规定的条件，算法一定能给出正确的解（即输出满足规定的条件）。这里隐含着一个要求：算法必须得有输出。所谓“有输出”就是算法必须“终止”。那么欧几里得算法为什么一定会终止呢？为什么不会“永远”递归下去呢？根据余数的数学性质，余数值一定小于除数，这就意味着每递归一次，算法中b 的值一定会严格下降，每次下降的幅度一定是整数。因此经过有限多次递归，b 一定会等于0。根据算法，当b 等于0 便不再继续递归了，直接返回结果。

对于一个计算机算法，除了考虑正确性，我们还关心计算的代价，即复杂性。从时间代价上看，我们关心欧几里得算法对特定的输入究竟要经过多少次递归才能得到结果（b 变成0）。这个问题可不像看上去那么简单。读者不妨先想一想，a、b 值会怎样地影响递归次数的多少，后面我们将讨论斐波那契序列，那时我们再给出一个比较明确的分析结果。

现在我们再来考虑第二个问题，即如何找出线性组合中的两个待定系数x、y。这里必须输出3个值：gcd （a，b），x 和y，算法描述中就用这个顺序表示，为了看上去简洁，令d＝gcd （a，b），d'＝gcd （b，a mod b）。

首先看递归终止条件，即b＝0，此时d（a，0）＝ax＋by＝a，所以输出是（a，1，0）。欧几里得算法之所以非常简单，是因为d 和d'相等，直接输出即可。我们现在需要搞清楚：如果d'＝bx'＋（a mod b）y'，d＝ax＋by，那么如何用x'与y'来表示x、y 呢？

因为d＝d'，所以：

d＝bx'＋ （a mod b）y'＝bx'＋ （a－|a／b |b）y'＝ay'＋b （x'－|a／b |y'）

因此：x＝y'，y＝x'－|a／b |y'；这里|a／b |是a 除以b 的商的整数部分，所以a mod b＝a－|a／b |b

直接将这两个关系式加入欧几里得算法，便可得到能同时计算x、y 的扩充的欧几里得算法：

Extended－Euclid （a，b）

1.if b＝0

2.then return （a，1，0）

3. （d'，x'，y'）←Extended－Euclid （b，a mod b）

4. （d，x，y）←（d'，y'，x'－|a／b |y'）

5.return （d，x，y）

我们来计算gcd （19，11），经过5 次递归，依次为（11，8）， （8，3）， （3，2）， （2，1）， （1，0），得到最大公约数d＝1 （当然对于这么小的数，我们不计算也能看出它们互质）。假设我们从下往上表示相应的（xi，yi），i＝1，2，…，6：

由此可知：（－4）×19＋7×11＝1。

回到量水的问题，假如我们有两个容量分别为19 升和11 升的水桶。通过上述计算可知，将容量为11 升的桶充满7 次，容量为19 升的桶出空4 次，就得到了1 升水。任给正整数t，利用这两个水桶将上述过程重复t 次，我们就可以量出t 升水来。

如果a 和b 的最大公约数d＞1，在本文前面提到过，那我们就不可能量出小于d 的水量来。而且，同样的思路告诉我们，可以量出的只能是d 的倍数，即“超升”数。具体过程则和d＝1 时完全一样。

在这个基础上你能否编写一个算法，不但可以判断给出的水桶条件（a，b）是否能对任意正整数t，量出恰好t 升的水，并且能够输出具体操作的过程。这里需要注意何时该充满一个水桶，何时该出空一个水桶，并跟踪半满的状况。

参考文献：

[1]Thomas H.Cormen Introduction to Algorithms [M].Cambridge：The MIT Press，2009.

（作者系南京大学软件学院原院长，计算机系原系主任。）