电脑倒水会怎么样(关于倒水问题)

有两个水壶，一个容积为6升，一个为5升，如何用这两个壶倒出3升的水？

很久很久以前，数学佬在搞NOI的时候，要编程解这个问题，首先要将这个问题转换成数学解。

那么这个问题的数学解释是什么呢？

显然，我们可以看出来，每一次加水和倒水，都是5或6的整数倍。

那么，这个问题相当于，加水或倒水多少个5、6升，可以的到3升？

设5升壶用x次，6升壶用y次，则

本题相当于解方程5x+6y=3

注：x，y为正则用壶装水，为负则将水倒掉

用瞪眼法我就可以得出答案：x=3，y=-2

即用5升壶装水3次，用6升壶倒水2次。

将数学解答转换成日常语言就是：

先将5升壶装满，（5，0）

倒入6升壶中，（0，5）

再将5升壶装满，（5，5）

将6升壶加满，（4，6）

将6升壶倒空，（4，0）

再将5升壶倒到6升壶，（0，4）

将5升壶装满，（5，4）

将6升壶加满，（3，6）

把6升壶倒空，（3，0）

看出来了吗？上面的眼花缭乱的过程核心就是5升壶装水3次，6升壶被加满就倒掉2次。

瞪眼法

当然我们不能满足于瞪眼法，要去寻找瞪眼法背后的数学规律。

数学佬发现，其实我不必要去找5x+6y=3的解，而是要先去找5x+6y=1的解，然后乘3（或者乘-3）即可。

再如，我们将数字改一改，用两个容积为65升和78升的壶，倒出39升的水。

看起来事情麻烦一些，但实际上，65和78的最大公约数为13，我们将13升当成一个单位，则相当于用5单位和6单位的壶倒出3单位的水，这和原题是一样的。

如果用65升和78升的壶，倒出38升的水。

这个问题是无解的，因为我们只能用这两个壶倒出13升为单位的水，而38不是13倍数，是倒不出来的。

这一类问题剥去所有装饰性描述后是：用容量为a,b的两个壶，倒出容量为1的水。

数学核心是：

到实际问题，则让容量小的壶装水，让容量大的壶倒空水即可。

首先，要判定什么样的方程有整数解。

显然，只要a,b互质，也就是最大公约数为1，这个方程就一定有整数解

第二，有没有套路化的解法。

我们来试一个稍微不那么容易瞪眼的数字。

老师发现一个Bug，这两个答案怎么不一样？

显然，

所以，这两组解(-3,5)和(2,-3)其实是同样的。

（作为竞赛，或许会要求倒水次数最小，那么选取(2,-3)就是最优，但这不是核心操作）

老师小时候搞竞赛，非常喜欢解法一，因为竞赛时间紧，要在最短时间内把程序弄出来，显然解法一的代码要短得多，而循环多几次对于电脑根本不在话下。尽管我相信出题人是希望我能用数学味道更浓的辗转相除法。

我们再举一个例子。

下面我要介绍一个秘笈。

我们还是以本题为例。

神奇吗？

（因为连分数都是正数，我就把方程改了改）

说穿了其实也不神奇。转换连分数本身就是辗转相除法嘛！当然，你可以说“神告诉我的”哦。