目錄

1. 問題描述

2. 解題分析

2.1?節點狀態表示

???????2.2?鄰節點搜索

???????2.3?路徑歷史記憶以及判斷鄰節點是否在路徑歷史中

3. 代碼及測試

運行結果：

4. 后記

1. 問題描述

????????有A，B，C這三個大小各不相同的玻璃杯。從A杯裝滿水、B和C空杯的狀態開始，不斷地從一個杯子倒到其它杯子里去。假設不能使用任何輔助測量工具，且倒水時只能倒到這個杯子變為空，或者目標杯子變為滿。重復這樣的倒水操作，使A杯剩余水量是最初的一般。舉個例子，如果A、B、C的初始容量分別為8、5、3，則可以通過以下操作序列使得A的水量變為4：(A to B), (B to C), (C to A), (B to C), (A to B), (B to C), (C to A)。讀者可以自行手動演算驗證。

????????在B和C的容量互質，且滿足B+C=A，B>C的條件下，當A為10~100之間的偶數時，請問能使得“倒水操作后A杯水量減半”的A、B、C容量的組合有多少個？

2. 解題分析

????????圖搜索問題，深度優先遞歸搜索（隨口杜撰的名詞大雜燴。。。做了一些題后一些概念開始在腦子里亂燉到一塊兒了，后面要適時地總結整理夯實一下地基鞏固一下訓練成果）！本系列中有相當多題目都是這一個類型，用同樣的套路就可以解決，后面有時間要回頭來做一次總結。相比之下，原書還提供了另外一種更為精妙的解法，但是那個是只適用于當前題目的特定技巧，沒有通用性。

??????? 圖搜索問題的過程的關鍵就是構建搜索樹，這一類問題的通用解題思路的要點：

1. 節點狀態表示
2. 鄰節點（或子節點）搜索
3. 路徑歷史記憶以及判斷鄰節點是否在路徑歷史中? ?

????????通用很重要！靈光一現的解題技巧（可遇而不可求）就留給天才們去做好了。掌握了一個通用技巧，你可以確保碰到一個同類型的問題你有一個重型坦克般的保底的解決方案，雖然有時候不免顯得笨拙，但是沒有什么能攔得住！

???????2.1?節點狀態表示

????????本題節點狀態很簡單，就是當前三個杯子中的水量，用列表[a,b,c]表示即可。

???????2.2?鄰節點搜索

????????鄰節點搜索就是指搜索從當前狀態/節點能夠去往的下一個節點/狀態，這些鄰節點在搜索樹中就對應著當前節點的子節點。所以這里鄰節點和子節點是可以互換使用的等價概念。

????????但是鄰節點要避免回到當前路徑上已經到達過的節點，因為那樣的話就形成了環路（loop），破壞了樹的結構。如何防止形成環路參見下一節。

???????2.3?路徑歷史記憶以及判斷鄰節點是否在路徑歷史中

????????與單純的深度優先搜索（for reachability judge only）不同的是，本類問題需要搜索所有可能的路徑（呃。。。后來發現我誤解了題目，主動提高了解題要求，不過油多不壞菜，就按‘誤解’后的擴展版本來解吧，反正擴展版本包含了原題的答案），不同路徑有可能共享一部分的節點或者甚至一部分edge。所以在搜索過程中需要記住當前搜索路徑的歷史，而不是一個全局的visited，因為只用于防止本路徑形成環路。每條路徑的搜索需要維護自己的路徑歷史。

????????在本題解中，用python dict來存儲路徑歷史。但是由于python dict不能使用list作為key，所以將表示狀態的列表[a,b,c]轉換為tuple后再用作dict的key。那為什么不直接用tuple表示節點/狀態呢？這是因為tuple的值不能修改，對于在處理過程需要更新狀態值時不太方便。當然這些都不過是細枝末節。

????????在每次遞歸調用時，將當前節點/狀態加入pathHistory，然后在退出本次遞歸調用時又將進入本次遞歸調用時加入的當前節點/狀態清除掉。這相當于伴隨著遞歸調用的隱式棧，并行地維護了一個顯式的路徑歷史堆棧。我還沒有想清楚這個是不是不可避免的，或許有什么辦法可以回避掉。。。有時間再琢磨琢磨。

