字节跳动面试题-水壶问题
问题
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
思路
先想想用人脑如何解决这个问题，模拟将水从一个水壶倒进另一个水壶，使得各个水壶水的体积不断变化，一步步尝试和推导，比如先正向推导，从已知状态推导后续状态，再反向推导，从结果状态往前推导，2种状态某一刻相同了，说明求出了答案，此方式较考验大脑的记忆能力和逻辑思维能力。
程序的方式和人脑相似，不过更为简单粗暴，俗称广度优先遍历剪枝算法，从初始状态开始，衍生出后续状态，每个后续状态只能是前一个状态下，从其中一个水壶倒向另一个水壶的一步操作，比如从(8,0,0)开始，只能倒水一次，则后续状态只能是(3,5,0)和(5,0,3)，再从这2个状态继续向后衍生。所谓剪枝，是指后续状态不能再和前面任何一个状态重复。一直往后衍生，直到没有后续，或者找到了一种状态，表示正好有个水壶的水是4升。采用广度优先遍历，可保证我们的结果一定是最优解，也就是使用倒水的步骤一定是最少的。
从一个状态衍生后续状态的代码，倒水过程：
12345678910111213 | #从所有排列组合中，任取2个容器，从其中一个倒向另一个，只能倒一次并且倒完之后不能和之前的状态重复def water(self,state): for p in self.per: i,j=p[0],p[1] leave=self.kettles[j]-state[j] if state[i]>0 and leave>0: lst=list(state) have=lst[i] lst[i]=max(0,have-leave) lst[j]=lst[j]+min(have,leave) r=tuple(lst) if not r in self.marked: yield r |
|---|
广度优先遍历BFS算法：
123456789101112131415 | def kettleProblem(self,kettles,initState,result): self.kettles=kettles self.per=[i for i in itertools.permutations(range(len(self.kettles)), 2)] self.marked=set() queue=[[initState]] self.marked.add(initState) while queue: q=queue.pop(0) for i in self.water(q[0]): #把路径也记录下来，可清晰的看出步骤 queue.append([i]+q) self.marked.add(i) if result in i: return [i]+q return None |
|---|
既然有了算法，不妨把这个变成此类问题的通用解。只需要得知3个参数: 1.所有容器的容量大小，此题为(8,5,3) 2.初始状态，此题为(8,0,0) 3.要得到的体积，此题为4
12345678910 | if __name__=='__main__': #演示：把1-7所有的容量都求一遍 for i in range(1,8): r=s.kettleProblem((8,5,3),(8,0,0),i) print("求{0}升水".format(i)) if r: r.reverse() print("结果:{0}".format(r)) else: print("无解!") |
|---|
结果
总结
数学VS计算机
数学 | 计算机 | |
|---|---|---|
解法 | 不定方程 | 暴力枚举 |
思想 | 人类智慧结晶 | 大量重复运算 |
个人觉得数学是人类文明几千年发展来的智慧结晶，而计算机只是人类历史上发明的一个重要工具。正是因为有了理论基础，才使工具的诞生有了可能，比如布尔代数的诞生，就大大简化了计算机逻辑电路的布线。 有了计算机这个工具，我们就可以在并不是那么“聪明”的情况下，也能解决具体问题。
腾讯云开发者
