Cracking Coding Interview - 6.5 Jugs of Water

Jugs of Water: You have a 5-quart jug, a 3-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly 4 quarts of water? Note that the jugs are oddly shaped,such that filling up exactly “half” of the jug would be impossible.

Hints :#149, #379, #400

翻译：five-quart jug，五夸脱的水罐。

解法

一个5单位的罐子，一个3单位的罐子，无限的水，让你弄出4单位的水。

J3(x)代表3升桶里有x升水，J5(x)代表5升桶里有x升水

1. 把3升桶罐满：J3(3)，J5(0)
2. 倒进5升桶里：J3(0)，J5(3)
3. 把3升桶罐满：J3(3)，J5(3)
4. 倒进5升桶里，3升桶里剩余1升：J3(1)，J5(5)
5. 把5升桶倒掉：J3(1)，J5(0)
6. 把3升桶里的水倒进5升桶里：J3(0)，J5(1)
7. 把3升桶罐满：J3(3)，J5(1)
8. 倒进5升桶里：J3(0)，J5(4)

另一个办法：

1. 把5升桶罐满：J5(5)，J3(0)
2. 倒进3升桶里：J5(2)，J3(3)
3. 倒掉3升桶：J5(2)，J3(0)
4. 5升桶倒进3升桶里：J5(0)，J3(2)
5. 把5升桶罐满：J5(5)，J3(2)
6. 5升桶倒进3升桶里：J5(4)，J3(3)
7. 3升桶倒掉：J5(4)，J3(0)