字节跳动面试题-水壶问题

问题

给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

思路

先想想用人脑如何解决这个问题，模拟将水从一个水壶倒进另一个水壶，使得各个水壶水的体积不断变化，一步步尝试和推导，比如先正向推导，从已知状态推导后续状态，再反向推导，从结果状态往前推导，2种状态某一刻相同了，说明求出了答案，此方式较考验大脑的记忆能力和逻辑思维能力。

程序的方式和人脑相似，不过更为简单粗暴，俗称广度优先遍历剪枝算法，从初始状态开始，衍生出后续状态，每个后续状态只能是前一个状态下，从其中一个水壶倒向另一个水壶的一步操作，比如从(8,0,0)开始，只能倒水一次，则后续状态只能是(3,5,0)和(5,0,3)，再从这2个状态继续向后衍生。所谓剪枝，是指后续状态不能再和前面任何一个状态重复。一直往后衍生，直到没有后续，或者找到了一种状态，表示正好有个水壶的水是4升。采用广度优先遍历，可保证我们的结果一定是最优解，也就是使用倒水的步骤一定是最少的。

从一个状态衍生后续状态的代码，倒水过程：

#从所有排列组合中，任取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算法：

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

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("无解!")