“倒水问题”的数论解法与暴力解法

1,351 views
Skip to first unread message

Xinyu LIU

unread,
Feb 10, 2014, 10:32:28 PM2/10/14
to pon...@googlegroups.com
“倒水问题”是个经典的题目。例如：给两个水桶，例如一个9升，一个4升，要求用这两个水桶去河里准确打出6升水。

这个题目的通常解法是使用广度优先BFS暴力搜索。但是暴力搜索失去了趣味性。

这类题目的历史很久，桶的容积也有不同的版本，并且在不同的国家都出现过，解决这一问题的主人公也多种多样，有一个版本的主人公是法国数学家、物理学家青年帕斯卡；有一个版本是Simeon Denis Poisson，还有一个版本是好莱坞大片Die-Hard 3，主人公是布鲁斯威利斯和Samuel Jackson。

这道题目还是ACM/ICPC的一道题。在POJ和ZOJ上都有。

在给出系统的解法前，我特别想提一下数学家G. Polya在《怎样解题》（How to solve it）中给出的“倒着干”的方法。这个方法，我们通常称为“倒推法”。

如果希望获得6升水，那么最后一步一定是从9升的桶倒出3升水，为此我们需要4升的桶中剩余1升水。
现在已经可以非常容易的看出：只要从9升的桶，连续向4升的桶倒两次，就可以获得1升水了。剩下的只要把上述倒推的结果正过来就可以了。

Polya的方法很具有启发性，并且倒推法是非常普遍的解题方法。但是具体到倒水问题上，我们还需要给出系统的算法来加以解决。例如：如何用899升和1147升的桶打出2升水？面对这样的数字我们必须给出高度机械化的方法。

任给2个桶，A, B，总共存在6种不同的操作：
1. 将A打满水；
2，将B打满水；
3，将A的水倒光；
4，将B的水倒光；
5，将A的水倒入B；
6，将B的水倒入A。

记两个桶的容积分别为a, b， 不妨设 a < b < 2a
观察下面的操作序列：
A, B, 操作
0, 0, 开始
a, 0， A打满水
0， a, A的水倒入B
a, a, A打满水
2a-b, b, A的水倒入B
2a-b, 0, B的水倒光
0, 2a-b，A的水倒入B
a, 2a-b, A打满水
3a-2b, b，A的水倒入B
...

