三個水桶等分8升水的問題 -《演算法的樂趣》
智力題目
有三個容積分別為3升、5升、8升的水桶，其中容積為8升的水桶中裝滿了水，容積為3升和容積為5升的水桶都是空的。三個水桶都沒有刻度，現在需要將大水桶中的8升水等分成兩份，每份都是4升水，附加條件是隻能這三個水桶，不能借助其他輔助容器。
“恩，是的，這是一個很經典的問題。”
“然而，我們並不能想全，不信請繼續往下看。”
答案
”廢話不多說，直接看方法吧。“
第一種（7步）
- 將8L的水桶中的水，倒滿5L的水桶，這時：8L水桶為3L、5L水桶為5L、3L水桶為0L
- 將5L的水桶中的水，倒滿3L的水桶，這時：8L水桶為3L、5L水桶為2L、3L水桶為3L
- 將3L的水桶中的水，倒入8L的水桶，這時：8L水桶為6L、5L水桶為2L、3L水桶為0L
- 將5L的水桶中的水，倒入3L的水桶，這時：8L水桶為6L、5L水桶為0L、3L水桶為2L
- 將8L的水桶中的水，倒入5L的水桶，這時：8L水桶為1L、5L水桶為5L、3L水桶為2L
- 將5L的水桶中的水，倒滿3L的水桶，這時：8L水桶為1L、5L水桶為4L、3L水桶為3L
- 將3L的水桶中的水，倒入8L的水桶，這時：8L水桶為4L、5L水桶為4L、3L水桶為0L
第二種（8步）
- 將8L的水桶中的水，倒滿3L的水桶，這時：8L水桶為5L、5L水桶為0L、3L水桶為3L
- 將3L的水桶中的水，倒入5L的水桶，這時：8L水桶為5L、5L水桶為3L、3L水桶為0L
- 將8L的水桶中的水，倒滿3L的水桶，這時：8L水桶為2L、5L水桶為3L、3L水桶為3L
- 將3L的水桶中的水，倒滿5L的水桶，這時：8L水桶為2L、5L水桶為5L、3L水桶為1L
- 將5L的水桶中的水，倒入8L的水桶，這時：8L水桶為7L、5L水桶為0L、3L水桶為1L
- 將3L的水桶中的水，倒入5L的水桶，這時：8L水桶為7L、5L水桶為1L、3L水桶為0L
- 將8L的水桶中的水，倒滿3L的水桶，這時：8L水桶為4L、5L水桶為1L、3L水桶為3L
- 將3L的水桶中的水，倒入5L的水桶，這時：8L水桶為4L、5L水桶為4L、3L水桶為0L
我相信答案肯定不止兩個，到底有多少種答案？
帶著這個疑問，我們來設計一個演算法吧。
問題分析
人的思維
解決這個問題的關鍵是怎麼通過倒水湊出確定的1升水或能容納1升水的空間。
例如，當8L水桶或5L水桶或3L水桶有1L水時，都能快速倒出4L水。
計算機思維
“窮舉法”
水桶初始狀態：8L水桶裝滿水，3L和5L的水桶為空。
水桶最終狀態：3L水桶為空，5L和8L的水桶各4L水。
假設將每個狀態下三個水桶中的水的體積作為status。
從 $status = array(8,0,0) 得到 $status = array(4,4,0)。
當然還會有一些限制：
1.各個水桶的都有最大值：
0 <= status[0] <= 8;
0 <= status[1] <= 5;
0 <= status[2] <= 3;
2.當前倒水之後各個水桶的狀態，與歷史倒水之後各個水桶的狀態，不能相同。
3.當前水桶為空時，不能倒給其他水桶。
4.當前水桶為最大容積時，其他水桶不能再向這個水桶倒水。
程式程式碼（PHP）
執行結果
一共有 16 種倒水方法，方法如下：
...
（16種方法，貼上去太長了，大家在本地嘗試下，如需要原始碼，請關注公眾號「XinLiangTalk」進行留言。）
小結
執行程式碼之後，一共找到了 16 種倒水的方法，最快的方法需要 7 個步驟。
“怎麼樣，是不是沒想到會有這麼多方法吧，去考考你身邊的小夥伴吧。”
本文歡迎轉發，轉發請註明作者和出處，謝謝！