水壶问题通解

有两个容量分别为a升和b升的水壶以及无限多的水。请判断能否通过使用这个两个水壶，从而可以得到恰好z升的水？你允许进行以下三种操作：

1. 装满任意一个水壶。
2. 清空任意一个水壶。
3. 从一个水壶向另一个水壶倒水，直到装满或者倒空。

如果要求最短操作，我们可以使用广度优先搜索，这样可以得到最短的步骤数及对应的步骤。具体的代码如下。

#include<iostream>
#include<string>
#include<stack>
using namespace std;

typedef struct node Node;
struct node {
    int x;//第一个瓶子的水
    int y;//第二个瓶子的水
    int pre;//上一个状态
    int op;//从上一个状态到这个状态执行的操作
};

//执行的操作
string opName[6] = {"FILL(1)","FILL(2)",
        "DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

//记录状态是否被使用
int visited[101][101];

//记录两个瓶子的总容量
int t1,t2;
//目标状态
int des;

//记录结果
Node result[1000];

int head = 0;
int tail = 0;

void add(int x,int y,int pre,int op) {
    Node node;
    node.x = x;
    node.y = y;
    node.pre = pre;
    node.op = op;
    result[tail] = node;
    tail++;
}

void op(int x,int y,int* a,int* b,int opType) {
    switch(opType) {
        case 1:
            *a = t1;
            *b = y;
            break;
        case 2:
            *b = t2;
            *a = x;
            break;
        case 3:
            *a = 0;
            *b = y;
            break;
        case 4:
            *a = x;
            *b = 0;
            break;
        case 5:
            if(x - t2 + y>=0) {
                *b = t2;
                *a = x - t2 + y;
            } else {
                *b = x + y;
                *a = 0;
            }
            break;
        case 6:
            if(y - t1 + x>=0) {
                *a = t1;
                *b = y - t1 + x;
            } else {
                *a = x + y;
                *b = 0;
            }
            break;
        default:
            break;
    }
}

int main() {
    int x;
    int y;
    stack<int> Stack;
    cin>>t1>>t2>>des;
    for(int i=0; i<101; i++) {
        for(int j=0; j<101; j++) {
            visited[i][j] = 0;
        }
    }
    add(0,0,-1,-1);
    visited[0][0] = 1;
    while(head != tail) {
        Node node = result[head];
        if(node.x == des||node.y == des) {
            break;
        }
        for(int i=1; i<=6; i++) {
            op(node.x,node.y,&x,&y,i);
            if(visited[x][y] != 1) {
                visited[x][y] = 1;
                add(x,y,head,i);
            }
        }
        head++;
    }
    if(head == tail){
        cout<<"impossible"<<endl;
        return 0;
    }
    for(int i = head; i>0; i = result[i].pre) {
        Stack.push(result[i].op);
    }
    cout<<Stack.size()<<endl;
    while(!Stack.empty()) {
        int op = Stack.top();
        cout<<opName[op-1]<<endl;
        Stack.pop();
    }
    return 0;
}

但我没有想过这个问题有通解，所以我在《计算机科学中的数学》中看到通解的时候，还是比较惊讶，因为我发现我根本就没有想过这个问题。下面给出关键的步骤。

1. 通过状态的转移，论证了在每一个时刻，每一个壶中的水的总量总是a和b的线性组合。
2. a和b的最大公约数是a和b的线性组合，即存在整数s和t使得。
3. 一个整数是a和b的线性组合，当且仅当它是的倍数。
4. 每一个水壶的水的总量始终是的倍数。

如果说要得到x升水，当且仅当x是a和b的最大公约数的倍数时，才能得到x升的水。因为x可以用表示，我们可以枚举s和t的值，直到得到x的值。注意到，我们可以通过调整s和t使得t为负数。所以，我们可以得到以下的通解。

1. 装满较小的水壶。
2. 将小壶中的所有水倒入大壶。每当大水=壶被装满时，将其倒空，并继续将小壶中的水倒入大壶中。
3. 记录大壶中的水量，直到等于x。

对于如何求最大公约数（greatest common divisor，后面写作gcd(a,b)），可以利用欧几里得算法，欧几里得算法利用这样一个性质，。算法的终止条件为，此时，x即为所求的最大公约数。具体代码如下。

/* a >= b */
int gcd(int a,int b){
    if(b == 0){
        return a;
    }
    return gcd(b,a%b);
}