1. 問題描述：

有兩個容量分別為?x升和 y升的水壺以及無限多的水。請判斷能否通過使用這兩個水壺，從而可以得到恰好z升的水？
如果可以，最后請用以上水壺中的一或兩個來盛放取得的z升水。
你允許：

• 裝滿任意一個水壺
• 清空任意一個水壺
• 從一個水壺向另外一個水壺倒水，直到裝滿或者倒空

示例 1:?

輸入: x = 3, y = 5, z = 4
輸出: True

示例 2:

輸入: x = 2, y = 6, z = 5
輸出: False

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/water-and-jug-problem

2. 思路分析：

① 分析題目可以知道最容易想到的是遞歸（也可以使用寬搜，思路都是一樣的），在遞歸的時候枚舉所有可能操作下的狀態，由題可知，對應的操作下總共有八個平行的狀態，分別是：① 將A倒滿 ② 將B倒滿 ③ 將A清空 ④ 將B清空 ⑤ 將A倒B并且A有剩余 ⑥ 將A倒B并且A倒空 ⑦ 將B倒A且B有剩余 ⑧ 將B倒A且B倒空，在遞歸的時候嘗試這八種平行狀態即可，為了避免在遞歸的時候遞歸之前已經求解過的狀態我們需要標記一下已經被訪問過的狀態，因為使用的是python語言所以可以使用python中的字典標記，使用元組表示兩個容器的狀態，鍵表示元組對應的狀態，值為int類型表示當前的狀態已經標記。只有當前操作下新的狀態在之前沒有遞歸過的時候我們才往下遞歸，并且我們可以寫一個有返回值的遞歸這樣當我們往下遞歸求解的過程發現可以通過x與y得到z那么就可以直接返回True，也即找到一個滿足條件的狀態就返回True，這樣就可以避免重復性的遞歸。

② 除了①中遞歸求解所有可能方案的思路之外，還有一種比較好的是使用數學的思路求解。分析題目可以知道兩個水壺不可能同時是既不空也不滿的狀態，所以水壺的水與外界交換的總共有四種情況，分別是+ a, -a, +b，-b（a, b為水壺的體積），只有這四種狀態才對應著最優解，所以問題就轉化為判斷方程ax + by = c是否有解，判斷方程是否有解我們可以使用裴蜀定理：方程有解的充要條件是a, b的最大公約數是c的倍數，也即判斷c是否能夠整除a, b的最大公約數即可。并且方程有解的時候我們需要判斷是否存在一種合法的操作序列使得方程有解。我們知道0 <= c <= a + b的，當c = 0時肯定滿足條件所以c > 0 且c <= a + b所以只需要判斷0 < c <= a + b的情況即可，c > 0說明a, b對應的操作次數中至少有一個是大于0的，假設x?> 0，當y > 0時說明將a, b倒滿即可，當x > 0且y <= 0時說明不斷將a倒滿，將b倒掉，使得最終的次數滿足ax + by = c成立。所以當方程有解的時候我們是可以構造成一種合法的操作序列的，所以只要是方程有解我們就可以知道一種合法的操作序列，也即直接判斷方程是否有解即可。

3. 代碼如下：

遞歸：

import collectionsclass Solution:# 使用dfs搜索def dfs(self, dic: collections.defaultdict(int), x1, y1, x, y, z):# 通過x與y最終可以得到z直接返回Trueif x1 == z or y1 == z or x1 + y1 == z: return True# 嘗試可能的狀態# 將A倒滿 if (x, y1) not in dic:dic[(x, y1)] = 1# 我們只要是找到一個滿足條件的就直接返回if self.dfs(dic, x, y1, x, y, z): return True# 將B倒滿if (x1, y) not in dic:dic[(x1, y)] = 1if self.dfs(dic, x1, y, x, y, z): return True# 將A清空if (0, y1) not in dic:dic[(0, y1)] = 1if self.dfs(dic, 0, y1, x, y, z):return True# 將B清空if (x1, 0) not in dic:dic[(x1, 0)] = 1if self.dfs(dic, x1, 0, x, y, z): return True# 將A倒B并且A有剩余if x1 >= y - y1 and (x1 - y + y1, y) not in dic:dic[(x1 - y + y1, y)] = 1self.dfs(dic, x1 - y + y1, y, x, y, z)# 將A倒B并且A倒空if x1 < y - y1 and (0, x1 + y1) not in dic:dic[(0, y1 + x1)] = 1self.dfs(dic, 0, x1 + y1, x, y, z)# 將B倒A且B有剩余if y1 >= x - x1 and (x, y1 - x + x1) not in dic:dic[(x, y1 - x + x1)] = 1if self.dfs(dic, x, y1 - x + x1, x, y, z): return True# 將B倒A且B倒空if y1 < x - x1 and (x1 + y1, 0) not in dic:dic[(y1 + x1, 0)] = 1if self.dfs(dic, x1 + y1, 0, x, y, z): return Truereturn Falsedef canMeasureWater(self, x: int, y: int, z: int) -> bool:# 使用字典來標記狀態是否被訪問過dic = collections.defaultdict(int)return self.dfs(dic, 0, 0, x, y, z)

可以使用一個字符串變量來記錄中間滿足條件的結果：

import collectionsclass Solution:def dfs(self, dic: collections.defaultdict(int), x1, y1, x, y, z):# 通過x與y最終可以得到z, 注意兩個瓶子的水加起來等于z也是滿足條件的if x1 == z or y1 == z or x1 + y1 == z: return Trueif (x, y1) not in dic:dic[(x, y1)] = 1if self.dfs(dic, x, y1, x, y, z): return Trueif (x1, y) not in dic:dic[(x1, y)] = 1if self.dfs(dic, x1, y, x, y, z): return Trueif (0, y1) not in dic:dic[(0, y1)] = 1if self.dfs(dic, 0, y1, x, y, z):return Trueif (x1, 0) not in dic:dic[(x1, 0)] = 1if self.dfs(dic, x1, 0, x, y, z): return Trueif x1 >= y - y1 and (x1 - y + y1, y) not in dic:dic[(x1 - y + y1, y)] = 1self.dfs(dic, x1 - y + y1, y, x, y, z)if x1 < y - y1 and (0, x1 + y1) not in dic:dic[(0, y1 + x1)] = 1self.dfs(dic, 0, x1 + y1, x, y, z)if y1 >= x - x1 and (x, y1 - x + x1) not in dic:dic[(x, y1 - x + x1)] = 1if self.dfs(dic, x, y1 - x + x1, x, y, z): return Trueif y1 < x - x1 and (x1 + y1, 0) not in dic:dic[(y1 + x1, 0)] = 1if self.dfs(dic, x1 + y1, 0, x, y, z): return Truereturn Falsedef canMeasureWater(self, x: int, y: int, z: int) -> bool:dic = collections.defaultdict(int)return self.dfs(dic, 0, 0, x, y, z)

數學：

class Solution:# 求解最大公約數模板def gcd(self, a: int, b: int):return a if b == 0 else self.gcd(b, a % b)def canMeasureWater(self, a: int, b: int, c: int) -> bool:if c > a + b: return Falsereturn c >= 0 and c % self.gcd(a, b) == 0

?

總結

以上是生活随笔為你收集整理的365 水壶问题（递归、数学-裴蜀定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。