你還記得未名湖畔的輾轉相除法嗎？

08-31

你還記得未名湖畔的輾轉相除法嗎？

來自專欄礦工

365. Water and Jug Problem

You are given two jugs(容器) with capacities x and y litres(公升). There is an infinite(無限) amount of water supply available. You need to determine whether it is possible to measure(測量) exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.（最終，你必須用這兩個容器來測量出z公升）。

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4

Output: True

Example 2:

Input: x = 2, y = 6, z = 5

Output: False

解題思路：

我們先來了解一個裴蜀定理(Bézouts identity)(wiki: https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity),

如果x或者y是負數，這就意味著我們分別倒了一個容器x次a公升或者y次b公升，同樣地，如果x或者y是正數，這就意味著我們分別填滿了一個容器x次a公升或者y次b公升。

比如：

a = 4, b = 6， z = 8. 那麼GCD(a,b) = 2。 GCD 就是greatest common divisor的縮小，以為最大公約數。8 是 2 的倍數，所以呢，裴蜀定理可以寫成-1*4 + 6*2 = 8。這就意味者倒掉4公升容器一次，裝滿6公升容器2次。第一次裝入6公升容器一次，從6公升水中倒掉4公升水到4公升容器，完成上一步之後，把4公升容器倒掉，再把6公升中剩下的2公升水倒入到4公升容器中，再次把6公升水裝滿就行了。這樣一共裝了8公升水。

參考代碼：

什麼是輾轉相除法呢？

輾轉相除法，又名歐幾里德演算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。

另一種求兩數的最大公約數的方法是更相減損法。

既然提到了更相減損法，那我們再了解一下什麼是更相減損法吧。更相減損法是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。又名「更相減損術」，輾轉相減法，等值演算法，尼考曼徹斯法。它廣泛應用在數學和計算機上。

不過由於演算法效率沒有輾轉相除法效率高，一般採用輾轉相除法來求解。

最後提交的一個結果。個人微信號algboy。

參考：Water and Jug Problem - LeetCode