题意：
给定两个容量分别为x和y升的罐子。提供无限容量的水。你需要判断用这两个罐子是否可以恰好量出z升的体积。到最后量出的z升体积可以由一到两个罐子装着。
允许的操作包括：
1、将任意罐子灌满。
2、将任意罐子清空。
3、将任意罐子的水倒入另一个罐子，直到另一个罐子倒满或者自己为空为止。
方法一：我自己的解法（不能保证正确）
void increse(set<int>& s, int x, int y) {
int size = s.size();
auto items2 = s;
for(auto var = items2.begin(); var != items2.end(); var++)
{
int newx = x - *var;
int newy = y - *var;
if (newx > 0)s.insert(newx);
if (newy > 0) s.insert(newy);
}
if (size != s.size()) increse(s, x, y);
}
bool canMeasureWater(int x, int y, int z) {
if (z > x + y) return false;
if (z == x + y) return true;
if (x < y) {
int temp = x;
x = y;
y = temp;
}
set<int> items;
for (int i = x - y; i > 0 && y != 0; i -= y) {
items.insert(i);
}
increse(items, x, y);
for(auto var = items.begin(); var != items.end(); var ++)
{
if (*var + x == z || *var + y == z) return true;
}
return false;
}
方法二：利用数学知识，判断z是否为x,y的最大公约数的倍数
int gcd(int p, int q) {
return q == 0 ? p : gcd(q, p % q);
}
bool canMeasureWater2(int x, int y, int z) {
if (z > x + y) return false;
if (z == 0) return true;
return z % gcd(x, y) == 0 ? true : false;
}
总结：数学真的很重要啊，从这代码量就能看出来了啊
