兩個水桶

說明

給你兩個大小不同的水桶，並指定要先裝滿哪一個水桶，請判斷在兩個水桶之間策略性地倒水，需要多少個動作才能量出剛好幾公升。

你的解法必須遵守以下規則：

• 你一次只能做一個動作。
• 只有 3 種可能的動作：
  1. 把一個水桶倒進另一個水桶，直到： a) 第一個水桶空了 b) 第二個水桶滿了
  2. 倒空一個水桶，另一個水桶維持不變。
  3. 裝滿一個水桶，另一個水桶維持不變。
• 每次動作之後，都不能出現一開始裝水的那個水桶是空的、而另一個水桶是滿的狀態。

你的程式會接收以下輸入：

• 第一個水桶的容量
• 第二個水桶的容量
• 想要量出的公升數
• 要先裝滿哪一個水桶，第一個或第二個水桶

你的程式應該判斷出：

• 達到目標公升數總共需要幾個動作，包含第一次裝滿起始水桶的動作
• 最後哪個水桶應該裝有目標公升數，第一個或第二個水桶
• 另一個水桶裡還剩多少公升

注意：只要其中一個水桶或兩個水桶的狀態有改變，就算一個（1）動作。

範例： 第一個水桶最多可以裝 7 公升，第二個水桶最多可以裝 11 公升。 假設在某個步驟，第一個水桶裝了 7 公升，第二個水桶裝了 8 公升（7,8）。 如果你倒空第一個水桶，第二個水桶維持不變，兩個水桶分別剩下 0 公升和 8 公升（0,8），這算一個動作。 反過來說，如果你把第一個水桶倒進第二個水桶，直到第二個水桶滿了，結果第一個水桶剩下 4 公升、第二個水桶有 11 公升（4,11），這也同樣只算一個動作。

另一個範例： 第一個水桶可以裝 3 公升，第二個水桶最多可以裝 5 公升。 題目要求你必須從第一個水桶開始。 所以你的第一個動作是裝滿第一個水桶。 你選擇在第二個動作倒空第一個水桶。 到了第三個動作，你不能裝滿第二個水桶，因為這違反了第三條規則：任何動作之後，都不能出現起始水桶是空的、而另一個水桶是滿的狀態。

由 Lindsay Levine 在 Fullstack Academy 用 <3 寫成。

---

出處

倒水問題