可以发现，无论何种顺序，在任何时间，任何桶中的水都可以表达为ax + by的形式。也就是说是a，b的线性组合。有了这个结论，我们可以立即给出问题是否有解的判定条件：
用两个容积为a, b的桶打出g升水有解的充分必要条件是 (a, b)整除g。
也就是说a, b的最大公约数整除g, (你能证明它么？）
例如，我们无法用4升和6升的桶，获得5升水。特别地，当a, b互素时，总有解。

虽然我们获得了有没有解的判定条件，但是我们还没有获得解的一般方法。如果我们找到了某两个整数x, y使得ax + by = g，我们一定能构造这样一个倒水操作序列：
（不失一般性，设x > 0, y < 0，我们试图将A倒满x次，将B倒光y次）
重复x次：
  1，倒满A;
  2, 将A的水倒入B，当B满的时候，将B倒光。

一下是用3升和5升的桶，获得4升水的方案：
0, 0
3, 0,
0, 3
3, 3
1, 5
1, 0
0, 1
3, 1
0, 4

剩下的问题就是如何找到x, y。数论中的扩展欧几里德算法给了我们这个武器。相对于欧几里德算法，扩展欧几里德算法不仅可以找到(a, b)，还可以找到x, y使得ax + by = d = (a, b)。

以下我们推到一下ext-gcd算法：

定义：(d, x, y) = ext-gcd(a, b)
不失一般性，设a < b，我们有 b = aq + r，其中q是商，r是余数。由于d是最大公约数，故而d整除a,和b，因而，d必然整除r，由于r < a，所以我们可以求ext-gcd(r, a)来减小问题规模：
(d, x', y') = ext-gcd(r, a)
根据定义有d = x'r + y'a, 由于b = aq + r故而r = b - aq，将其带入：
d = x' (b - aq) + y' a = (y' - x'q) a + x' b
明显这是a, b的线性组合，故而我们有：
x = y' - x' b / a
y = x'

这是一个典型的递归关系，其边界条件发生在a = 0时，此时：
(0, b) = b = 0 a + 1 b 于是我们可以给出ext-gcd的实现了：

extGcd 0 b = (b, 0, 1)
extGcd a b = let (d, x’, y’) = extGcd (b ‘mod‘ a) a in
                    (d, y’ - x’ ∗ (b ‘div‘ a), x’)

至此，使用数论方法解倒水问题的答案如下：

solve a b g | g ‘mod‘ d /= 0 = [] -- no solution
                 | otherwise = solve’ (x ∗ g ‘div‘ d)
where
  (d, x, y) = extGcd a b
  solve’ x | x < 0 = solve’ (x + b)
              | otherwise = pour x [(0, 0)]
  pour 0 ps = reverse ((0, g):ps)
  pour x ps@((a’, b’):_) | a’ = 0 = pour (x - 1) ((a, b’):ps) -- fill a
                                  | b’ = b = pour x ((a’, 0):ps) -- empty b
                                  | otherwise = pour x ((max 0 (a’ + b’ - b),min (a’ + b’) b):ps)

这一方法的最大优越性是在速度上远远快于基于暴力搜索的BFS解法。但是并不保证操作次数是最少的。如果要想获得最少的操作次数，需要使得|x| + |y|最小，这个并不难实现。

对应的BFS解法的C代码如下：
#include <stdio.h>
#include <stdlib.h>

int min(int a, int b) { return a <= b ? a : b; }

int max(int a, int b) { return b < a ? a : b; }

struct Step {
    int p, q;
    struct Step* parent;
};

struct Step* make_step(int p, int q, struct Step* parent) {
    struct Step* s = (struct Step*) malloc(sizeof(struct Step));
    s->p = p;
    s->q = q;
    s->parent = parent;
    return s;
}

struct Step *steps[1000], **head, **tail = steps;

void push(struct Step* s) { *tail++ = s; }

struct Step* pop() { return *head++; }

int empty() { return head == tail; }

void reset() {
    struct Step **p;
    for (p = steps; p != tail; ++p)
        free(*p);
    head = tail = steps;
}

int eq(struct Step* a, struct Step* b) {
    return a->p == b->p && a->q == b->q;
}

int visited(struct Step* s) {
    struct Step **p;
    for (p = steps; p != tail; ++p)
        if (eq(*p, s)) return 1;
    return 0;
}

void expand(struct Step* s, int a, int b, struct Step** cs) {
    int p = s->p, q = s->q;
    cs[0] = make_step(a, q, s); /*fill A*/
    cs[1] = make_step(p, b, s); /*fill B*/
    cs[2] = make_step(0, q, s); /*empty A*/
    cs[3] = make_step(p, 0, s); /*empty B*/
    cs[4] = make_step(max(0, p + q - b), min(p + q, b), s); /*pour A into B*/
    cs[5] = make_step(min(p + q, a), max(0, p + q - a), s); /*pour B into A*/
}

struct Step* solve(int a, int b, int g) {
    int i;
    struct Step *cur, *cs[6];
    reset();
    push(make_step(0, 0, NULL));
    while (!empty()) {
        cur = pop();
        if (cur->p == g || cur->q == g)
            return cur;
        else {
            expand(cur, a, b, cs);
            for (i = 0; i < 6; ++i)
                if(!eq(cur, cs[i]) && !visited(cs[i]))
                    push(cs[i]);
        }
    }
    return NULL;
}

/**print the steps in reverse order, returns how many steps there are. */
int print(struct Step* s) {
    int n = -1;
    if (s) {
        n = 1 + print(s->parent);
        printf("%d, %d\n", s->p, s->q);
    }
    return n;
}

void test(int a, int b, int g) {
    printf("solve a=%d, b=%d, g=%d:\n", a, b, g);
    printf("total %d steps\n", print(solve(a, b, g)));
    reset();
}

int main(int argc, char *argv[]) {
    test(3, 5, 4);
    test(4, 9, 6);
    return 0;
}


Xinyu LIU

unread,
Feb 11, 2014, 12:15:56 AM2/11/14
to pon...@googlegroups.com
时间关系，有些细节我没有给出。我这里以问题的形式列在这里，这些问题的答案在我的代码中。
- 扩展欧几里德算法给出的x, y是ax + by = (a, b)的解，而(a, b) 不一定等于g，如何获得ax + by = g的解？
- 我们构造操作序列时，假设x > 0, y < 0, 从而构造出了倒满A桶x次，倒光B桶y次的序列，如果扩展欧几里德法给出的x < 0, y > 0怎么办呢？
- 求解ax + by = g，本质上是求解二元一次不定方程，根据高斯在《算术研究》中的结论，我们可以将其转化为求解同余方程。求出的x, y实际上可以表达为 特解+模的倍数 的形式，我们可否利用这一形式找出最优解？



Ray Song

unread,
Feb 11, 2014, 10:16:59 PM2/11/14
to pon...@googlegroups.com
抱歉 top posting

用 a 和 b 倒出 c

最佳倒水方案只有兩種形式：
- 只包含 注滿a、a倒入b、清空b 三種操作  (甲)
- 只包含 注滿b、b倒入a、清空a 三種操作  (乙)


若 c = a 或 c = b 時答案爲 1
不然：

  找到 a*x+b*y = c 的滿足 |x|+|y| 最小的解 (x,y)，這樣的最小解有一個或兩個
  對於每個解 (x,y) 判斷是否滿足 x>0 ? c<a : c<b，若是，則最少步數爲 2(|x|+|y|-1)，
  並且：
    - x>0 and c<a 時：(甲)是其中一個最佳倒水方案
    - x<0 and c<b 時：(乙)是其中一個最佳倒水方案
  
  若最小解(1~2個)都不滿足 x>0 ? c<a : c<b，則最少步數爲 2(|x|+|y|)
  同樣：
    - x>0時：(甲)是其中一個最佳倒水方案
    - x<0時：(乙)是其中一個最佳倒水方案


Reply all
Reply to author
Forward
0 new messages