量水问题中的算法——《中小学教材教学》（算法园地专栏第一篇）
2019-06-18 09:48阅读：
量水问题中的算法
南京大学 陈道蓄
设想有人给你两只桶，容积分别是9升和6升，但没有刻度，要求你只能通过在它们之间的倒腾，量出一个3升的水来。怎么办？那应该很容易：
1.
把9升桶装满；
2.
向6升桶倒，直到满；
3.
9升桶中剩下的即为3升。
这没有什么悬念。如果给你的桶一只7升，一只5升，要求倒出一升的水来呢？你大概需要想一想了，但也不难，也能很快给出一个“操作序列”——也就是人们通常说的算法了。不过我们下面要讨论的是，如果给你的桶一只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，x,y满足：ax+by=1
对于任给的两个非负整数，如果其中一个是0，我们立刻就知道最大公约数就等于另一个数。
如果a,b都不是0，很容易理解，x,y中一定有一个是负值。这一点使我们一定可以给出一个上述倒水问题的实施序列。
为了更容易解释我们的算法，我们先解第一个问题。然后只需稍加拓展就可以用一个算法同时解上述两个问题。
那么如果两个数都不是0呢？我们用gcd(a,b)表示a,b的最大公约数，a
mod
b表示a除以b的余数(注意：如果a则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:
i
|
1
|
2
|
3
|
4
|
5
|
6
|
xi
|
1
|
0
|
1
|
-1
|
3
|
-4
|
yi
|
0
|
1
|
-1
|
3
|
-4
|
7
|
由此可知：(-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升的水，并且能够输出具体操作的过程。这里需要注意何时该充满一个水桶，何时该出空一个水桶，并跟踪半满的状况。
参考文献
Thomas H.Cormen: Introduction to Algorithms, 3rd
ed., The MIT Press, 2009, 第31章
数论算法
