一道 Google 的面試題
大家好，我是一行
想進谷歌不會連這道題也不會吧
面試題目是這樣的：
假設(shè)第1個杯子的容量是A升，第2個杯子的容量B升，兩個杯子一開始都為空，現(xiàn)在有以下三種操作：
FILL(i)：將 i 杯子中的水倒?jié)M。
DROP(i)：將 i 杯子中的水全部倒出只?？毡?。
POUR(i,j)：將杯子 i 中的水倒到杯子 j 中，若杯子 j 滿了或者杯子 i 已經(jīng)為空了則停止。
如果你每次只能進行上面操作中的一種，如何使其中一個杯子的水容量恰好為C（C <= max(A,B)）升？
問題入手分析：
當(dāng)A=3， B=5， C=4 時，初始時兩個杯子均為空，該如何操作？
很容易得出依次需要進行的操作為：
FILL(2)，此時兩個杯子的水容量為：0，5
POUR(2,1)，此時兩個杯子的水容量為：3，2
DROP(1)，此時兩個杯子的水容量為：0，2
POUR(2,1)，此時兩個杯子的水容量為：2，0
FILL(2)，此時兩個杯子的水容量為：2，5
POUR(2,1)，此時兩個杯子的水容量為：3，4
這就得到了容量為4的水。通過這個分析，我們能夠得到哪些啟發(fā)？
因為 i 和 j 的取值都是1或者2， 所以對于某個狀態(tài)，所執(zhí)行的操作總共有六種，下面會具體分析。
對于某一個狀態(tài)，我們下面有 6 種選擇，很明顯，解決這類問題比較好的辦法是廣度優(yōu)先遍歷（BFS）。而廣度優(yōu)先遍歷，所依賴的數(shù)據(jù)結(jié)構(gòu)便是隊列。
假設(shè)目前2個杯子水的容量分別為 a 和 b，那么可以執(zhí)行的操作分別為：
1、FILL(1)
此時杯子1的水的容量變?yōu)锳，而杯子2的水的容量不發(fā)生變化。
2、FILL(2)
此時杯子2的水的容量變?yōu)锽，而杯子1的水的容量不發(fā)生變化。
3、DROP(1)
此時杯子1的水的容量變?yōu)?，而杯子2的水的容量不發(fā)生變化。
4、DROP(2)
此時杯子2的水的容量變?yōu)?，而杯子1的水的容量不發(fā)生變化。
5、POUR(1,2)
此種情況略微復(fù)雜，要分為兩種場景：
1)、若杯子1中的水可以全部倒入杯子2中，即滿足a<=B-b，那么杯子1的水的容量變?yōu)?，杯子2的水的容量變?yōu)閍+b。
2)、若杯子1中的水倒入杯子2中還會有剩余，即a>B-b，那么杯子1的水的容量變?yōu)?a-(B-b)，杯子2的水的容量變?yōu)锽。
6、POUR(2,1)
此種情況同POUR(1,2)，也要分為兩種場景：
1)、若杯子2中的水可以全部倒入杯子1中，即滿足b<=A-a，那么杯子2的水的容量變?yōu)?，杯子1的水的容量變?yōu)閍+b。
2)、若杯子2中的水倒入杯子1中還會有剩余，即b>A-a，那么杯子2的水的容量變?yōu)?b-(A-a)，杯子1的水的容量變?yōu)锳。
所以，對于某個狀態(tài)，我們需要廣度優(yōu)先遍歷上述6種操作，當(dāng)遇到某個杯子的容量為C時，停止廣度優(yōu)先遍歷，遍歷的過程可以用下圖簡單表示：
明白了上述原理，就可以考慮隊列節(jié)點的數(shù)據(jù)結(jié)構(gòu)了：
對于每個狀態(tài)，我們需要存儲的信息包括：當(dāng)前杯子1的水的容量a，當(dāng)前杯子2的水的容量b，由上個狀態(tài)到本狀態(tài)執(zhí)行的操作，以及上一個狀態(tài)的信息（需要由此獲得所有的操作流程）。Python代碼如下：
class Node:
? ?# a:當(dāng)前狀態(tài)杯子1的水的容量
? ?# b:當(dāng)前狀態(tài)杯子2的水的容量
? ?# pre 上一個狀態(tài)
? ?# action上一個狀態(tài)到本狀態(tài)執(zhí)行的操作
? ?def __init__(self, a, b, pre, action):
? ? ? ?self.a = a
? ? ? ?self.b = b
? ? ? ?self.pre = pre
? ? ? ?self.action = action對于BFS，理解了上述6種操作就很簡單了，在這里特別要注意的是避免死循環(huán)，所以在入隊列的時候只入之前沒出現(xiàn)過的狀態(tài)，用數(shù)組visted 記錄已經(jīng)存在過的狀態(tài)，存在過的狀態(tài)就不入隊列。Python代碼如下：
def BFS(A, B, C):
? ?"""
? ?通過廣度搜索來計算容量為C的水
? ?:param A: 容量為A的杯子1
? ?:param B: 容量為B的杯子2
? ?:param C: 容量為C的水
? ?:return:
? ?"""
? ?# visited 記錄是否有過相關(guān)的容器組合，如果沒有才塞入隊列，避免死循環(huán)
? ?maxC = max([A,B])
? ?visited = [[0 for i in range(maxC + 1)] for i in range(maxC + 1)]
? ?# 初始化隊列
? ?q = Queue.Queue()
? ?# 初始化隊列的第一個節(jié)點并放入隊列
? ?node = Node(0, 0, None, "0")
? ?q.put(node)
? ?while not q.empty():
? ? ? ?cur = q.get()
? ? ? ?# FILL(1)
? ? ? ?a = A
? ? ? ?b = cur.b
? ? ? ?pre = cur
? ? ? ?action = "FILL(1)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ? ? ?# FILL(2)
? ? ? ?a = cur.a
? ? ? ?b = B
? ? ? ?pre = cur
? ? ? ?action = "FILL(2)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ? ? ?# DROP(1)
? ? ? ?a = 0
? ? ? ?b = cur.b
? ? ? ?pre = cur
? ? ? ?action = "DROP(1)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ? ? ?# DROP(2)
? ? ? ?a = cur.a
? ? ? ?b = 0
? ? ? ?pre = cur
? ? ? ?action = "DROP(2)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ? ? ?# POUR(1,2)
? ? ? ?if cur.a < B - cur.b:
? ? ? ? ? ?a = 0
? ? ? ? ? ?b = cur.b + cur.a
? ? ? ? ? ?pre = cur
? ? ? ? ? ?action = "POUR(1,2)"
? ? ? ?else:
? ? ? ? ? ?a = cur.a - (B - cur.b)
? ? ? ? ? ?b = B
? ? ? ? ? ?pre = cur
? ? ? ? ? ?action = "POUR(1,2)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ? ? ?# POUR(2,1)
? ? ? ?if cur.b < A - cur.a:
? ? ? ? ? ?a = cur.b + cur.a
? ? ? ? ? ?b = 0
? ? ? ? ? ?pre = cur
? ? ? ? ? ?action = "POUR(2,1)"
? ? ? ?else:
? ? ? ? ? ?a = A
? ? ? ? ? ?b = cur.b - (A - cur.a)
? ? ? ? ? ?pre = cur
? ? ? ? ? ?action = "POUR(2,1)"
? ? ? ?if not visited[a][b]:
? ? ? ? ? ?node = Node(a, b, pre, action)
? ? ? ? ? ?q.put(node)
? ? ? ? ? ?visited[a][b] = 1
? ? ? ?if a == C or b == C:
? ? ? ? ? ?return True, node
? ?return False, None還需要一個代碼，獲取一步步操作的流程，這里，由于拿到的是最后一個節(jié)點，所以要根據(jù)pre逆向?qū)ふ蚁嚓P(guān)的action，并存儲在列表中。最后，將結(jié)果逆向輸出：
def ShowResult(node):
? ?"""
? ?根據(jù)最終節(jié)點選擇前面的節(jié)點，并打印action
? ?:param node:
? ?:return:
? ?"""
? ?L = []
? ?while node.pre is not None:
? ? ? ?L.append(node.action)
? ? ? ?node = node.pre
? ?inverseL = L[::-1]
? ?for item in inverseL:
? ? ? ?print item有了上述代碼，就可以設(shè)置不同的容量值來進行測試了：
if __name__ == '__main__':
? ?A = 3
? ?B = 5
? ?C = 4
? ?flag, node = BFS(A, B, C)
? ?if flag is True:
? ? ? ?ShowResult(node)
? ?else:
? ? ? ?print "Impossible"現(xiàn)在想想，一步步分析下來，題目就沒有當(dāng)初第一眼看到題目時那么難了吧？所以，當(dāng)遇到難題時，一定要從小問題入手，逐步化解，由淺入深。
推薦閱讀
（點擊標(biāo)題可跳轉(zhuǎn)閱讀）
轉(zhuǎn)了嗎 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?贊了嗎 在看嗎
