点我
点我
文章目录
  1. 1 是否有解
  2. 2 解法

解决倒水问题

有两个容器,容积分别为A升和B升,有无限多的水,现在需要C升水。
我们还有一个足够大的水缸,足够容纳C升水。起初它是空的,我们只能往水缸里倒入水,而不能倒出。
可以进行的操作是:
把一个容器灌满;
把一个容器清空(容器里剩余的水全部倒掉,或者倒入水缸);
用一个容器的水倒入另外一个容器,直到倒出水的容器空或者倒入水的容器满。
问是否能够通过有限次操作,使得水缸最后恰好有C升水。

这是很经典的智力题,各种倒水,求怎么倒.
网上有很多资料,我稍微总结下.

1 是否有解

是的,不是任意的ABC值都是有解的,比如用4升和6升的容器,倒出5升水,这个方案就是无解的.
总结来说:

1
2
3
倒水方案有解的,充要条件是:
C<=A+B并且
C能被A和B的最大公约数整除

比如上面的例子,4和6的公约数是2,5不能被2整除,所以是无解的.
具体证明过程请看文章后面的参考文献

2 解法

有一个很简单的思路,在AB两个容器中,假设A<B,那么我们不停地用A往B中加水,溢出的时候,就把B清空,把A中多余部分导入B中.具体流程描述如下

1
2
3
4
5
A%B=x
2A%B=y
...
...
nA%B=z

知道最后余数z等于C,就停止
用一个具体的例子
A=5,B=9,C=7

1
2
3
4
5
5%9=5
10%9=1
15%9=6
20%9=2
25%9=7

也就完成了查找
当然这个方法不是步数最少的解法

倒水问题
欧几里得和扩展欧几里得算法
最大公约数的三种解法

支持一下
扫一扫,试试看
  • 微信扫一扫
  • 支付宝扫一扫