完善程序2解析

有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允许下列的三种操作,分别为:

  1. FILL(i):用水龙头将容器 i(i∈1,2)i(i∈1,2) 灌满水;
  2. DROP(i):将容器 i 的水倒进下水道;
  3. POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要么容器 i 被清空)。

求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数,且 c≤max{a,b}。

这道题其实是一道数学题,虽然据说微软的面试考过这道题。 数论中,有一个裴蜀定理( Bézout’s identity),说明了对任何整数a、b和它们的最大公约数d,一定存在整数x,y,使ax+by=d成立。
因此,只要满足z是GCD(a, b)的倍数,即可捣鼓出z升水。GCD(a, b)代表x,y的最大公约数。

两桶分水的规律就是:
大桶没水了,就把大桶接满水
大桶有水,就往小桶倒水
小桶满了,就把小桶倒了,重新让大桶向小桶倒水

例如:一个3 公升的提捅,一个5 公升的提捅,如何才能准确称出4 公升的水?

也可以用穷举法。穷举法实现比较方便,其基本思想是用:用小桶容量的倍数对大桶的容量进行取余。比如3升的桶和5升的桶得到4升水可以这样做:

3 % 5 = 3

6 % 5 = 1

9 % 5 = 4

成功得到4升水。(PS:上面的过程用如何用文字描述了?)

同样,用7升的桶和11升的桶得到2升水可以这样做:

7 % 11 = 7

14 % 11 = 3

21 % 11 = 10

28 % 11 = 6

35 % 11 = 2

成功得到2升水。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**************************************************************** 
 * Description: 2022_S_finish_2
 * Author: Alex Li
 * Date: 2023-08-30 11:24:50
 * LastEditTime: 2023-08-31 09:30:51
****************************************************************/
#include <iostream>
using namespace std;
const int N = 110;

int f[N][N];//f[i][j]是在容器1有i升水,容器2有j升水,的情况下,达到目标c的次数。
int ans;
int a, b, c;
int init;

int dfs(int x, int y) {
    if (f[x][y] != init)//记忆化搜索,f[x][y]之前访问过,直接返回结果
        return f[x][y];
    if (x == c || y == c) //容器1或容器2是c,还需0次。
        return f[x][y] = 0;
    f[x][y] = init - 1;//初始值是极大值-1,之后滚动比较求最小值 
    f[x][y] = min(f[x][y], dfs(a, y) + 1);  //FILL[1]操作
    f[x][y] = min(f[x][y], dfs(x, b) + 1);  //FILL[2]操作
    f[x][y] = min(f[x][y], dfs(0, y) + 1);  //DROP[1]操作
    f[x][y] = min(f[x][y], dfs(x, 0) + 1);  //DROP[2]振作
    int t = min(a - x, y);
    f[x][y] = min(f[x][y], dfs(x + t, y - t) + 1); //POUR(2,1)从容器2向容器1倒水
    t = min(x, b - y);
    f[x][y] = min(f[x][y], dfs(x - t, y + t) + 1);//POUR(1,2)从容器1向容器2倒水
    return f[x][y];
}

//根据f[x][y]输出步骤
void go(int x, int y) {
    if (x == c || y == c)
        return;
    if (f[x][y] == dfs(a, y) + 1) {
        cout << "FILL(1)" << endl;
        go(a, y);
    } else if (f[x][y] == dfs(x, b) + 1) {
        cout << "FILL(2)" << endl;
        go(x, b);
    } else if (f[x][y] == dfs(0, y) + 1) {
        cout << "DROP(1)" << endl;
        go (0, y);
    } else if (f[x][y] == dfs(x, 0) + 1) {
        cout << "DROP(2)" << endl;
        go(x, 0);
    } else {
        int t = min(a - x, y);
        if(f[x][y] == dfs(x + t, y - t) + 1) {
            cout << "POUR(2,1)" << endl;
            go(x + t, y - t);
        } else {
            t = min(x, b - y);
            if (f[x][y] ==dfs(x - t, y + t) + 1) {
                cout << "POUR(1,2)" << endl;
                go(x - t, y + t);
            } else
                assert(0);
        }
    }
}

int main() {
    cin >> a >> b >> c;
    ans = 1 << 30;
   memset(f, 127, sizeof f); //初始化,极大值, 0x7f7f7f7f
    init = **f;//  init=f[0][0]  二维数组和指印
    if ((ans = dfs (0, 0)) == init - 1)//若ans是init-1没有被更新
        cout << "impossible";
    else {
        cout << ans << endl;
    //输出步骤
       go (0, 0);
    }
}
Scroll to Top