Jugs of Water

作者 QIFAN 日期 2016-10-24
Jugs of Water

Source: Cracking the Code Interview 6.5


Description

You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but
no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly “half” of the jug would be impossible.
经典的倒水题。两个瓶子一个五升一个三升,怎么量出4升。

Solution

  1. 5升倒满,并转到3升,此时5升瓶中还有有2升
  2. 清空3升,将5升瓶中的2升倒进3升,此时3升瓶中有2升
  3. 倒满5升,用5升中的水将3升瓶的倒满,此时5升瓶中还剩4升