幸福大观园

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

作者: 学父五迁    时间: 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/) Powered by Discuz! X2