只有两个不同容量的水桶,没有刻度。你可以装满、倒空或在两桶之间倒水,通过组合这些操作得到目标水量。
任务说明
给定两个不同容量的水桶,以及必须先装满哪一个桶,通过在两桶间倒水量出指定升数,计算所需操作次数。
解法必须遵循:
- 一次只能做一个操作。
- 只有三种操作:把一桶倒入另一桶,直到源桶空或目标桶满;清空一桶而不改变另一桶;装满一桶而不改变另一桶。
- 任何操作结束后,都不能出现“指定起始桶为空,而另一桶为满”的状态。
输入包括:
- 第一桶容量。
- 第二桶容量。
- 目标升数。
- 必须先装满的桶,第一桶或第二桶。
程序应确定:
- 达到目标所需总操作数,包括第一次装满起始桶。
- 最终哪一桶装有目标升数。
- 另一桶剩余多少升。
注意,每次改变一个或两个桶的合法动作,都计为 1 次操作。
例如,两桶容量分别为 7、11 升,当前为 (7,8)。清空第一桶得到 (0,8),计一次;若改为将第一桶倒入第二桶直到满,得到 (4,11),也只计一次。
另一例:容量为 3、5 升,要求从第一桶开始。第一步装满第一桶,第二步清空它。第三步不能直接装满第二桶,因为这样会出现起始桶空、另一桶满的禁止状态。
本练习由 Lindsay Levine 在 Fullstack Academy 用心编写。