小学奥数 -- 分油问题通解
题目：三个桶。
10升桶，7升桶，3升桶。
10升桶里面装了10升油。
另外两个桶是空的。
没有其他量具，只能依靠倒满或倒空，把油。
不考虑油粘着桶壁剩余的问题。
请问，给定要求之后，分油的步骤如何？
比如，分成相同的两份，5升和5升。
比如，分成1升和9升。
比如，分成2升和8升。
比如，分成4升和6升。 解答：
如果只是要求特解的话，这类问题的解法就比较直接。
定好一个循环方向，绝不回头，一步步倒下去，有限步骤后，就会分好。
比如，
10升桶 -> 7升桶 -> 3升桶 -> 10升桶 -> 7升桶 -> 3升桶 -> ....
不要有任何反方向。
7升桶 -> 10 升桶。
3升桶 -> 7 升桶。
这种反方向，等于抵消之前的步骤，会增加步数，要绝对避免。 又比如，
10升桶 -> 3升桶 -> 7升桶 -> 10升桶 -> 3升桶 -> 7升桶 -> ....
不要有任何反方向。
3升桶 -> 10 升桶。
7升桶 -> 3 升桶。
这种反方向，等于抵消之前的步骤，会增加步数，要绝对避免。 以上是特解。
如果要通解的话，就需要考虑得通透一点。
难度不高，但是，比较复杂，涉及到数论中同余问题、剩余理论中的算法概念。 首先，那个10升桶，实际上并没有在分油过程中起度量作用，只是一个临时过渡容器而已。
只要那个桶大于等于10升，对于问题本身都没有影响。
如果把10升桶换成11升桶、12升桶、100升桶，问题本质不会发生变化。
（当然，总油量不变，还是10升） 理解了这一点之后，剩下的问题就是3升桶和7升桶之间的关系了。
以下这个关系，比较难以理解。
由于水平所限，我也没有办法一言两语说清楚。
我直接给出解法描述。 这个问题，可以转化为一个 二元一次 不定方程问题。
3x + 7y = 某一份油
求 x 和 y 的整数解。
x 和 y 可以为负数或正数。
如果为负数，表示 从本桶中 倒出 到 10升桶 几次。
如果为正数，表示 从另一个度量桶中 倒入 本桶 几次。
比如，分成相同的两份，5升和5升。
3x + 7y = 5
比如，分成1升和9升。
3x + 7y = 1
比如，分成2升和8升。
3x + 7y = 2
比如，分成4升和6升。
3x + 7y = 4
上述这些不定方程的解法，有通用的解法。
没有难度，但是，有复杂度。
解法很简单，就是用于求 最大公约数 的辗转相除法。
无论是分成怎样的两份。
都要从 母问题 开始。
母问题，就是 3x + 7y = 1
解出这个问题之后，其他的问题，都迎刃而解。 3x + 7y = 1
7 与 3 恰好互质，这个问题有 解。
（如果不互质，最大公约数大于1，就没有整数解。
比如，4x + 6y = 1 就没有整数解。
比如，4x + 6y = 2 就有整数解。
这些都是数论中同余问题、剩余理论中的算法概念。）
辗转相除法
7 / 3 = 2 + 1/3
7 - 2 X 3 = 1
得到一组特解。
x = -2
y = 1
这组特解意味着什么？
意味着，
从 10升桶 倒入 7 升桶 1 次，
从 7 升桶 倒入 3 升桶 2次，就可以把油分出 1 升来。 有了这组特解，就可以得出通解。
x = -2 + 7k
y = 1 - 3k
为什么是这样的通解形式？
代入 3x + 7y = 1 试试就知道了。
3(-2 + 3k) + 7(1 - 3k) = 1
这些都是数论中同余问题、剩余理论中的算法概念。
现在，回到通解。
x = -2 + 7k
y = 1 - 3k
令 k = 1，那么，得到另一组特解。
x = 5
y = -2
这组特解意味着什么？
意味着，
从 10升桶 倒入 3 升桶 5 次，
从 3 升桶 倒入 7 升桶 2 次（7升桶倒满之后，要倒入10升桶） ，
就可以把油分出 1 升来。
这两组特解，绝对值最小，
就是步骤最少的两种解法（分别是两个循环方向）。
下面，再来看均分的情况，每份5升。
即，求解 二元一次 不定方程组 的整数解。
3x + 7y = 5 这个问题的特解，可以直接从 3x + 7y = 1 的一组特解得到。
3x + 7y = 1 的一组特解如下。
x = -2
y = 1
只要分别乘以5，就得到 3x + 7y = 5 的特解。
x = -10
y = 5 这个特解的绝对值较大，不是最少步骤的解法。
先求出通解，再求最小绝对值的特解。
同样的道理，根据特解，得到通解如下。
x = -10 + 7k
y = 5 - 3k
令 k = 1, 那么，
x = -3
y = 2
这组特解意味着什么？
意味着，
从 10升桶 倒入 7 升桶 2 次，
从 3 升桶 倒入 10 升桶 2次，就可以把油分出 5 升来。
现在，回到通解。
x = -10 + 7k
y = 5 - 3k
令 k = 2，那么，得到另一组特解。
x = 4
y = -1
这组特解意味着什么？
意味着，
从 10升桶 倒入 3 升桶 4 次，
从 7 升桶 倒入 3 升桶 1 次（7升桶倒满之后，要倒入10升桶） ，
就可以把油分出 5 升来。 以上这两组特解的绝对值最小，是两个最小步骤的解法（分别是两个不同的循环方向）。
页:
[1]
2