双桶量水

实践练习C++17

只有两个不同容量的水桶,没有刻度。你可以装满、倒空或在两桶之间倒水,通过组合这些操作得到目标水量。

任务说明

给定两个不同容量的水桶,以及必须先装满哪一个桶,通过在两桶间倒水量出指定升数,计算所需操作次数。

解法必须遵循:

  • 一次只能做一个操作。
  • 只有三种操作:把一桶倒入另一桶,直到源桶空或目标桶满;清空一桶而不改变另一桶;装满一桶而不改变另一桶。
  • 任何操作结束后,都不能出现“指定起始桶为空,而另一桶为满”的状态。

输入包括:

  • 第一桶容量。
  • 第二桶容量。
  • 目标升数。
  • 必须先装满的桶,第一桶或第二桶。

程序应确定:

  • 达到目标所需总操作数,包括第一次装满起始桶。
  • 最终哪一桶装有目标升数。
  • 另一桶剩余多少升。

注意,每次改变一个或两个桶的合法动作,都计为 1 次操作。

例如,两桶容量分别为 7、11 升,当前为 (7,8)。清空第一桶得到 (0,8),计一次;若改为将第一桶倒入第二桶直到满,得到 (4,11),也只计一次。

另一例:容量为 3、5 升,要求从第一桶开始。第一步装满第一桶,第二步清空它。第三步不能直接装满第二桶,因为这样会出现起始桶空、另一桶满的禁止状态。

本练习由 Lindsay Levine 在 Fullstack Academy 用心编写。