幸福大观园

标题: 小学奥数 -- 分油问题通解 [打印本页]

作者: 学父五迁 时间: 2016-1-28 09:45:41 标题: 小学奥数 -- 分油问题通解

题目：

三个桶。
10升桶，7升桶，3升桶。
10升桶里面装了10升油。
另外两个桶是空的。
没有其他量具，只能依靠倒满或倒空，把油。
不考虑油粘着桶壁剩余的问题。
请问，给定要求之后，分油的步骤如何？
比如，分成相同的两份，5升和5升。
比如，分成1升和9升。
比如，分成2升和8升。
比如，分成4升和6升。

作者: 学父五迁 时间: 2016-1-28 09:46:10

解答：

如果只是要求特解的话，这类问题的解法就比较直接。
定好一个循环方向，绝不回头，一步步倒下去，有限步骤后，就会分好。

作者: 学父五迁 时间: 2016-1-28 09:46:30

比如，

10升桶 -> 7升桶 -> 3升桶 -> 10升桶 -> 7升桶 -> 3升桶 -> ....

不要有任何反方向。
7升桶 -> 10 升桶。
3升桶 -> 7 升桶。
这种反方向，等于抵消之前的步骤，会增加步数，要绝对避免。

作者: 学父五迁 时间: 2016-1-28 09:46:42

又比如，

10升桶 -> 3升桶 -> 7升桶 -> 10升桶 -> 3升桶 -> 7升桶 -> ....

不要有任何反方向。
3升桶 -> 10 升桶。
7升桶 -> 3 升桶。
这种反方向，等于抵消之前的步骤，会增加步数，要绝对避免。

作者: 学父五迁 时间: 2016-1-28 09:46:56

以上是特解。
如果要通解的话，就需要考虑得通透一点。
难度不高，但是，比较复杂，涉及到数论中同余问题、剩余理论中的算法概念。

作者: 学父五迁 时间: 2016-1-28 09:47:13

首先，那个10升桶，实际上并没有在分油过程中起度量作用，只是一个临时过渡容器而已。
只要那个桶大于等于10升，对于问题本身都没有影响。
如果把10升桶换成11升桶、12升桶、100升桶，问题本质不会发生变化。
（当然，总油量不变，还是10升）

作者: 学父五迁 时间: 2016-1-28 09:47:35

理解了这一点之后，剩下的问题就是3升桶和7升桶之间的关系了。
以下这个关系，比较难以理解。
由于水平所限，我也没有办法一言两语说清楚。
我直接给出解法描述。

作者: 学父五迁 时间: 2016-1-28 09:47:57

这个问题，可以转化为一个二元一次不定方程问题。

3x + 7y = 某一份油

求 x 和 y 的整数解。
x 和 y 可以为负数或正数。

如果为负数，表示从本桶中倒出到 10升桶几次。

如果为正数，表示从另一个度量桶中倒入本桶几次。

作者: 学父五迁 时间: 2016-1-28 09:48:19

比如，分成相同的两份，5升和5升。

3x + 7y = 5

比如，分成1升和9升。

3x + 7y = 1

比如，分成2升和8升。

3x + 7y = 2

比如，分成4升和6升。

3x + 7y = 4

作者: 学父五迁 时间: 2016-1-28 09:48:47

上述这些不定方程的解法，有通用的解法。
没有难度，但是，有复杂度。

解法很简单，就是用于求最大公约数的辗转相除法。

无论是分成怎样的两份。
都要从母问题开始。
母问题，就是 3x + 7y = 1

解出这个问题之后，其他的问题，都迎刃而解。

作者: 学父五迁 时间: 2016-1-28 09:49:05

3x + 7y = 1

7 与 3 恰好互质，这个问题有解。

（如果不互质，最大公约数大于1，就没有整数解。
比如，4x + 6y = 1 就没有整数解。
比如，4x + 6y = 2 就有整数解。
这些都是数论中同余问题、剩余理论中的算法概念。）

作者: 学父五迁 时间: 2016-1-28 09:49:33

辗转相除法

7 / 3 = 2 + 1/3

7 - 2 X 3 = 1

得到一组特解。

x = -2
y = 1

这组特解意味着什么？

意味着，

从 10升桶倒入 7 升桶 1 次，
从 7 升桶倒入 3 升桶 2次，就可以把油分出 1 升来。

作者: 学父五迁 时间: 2016-1-28 09:49:49

有了这组特解，就可以得出通解。

x = -2 + 7k
y = 1 - 3k

为什么是这样的通解形式？
代入 3x + 7y = 1 试试就知道了。

