《Cracking the Coding Interview》——第6章：智力题——题目3

 1 // 6.3 Given two jugs with size x and y, and a volume v between 0 and y inclusive. Show how you‘re gonna get that value.
 2 // Note that you can only fill a jug, empty a jug or pour from one into another.
 3 // x and y will be positive and relatively prime.
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 int gcd(int x, int y)
 8 {
 9     return x == 0 ? y : gcd(y % x, x);
10 }
11 
12 int main()
13 {
14     int x, y;
15     int vx, vy;
16     int v;
17     
18     while (scanf("%d%d%d", &x, &y, &v) == 3 && (x > 0 && y > 0 && v > 0)) {
19         if (x > y) {
20             continue;
21         }
22         if (gcd(x, y) > 1) {
23             continue;
24         }
25         
26         vx = 0;
27         vy = y;
28         printf("[%d, %d]: fill y\n", vx, vy);
29         while (vy != v) {
30             if (vy < x) {
31                 vx = vy;
32                 vy = 0;
33                 printf("[%d, %d]: pour y into x\n", vx, vy);
34                 vy = y;
35                 printf("[%d, %d]: fill y\n", vx, vy);
36                 vy = vy - (x - vx);
37                 vx = x;
38                 printf("[%d, %d]: pour y into x\n", vx, vy);
39                 vx = 0;
40                 printf("[%d, %d]: empty x\n", vx, vy);
41             } else {
42                 vy -= x;
43                 vx = x;
44                 printf("[%d, %d]: pour y into x\n", vx, vy);
45                 vx = 0;
46                 printf("[%d, %d]: empty x\n", vx, vy);
47             }
48         }
49     }
50     
51     return 0;
52 }