目錄

1. 問題描述

2. 解題分析

2.1?節(jié)點(diǎn)狀態(tài)表示

???????2.2?鄰節(jié)點(diǎn)搜索

???????2.3?路徑歷史記憶以及判斷鄰節(jié)點(diǎn)是否在路徑歷史中

3. 代碼及測試

運(yùn)行結(jié)果：

4. 后記

1. 問題描述

????????有A，B，C這三個(gè)大小各不相同的玻璃杯。從A杯裝滿水、B和C空杯的狀態(tài)開始，不斷地從一個(gè)杯子倒到其它杯子里去。假設(shè)不能使用任何輔助測量工具，且倒水時(shí)只能倒到這個(gè)杯子變?yōu)榭眨蛘吣繕?biāo)杯子變?yōu)闈M。重復(fù)這樣的倒水操作，使A杯剩余水量是最初的一般。舉個(gè)例子，如果A、B、C的初始容量分別為8、5、3，則可以通過以下操作序列使得A的水量變?yōu)?：(A to B), (B to C), (C to A), (B to C), (A to B), (B to C), (C to A)。讀者可以自行手動演算驗(yàn)證。

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

2. 解題分析

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

??????? 圖搜索問題的過程的關(guān)鍵就是構(gòu)建搜索樹，這一類問題的通用解題思路的要點(diǎn)：

1. 節(jié)點(diǎn)狀態(tài)表示
2. 鄰節(jié)點(diǎn)（或子節(jié)點(diǎn)）搜索
3. 路徑歷史記憶以及判斷鄰節(jié)點(diǎn)是否在路徑歷史中? ?

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

???????2.1?節(jié)點(diǎn)狀態(tài)表示

????????本題節(jié)點(diǎn)狀態(tài)很簡單，就是當(dāng)前三個(gè)杯子中的水量，用列表[a,b,c]表示即可。

???????2.2?鄰節(jié)點(diǎn)搜索

????????鄰節(jié)點(diǎn)搜索就是指搜索從當(dāng)前狀態(tài)/節(jié)點(diǎn)能夠去往的下一個(gè)節(jié)點(diǎn)/狀態(tài)，這些鄰節(jié)點(diǎn)在搜索樹中就對應(yīng)著當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。所以這里鄰節(jié)點(diǎn)和子節(jié)點(diǎn)是可以互換使用的等價(jià)概念。

????????但是鄰節(jié)點(diǎn)要避免回到當(dāng)前路徑上已經(jīng)到達(dá)過的節(jié)點(diǎn)，因?yàn)槟菢拥脑捑托纬闪谁h(huán)路（loop），破壞了樹的結(jié)構(gòu)。如何防止形成環(huán)路參見下一節(jié)。

???????2.3?路徑歷史記憶以及判斷鄰節(jié)點(diǎn)是否在路徑歷史中

????????與單純的深度優(yōu)先搜索（for reachability judge only）不同的是，本類問題需要搜索所有可能的路徑（呃。。。后來發(fā)現(xiàn)我誤解了題目，主動提高了解題要求，不過油多不壞菜，就按‘誤解’后的擴(kuò)展版本來解吧，反正擴(kuò)展版本包含了原題的答案），不同路徑有可能共享一部分的節(jié)點(diǎn)或者甚至一部分edge。所以在搜索過程中需要記住當(dāng)前搜索路徑的歷史，而不是一個(gè)全局的visited，因?yàn)橹挥糜诜乐贡韭窂叫纬森h(huán)路。每條路徑的搜索需要維護(hù)自己的路徑歷史。

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

????????在每次遞歸調(diào)用時(shí)，將當(dāng)前節(jié)點(diǎn)/狀態(tài)加入pathHistory，然后在退出本次遞歸調(diào)用時(shí)又將進(jìn)入本次遞歸調(diào)用時(shí)加入的當(dāng)前節(jié)點(diǎn)/狀態(tài)清除掉。這相當(dāng)于伴隨著遞歸調(diào)用的隱式棧，并行地維護(hù)了一個(gè)顯式的路徑歷史堆棧。我還沒有想清楚這個(gè)是不是不可避免的，或許有什么辦法可以回避掉。。。有時(shí)間再琢磨琢磨。

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))

運(yùn)行結(jié)果：

? ? ? ? ......

????????[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. 后記

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

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

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

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

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

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