3(-2 + 3k) + 7(1 - 3k) = 1

这些都是数论中同余问题、剩余理论中的算法概念。

作者: 学父五迁 时间: 2016-1-28 09:50:12

现在，回到通解。

x = -2 + 7k
y = 1 - 3k

令 k = 1，那么，得到另一组特解。

x = 5
y = -2

这组特解意味着什么？

意味着，

从 10升桶倒入 3 升桶 5 次，
从 3 升桶倒入 7 升桶 2 次（7升桶倒满之后，要倒入10升桶），
就可以把油分出 1 升来。

作者: 学父五迁 时间: 2016-1-28 09:50:29

这两组特解，绝对值最小，
就是步骤最少的两种解法（分别是两个循环方向）。

作者: 学父五迁 时间: 2016-1-28 09:50:44

下面，再来看均分的情况，每份5升。

即，求解二元一次不定方程组的整数解。

3x + 7y = 5

作者: 学父五迁 时间: 2016-1-28 09:51:04

这个问题的特解，可以直接从 3x + 7y = 1 的一组特解得到。

3x + 7y = 1 的一组特解如下。

x = -2
y = 1

只要分别乘以5，就得到 3x + 7y = 5 的特解。

x = -10
y = 5

作者: 学父五迁 时间: 2016-1-28 09:51:24

这个特解的绝对值较大，不是最少步骤的解法。
先求出通解，再求最小绝对值的特解。

同样的道理，根据特解，得到通解如下。

x = -10 + 7k
y = 5 - 3k

令 k = 1, 那么，

x = -3
y = 2

这组特解意味着什么？

意味着，

从 10升桶倒入 7 升桶 2 次，
从 3 升桶倒入 10 升桶 2次，就可以把油分出 5 升来。

作者: 学父五迁 时间: 2016-1-28 09:51:50

现在，回到通解。

x = -10 + 7k
y = 5 - 3k

令 k = 2，那么，得到另一组特解。

x = 4
y = -1

这组特解意味着什么？

意味着，

从 10升桶倒入 3 升桶 4 次，
从 7 升桶倒入 3 升桶 1 次（7升桶倒满之后，要倒入10升桶），
就可以把油分出 5 升来。

作者: 学父五迁 时间: 2016-1-28 09:52:02

以上这两组特解的绝对值最小，是两个最小步骤的解法（分别是两个不同的循环方向）。

作者: 学父五迁 时间: 2016-1-28 09:52:23

以上这两组特解，是否一定要用按照上述步骤，一步步求出来呢？
不一定，这个问题比较简单，也可以直接试出来。
我给出上述这些步骤，只是为了给出一个通用思路。
换成其他的度量桶（比如，5升桶和7升桶），也都适用。

作者: 学父五迁 时间: 2016-1-28 14:12:58

我把最简单最直接的思路先写出来。
这种思路不考虑整数拼凑，只是一个劲儿地按照一个循环方向倒油。

作者: 学父五迁 时间: 2016-1-28 14:13:06

定好一个循环方向，绝不回头，一步步倒下去，有限步骤后，就会分好。

比如，

10升桶 -> 7升桶 -> 3升桶 -> 10升桶 -> 7升桶 -> 3升桶 -> ....

（产生数据的动作）    10升桶 7升桶 3升桶
（初始）             10       0       0
（10升桶 -> 7升桶） 3          7       0
（7升桶 -> 3升桶）    3          4       3
（3升桶 -> 10升桶） 6          4       0
（7升桶 -> 3升桶）    6          1       3
（3升桶 -> 10升桶） 9          1       0
（7升桶 -> 3升桶）    9          0       1
（10升桶 -> 7升桶） 2          7       1
（7升桶 -> 3升桶）    2          5       3

作者: 学父五迁 时间: 2016-1-28 14:13:24

又比如，

10升桶 -> 3升桶 -> 7升桶 -> 10升桶 -> 3升桶 -> 7升桶 -> ....

（产生数据的动作）    10升桶 3升桶 7升桶
（初始）             10       0       0
（10升桶 -> 3升桶） 7          3       0
（3升桶 -> 7升桶）    7          0       3
（10升桶 -> 3升桶） 4          3       3
（3升桶 -> 7升桶）    4          0       6
（10升桶 -> 3升桶） 1          3       6
（3升桶 -> 7升桶）    1          2       7
（7升桶 -> 10升桶） 8          2       0
（3升桶 -> 7升桶）    8          0       2
（10升桶 -> 3升桶） 5          3       2

欢迎光临幸福大观园 (http://www.xingfudgy.com/)