有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。 我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。 可以进行的操作是： 把一个容器灌满； 把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）； 用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。 问是否能够通过有限次操作，使得水缸最后恰好有C升水。
这是很经典的智力题,各种倒水,求怎么倒. 网上有很多资料,我稍微总结下.
1 是否有解
是的,不是任意的ABC值都是有解的,比如用4升和6升的容器,倒出5升水,这个方案就是无解的. 总结来说:
倒水方案有解的,充要条件是:
C<=A+B并且
C能被A和B的最大公约数整除
比如上面的例子,4和6的公约数是2,5不能被2整除,所以是无解的. 具体证明过程请看文章后面的参考文献
2 解法
有一个很简单的思路,在AB两个容器中,假设A<B,那么我们不停地用A往B中加水,溢出的时候,就把B清空,把A中多余部分导入B中.具体流程描述如下
A%B=x
2A%B=y
...
...
nA%B=z
知道最后余数z等于C,就停止
用一个具体的例子
A=5,B=9,C=7
5%9=5
10%9=1
15%9=6
20%9=2
25%9=7
也就完成了查找 当然这个方法不是步数最少的解法