量杯倒水

这个问题常见于趣味题和面试题，题意大概是这样的:有两个只有最大刻度的量杯(如10毫升，3毫升)， 并且有无限量的水。求怎么倒出x毫升的水?

思路与猜想

首先我们来操作一下，例如倒出4毫升的水,同时把大小量杯表示为a,b

1. b装满，倒入a(a有3ml,b有0ml)
2. b再装满，倒入a(a有6ml,b有0ml)
3. b再装满，倒入a(a有9ml,b有0ml)
4. b再装满，倒入a(a有10ml,b有2ml)
5. a倒掉，b倒入a(a有2ml,b有0ml)
6. 重复2-4的动作(此时a有10ml,b有1ml)
7. a倒掉，b倒入a(a有1ml,b有0ml)
8. b装满，倒入a(a有4ml,b有0ml)

假如我们再继续操作的话，还可以找到7ml,这样0ml~10ml的体积都是可以测量出来的。这是不是一般规律?

虽然我们进行了许多次操作，但操作是有规律的:b总是往a倒水直到a装满，这时b会剩余一点。 这样才能得到不同于a,b的体积。我们重复这个操作的过程，不考虑a装满的情况， 在a中出现的水t可以用t=mb-na来表示(a>t>=0,m>=0,n>=0)。其中m可以表示为往a倒水的次数， n表示a装满的次数。

首先考虑一下a,b不是互质的情况，假设他们的最大公约数为u,那么狠显然没法倒出t小于u的体积。 这种情况可以归结为两边除去u的情况。

现在再来考虑a,b互质的情况，我们需要考虑的是，对于t，是否都存在m,n使t=mb-na成立？

贝祖定理

我们从数学归纳法出发，很明显t=0的情况是满足要求的，假设t=1的要求也能够满足， 那么有t=mb-na成立就可以推导出t+1=m1b-n1a+m2b-n2a也是符合mb-na的。

如何证明存在m,n使得mb-na=1?这个倒不用自己动手，有个叫贝祖定理的数学定理，可以很容易推导出这个结论。

从wiki上看到的资料，贝祖定理可以证明a,b互质，存在xa+yb=1，其中x,y为整数 不过好像跟我们的要求有点出入。不过没关系，很显然x,y如果没有不等于0的话，必须有个是负数，

如果x是负数，显然符合要求，如果y是负数，那么总存在一个数k(k>0)使得y+ka>0,那么 1=xa+yb=xa+yb-kab+kab=(x-ka)a+(y+ka)b,这样也是可以符合要求的。

所以，按照我们的操作方式，假设a,b的最大公约数为u,就可以找到0ml,uml,2uml…aml的体积。

再思考

如果有多个量杯，情况会是怎样?

要倒出一定量的水，上述操作是否是最快的?