问题描述
有两个容量分别为x升和y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得z升 水。
你允许：
装满任意一个水壶；
清空任意一个水壶；
从一个水壶向另外一个水壶倒水，直到装满或者倒空。
解决方案
这道题转化为数学方法就是nx+my=z的问题，有一个数学定理叫贝祖定理：
如果x，y的最大公约数为k那么一定存在两个整数a，b满足ax+by=k。
如果z%k=0就一定存在一个整数G，满足G(ax+by)=Gk=z，即得到Gax+Gby=z。
满足条件，所以这道题就简化成求xy的最大公约数。
一、数学方法解决
import math def canMeasureWater(x,y,z): #首先处理几种极端情况 if x+y<z: return False elif z==x or z==y: return True elif x==0 or y==0: return False #判断z是否能整除最大公约数 return z%math.gcd(x,y)==0 #math.gcd()这个函数就是直接求出参数的最大公约数 #也可以用辗转相除法自己求最大公约数 def mygcd(x,y): while y: x,y=y,x%y return x |
二、用BFS模板来求解
1.建立BFS模板
(1)建立queue，visited set；
(2)while queue 不空：
(3)处理当前节点；
(4)扩展节点，更新visited，入queue。
2.BFS在python的模板
def BFS(graph,start,end): queue=[]#建立queue queue.append([start]) Visited=set()#建立visited visited.add(start) while queue:#循环queue node=queue.pop()#处理节点 visited.add(node)#更新visited process(node) nodes=generate_related_nodes(node)#扩展节点 queue.push(nodes)#入queue |
3.本题带入
主要是模拟倒水的情况用BFS暴力枚举。
import collections class Solution: def canMeasureWater(self, x: int, y: int, z: int) -> bool: # 首先处理几种极端情况 if z<0 or x+y<z:return False # BFS queue=collections.deque([(0,0)])#建立queue，collections.deque是双端队列，支持从两端添加和删除元素 visited={(0,0)} #建立visited while len(queue): # current node processing处理当前节点 a,b=queue.popleft() if a==z or b==z or a+b==z: return True #generate other nodes扩展更多节点 states=self._gen_states(a,b,x,y) # check visited push node 更新visited 提交节点 for state in states: if state not in visited: visited.add(state) queue.append(state) return False def _gen_states(self,a,b,x,y): states=[] #清空 states.append((0,b)) states.append((a,0)) #填满水 states.append((x, b)) states.append((a, y)) #a倒入b，a+b if a+b<y: states.append((0,a+b)) else : states.append((a+b-y,y)) #b倒入a，a+b if a+b<x: states.append((a+b,0)) else: states.append((x,a+b-x)) return states # sol=Solution() # print(sol.canMeasureWater(3,5,4)) |
结语
对比两种方法的代码量明显可以看出这道题的优质算法是用数学方法解决，之所以用BFS来解决，主要是为了熟练运用BFS模板来嵌套解决，方便以后遇到数学方法不是很容易想出来，必须要用到这种搜索算法来暴力枚举（模拟），当熟练掌握了这个模板并加以运用就可以很快的写出BFS算法相关的题了。