3. 代碼及測試

# -*- coding: utf-8 -*-"""Created on Wed Sep  1 07:34:21 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom   typing import List# from   queue import Queue# from   collections import dequeclass Solution:    def pourWaterGame(self, capacity:List) -> int:        """        :A:   The Capacity of cup A        :B:   The Capacity of cup B        :C:   The Capacity of cup C        :ret: The total number of possibale combinations        """                        # capacity    = (A,B,C)        pathHistory = {}        initState   = [capacity[0],0,0]                def pourWater(curstate, fromCup, toCup):            """            pour warter from cup X to cup Y.            Because curstate is pass-by-reference argument, to avoid it is modified,             it should be firstly copied to newstate, and then update newstate.            Because in the recursiion, the original "curstate" has its use after return             from this call.            """            newstate = curstate.copy() # instead of newstate = curstate!            x = newstate[fromCup]            y = newstate[toCup]            Y = capacity[toCup]                        if x > 0 and y < Y:                if x+y <= Y:                    x,y = 0,x+y                else:                    x,y = x+y-Y,Y                newstate[fromCup] = x                newstate[toCup]   = y            return newstate                def explore(pathHistory, curstate):            # Judge whether reach the target state            if curstate[0] == A/2:                return 1                        # Add curstate to pathHistory            pathHistory[tuple(curstate)] = ""                        nums = 0            # A --> B            newstate = pourWater(curstate, 0,1)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)            # A --> C            newstate = pourWater(curstate, 0,2)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)            # B --> C            newstate = pourWater(curstate, 1,2)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)            # B --> A            newstate = pourWater(curstate, 1,0)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)                        # C --> A            newstate = pourWater(curstate, 2,0)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)                        # C --> B            newstate = pourWater(curstate, 2,1)            if tuple(newstate) not in pathHistory:                nums += explore(pathHistory,newstate)                                    pathHistory.pop(tuple(curstate))                        return nums                return explore(pathHistory,initState)

if __name__ == "__main__":                        sln    = Solution()        numCombination = 0    for A in range(10,101,2):        for C in range(1,A//2): # Because it is assumed that B>C            B = A - C            if math.gcd(B,C) == 1:                tStart = time.time()                ans    = sln.pourWaterGame([A,B,C])                if ans > 0:                    numCombination += 1                tCost  = time.time() - tStart                print("[A,B,C]=[{0},{1},{2}], ans={3}, tCost = {4:6.3f}(sec)".format(A,B,C,ans,tCost))    print("numCombination={0}".format(numCombination))

運行結果：

? ? ? ? ......

????????[A,B,C]=[100,57,43], ans=199, tCost = ?0.104(sec)
????????[A,B,C]=[100,53,47], ans=199, tCost = ?0.097(sec)
????????[A,B,C]=[100,51,49], ans=199, tCost = ?0.086(sec)
????????numCombination=514

4. 后記

????????如前所述，原題其實只要求求出有多少{A，B，C}組合能夠使得“倒水操作后A杯水量減半”稱為可能，因此對于每一種組合只要找出一條可行的路徑即可。但是以上題解針對每一種{A，B，C}組合找出了所有可能的操作步驟（的種類數）。當然只要對以上程序稍作修改就可以變成針對每個{A，B，C}組合找到一種可行路徑就退出。

? ? ? ? 另外，如果需要找出針對每種{A，B，C}組合所需要的最少步數，問題就轉變成了圖搜索之最短路徑問題，這就需要用廣度優先搜索（BFS）來解決了。后面有時間再回頭來追加對應的題解，目前暫時留給各位小伙伴們做思考題。

? ? ? ? 另外，原書題解中提示了對于每種{A，B，C}組合所需要的最少操作次數為(A-1)。而另一方面，以上題解運行結果表明，對于每種{A，B，C}組合，可能的操作步驟數為(2*A-1)。這兩者之間存在什么關聯嗎？留給各位小伙伴們一起思考。

?? ? ? 上一篇：Q42: 將牌洗為逆序

? ? ? ? 下一篇：Q52: 糖果惡作劇

????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解