f(Program,Poet)=Programet

可能大家都遇到过这个问题，就是给你两杯具，一个可以装a升水的A，一个可以装b升水的B。现在我们要利用这两个杯具得到n升水 ，你能做的是要么把其中一个杯具装满水，要么把其中一个杯具的水完全倒掉续上面的步骤…这样，总会有一步，可以得到想要的结果。（当然n不能大于A、B容量较大的那个）。

这是我上个星期在ZOJ上做的一道题。如果明白一点数论的知识，这道题是非常简单的。

首先我们考虑这么一种很简单的情况，假设杯具A可以装2升水，杯具B可以装4升水，那我们可不可以得到1升水？显然不能吧。再复杂一点，我们假设杯具A容量4升，杯具B容量7升，我们是否可以得到6升水？一种解法是，先把装满B，然后用B中的水倒满A，然后掉A中的水，在把B中剩下的倒到A中，此时A中有3升水。再装满B，用B中的水倒满A，然后在B中就有6升水了。事实上我们可以得到1-7中，任一数量的水。

我们先岔开一下，说点数论的东西。

首先我们知道一个显然得不能再显然的结论：对于任一整数n，n=a*x+b*y，其中a，b，x，y都是整数（如果你怀疑的话，可以去看看《陶哲轩实分析》前几章关于数系构造的部分）。现在我们多加点限制条件：a，b是固定的正整数，x，y是变量，且为非零的。现在n还可能是任一整数么（这个时候我们称n为a，b的线性组合）？取a=3，b=6，这时n只可能为3的倍数。这时我们很容易推出这么一个结论：只要a与b不互质，那么n就是a，b的公约数的倍数[1]。现在我们就要想如果a与b互质的时候，n可以是什么数。首先n还是可以为其中一个的倍数，因为我们可以取另一个数的系数x或y为那个数或那个数倍数。如果n不是它们其中的倍数了，那会是哪些数。我们可以做个大胆的假设，1可不可用a*x+b*y表示出来。如果可以的话，那么就意味着任一整数都可以表示出来了，也就是说n可以是任一整数。

下面我们尝试一下

两个互质自然数的最大公约数是1，相信大家都知道。在很久很久以前的古希腊，有个叫做欧几里得的伟大数学家提出过一个方法，可以快速得到两个自然数的最大公约数。现在我们把这个方法应用到两个自然数互质这种特殊情况。假设b>a，我们用a除b可以得到一个商m1和一个余数r1，可以证明r1与a必然互质（为什么）。然后我们用r1除a得到m2和r2，接着用r2除r1得到m3和r3…亦即用上次得到余数除上次的除数。由于余数r是非负的，且是递减的，就存在某个rk=0，那么rk-1必定为1（为什么）。好了，现在我们得到{m}和{r}。r1=b-m1*b，用数学归纳法可以证明每一个ri都是a，b的线性组合。所以现在我们证到了1是两个互质正整数的线性组合。因为每一个整数都是1的倍数，所以我们就可以断言，每一个整数都是两个互质正整数的线性组合。

对于两个正整数的线性组合和公约数的关系，还有一个更强的结论：两个正整数的最大公约数是这两个正整数的线性组合。大家有兴趣的话，可以去证明一下。

现在我们回到装水的问题上面。

在两个桶都没有水的时候，只有0升水；装满A得到a升，装满B得到b升；复杂一点，装满B（假设b>a），用B的水装满A，这样得到b-a升。那桶里的水的量会不会就是a，b的线性组合呢？的确是如此的。其实虽然这点初看起来非常不明显，但是如果有了这个猜想，要证明它就变得很简单，用数学归纳法可以快速给出证明（略）。

ZOJ上的这道题有个条件是a，b是互质的，这样一来对于0<=n<=b理论上都是可以得到的。有一个编程策略是，把A装满，然后用A的水装B，如果B没满，就继续用A的水装B，每一次操作都检查是否得到想要的结果；如果B满了，而想要的结果没出现，继续重复上面的步骤……这样，总会到某一步，可以得到想要的结果。

本文由 Malloc 创作，转载或引用前请联系我们。

相关文章：

1. 明天去吃自助餐的童鞋注意啦！

2010年6月1日 星期二