資訊專(zhuān)欄INFORMATION COLUMN
摘要：但是由于不能使用作為，所以將表示狀態(tài)的列表轉(zhuǎn)換為后再用作的。上一篇將牌洗為逆序下一篇糖果惡作劇本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解
目錄
???????2.3?路徑歷史記憶以及判斷鄰節(jié)點(diǎn)是否在路徑歷史中
????????有A，B，C這三個(gè)大小各不相同的玻璃杯。從A杯裝滿(mǎn)水、B和C空杯的狀態(tài)開(kāi)始，不斷地從一個(gè)杯子倒到其它杯子里去。假設(shè)不能使用任何輔助測(cè)量工具，且倒水時(shí)只能倒到這個(gè)杯子變?yōu)榭眨蛘吣繕?biāo)杯子變?yōu)闈M(mǎn)。重復(fù)這樣的倒水操作，使A杯剩余水量是最初的一般。舉個(gè)例子，如果A、B、C的初始容量分別為8、5、3，則可以通過(guò)以下操作序列使得A的水量變?yōu)?：(A to B), (B to C), (C to A), (B to C), (A to B), (B to C), (C to A)。讀者可以自行手動(dòng)演算驗(yàn)證。
????????在B和C的容量互質(zhì)，且滿(mǎn)足B+C=A，B>C的條件下，當(dāng)A為10~100之間的偶數(shù)時(shí)，請(qǐng)問(wèn)能使得“倒水操作后A杯水量減半”的A、B、C容量的組合有多少個(gè)？
????????圖搜索問(wèn)題，深度優(yōu)先遞歸搜索（隨口杜撰的名詞大雜燴。。。做了一些題后一些概念開(kāi)始在腦子里亂燉到一塊兒了，后面要適時(shí)地總結(jié)整理夯實(shí)一下地基鞏固一下訓(xùn)練成果）！本系列中有相當(dāng)多題目都是這一個(gè)類(lèi)型，用同樣的套路就可以解決，后面有時(shí)間要回頭來(lái)做一次總結(jié)。相比之下，原書(shū)還提供了另外一種更為精妙的解法，但是那個(gè)是只適用于當(dāng)前題目的特定技巧，沒(méi)有通用性。
??????? 圖搜索問(wèn)題的過(guò)程的關(guān)鍵就是構(gòu)建搜索樹(shù)，這一類(lèi)問(wèn)題的通用解題思路的要點(diǎn)：
????????通用很重要！靈光一現(xiàn)的解題技巧（可遇而不可求）就留給天才們?nèi)プ龊昧恕Ｕ莆樟艘粋€(gè)通用技巧，你可以確保碰到一個(gè)同類(lèi)型的問(wèn)題你有一個(gè)重型坦克般的保底的解決方案，雖然有時(shí)候不免顯得笨拙，但是沒(méi)有什么能攔得住！
????????本題節(jié)點(diǎn)狀態(tài)很簡(jiǎn)單，就是當(dāng)前三個(gè)杯子中的水量，用列表[a,b,c]表示即可。
????????鄰節(jié)點(diǎn)搜索就是指搜索從當(dāng)前狀態(tài)/節(jié)點(diǎn)能夠去往的下一個(gè)節(jié)點(diǎn)/狀態(tài)，這些鄰節(jié)點(diǎn)在搜索樹(shù)中就對(duì)應(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á)過(guò)的節(jié)點(diǎn)，因?yàn)槟菢拥脑捑托纬闪谁h(huán)路（loop），破壞了樹(shù)的結(jié)構(gòu)。如何防止形成環(huán)路參見(jiàn)下一節(jié)。
????????與單純的深度優(yōu)先搜索（for reachability judge only）不同的是，本類(lèi)問(wèn)題需要搜索所有可能的路徑（呃。。。后來(lái)發(fā)現(xiàn)我誤解了題目，主動(dòng)提高了解題要求，不過(guò)油多不壞菜，就按‘誤解’后的擴(kuò)展版本來(lái)解吧，反正擴(kuò)展版本包含了原題的答案），不同路徑有可能共享一部分的節(jié)點(diǎn)或者甚至一部分edge。所以在搜索過(guò)程中需要記住當(dāng)前搜索路徑的歷史，而不是一個(gè)全局的visited，因?yàn)橹挥糜诜乐贡韭窂叫纬森h(huán)路。每條路徑的搜索需要維護(hù)自己的路徑歷史。
????????在本題解中，用python dict來(lái)存儲(chǔ)路徑歷史。但是由于python dict不能使用list作為key，所以將表示狀態(tài)的列表[a,b,c]轉(zhuǎn)換為tuple后再用作dict的key。那為什么不直接用tuple表示節(jié)點(diǎn)/狀態(tài)呢？這是因?yàn)閠uple的值不能修改，對(duì)于在處理過(guò)程需要更新?tīng)顟B(tài)值時(shí)不太方便。當(dāng)然這些都不過(guò)是細(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è)顯式的路徑歷史堆棧。我還沒(méi)有想清楚這個(gè)是不是不可避免的，或許有什么辦法可以回避掉。。。有時(shí)間再琢磨琢磨。
# -*- 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
????????如前所述，原題其實(shí)只要求求出有多少{A，B，C}組合能夠使得“倒水操作后A杯水量減半”稱(chēng)為可能，因此對(duì)于每一種組合只要找出一條可行的路徑即可。但是以上題解針對(duì)每一種{A，B，C}組合找出了所有可能的操作步驟（的種類(lèi)數(shù)）。當(dāng)然只要對(duì)以上程序稍作修改就可以變成針對(duì)每個(gè){A，B，C}組合找到一種可行路徑就退出。
? ? ? ? 另外，如果需要找出針對(duì)每種{A，B，C}組合所需要的最少步數(shù)，問(wèn)題就轉(zhuǎn)變成了圖搜索之最短路徑問(wèn)題，這就需要用廣度優(yōu)先搜索（BFS）來(lái)解決了。后面有時(shí)間再回頭來(lái)追加對(duì)應(yīng)的題解，目前暫時(shí)留給各位小伙伴們做思考題。
? ? ? ? 另外，原書(shū)題解中提示了對(duì)于每種{A，B，C}組合所需要的最少操作次數(shù)為(A-1)。而另一方面，以上題解運(yùn)行結(jié)果表明，對(duì)于每種{A，B，C}組合，可能的操作步驟數(shù)為(2*A-1)。這兩者之間存在什么關(guān)聯(lián)嗎？留給各位小伙伴們一起思考。
?? ? ? 上一篇：Q42: 將牌洗為逆序
? ? ? ? 下一篇：Q52: 糖果惡作劇
????????本系列總目錄參見(jiàn)：程序員的算法趣題：詳細(xì)分析和Python全解
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/118818.html
摘要：假設(shè)有幾個(gè)小朋友以相同間隔圍成圓周，要結(jié)對(duì)用紙杯電話相互通話。如果繩子交叉，很有可能會(huì)纏繞起來(lái)，所以結(jié)對(duì)的原則是不能讓繩子交叉。如下所示運(yùn)行結(jié)果上一篇異或楊輝三角形下一篇禁止右轉(zhuǎn)本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 1. 問(wèn)...
摘要：所幸，滿(mǎn)足平方根前十位數(shù)字正好讓的數(shù)字全部出現(xiàn)的數(shù)是存在的。上一篇斐波那契數(shù)列下一篇滿(mǎn)足字母算式的解法本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 1. 問(wèn)題描述 ????????求在計(jì)算平方根的時(shí)候，最早讓0~9的數(shù)字全部出現(xiàn)的最...
摘要：且聽(tīng)下回分解基于動(dòng)態(tài)規(guī)劃策略的優(yōu)化解法參見(jiàn)程序員的算法趣題偷懶的算盤(pán)上一篇程序員的算法趣題同數(shù)包夾程序員的算法趣題同數(shù)包夾本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 4. 后記 1. 問(wèn)題描述 ??...
摘要：可以在遍歷所有矩陣時(shí)，對(duì)各種出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，最后計(jì)數(shù)值為的個(gè)數(shù)即為所求結(jié)果。上一篇排序交換次數(shù)的最少化排序交換次數(shù)的最少化本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解 目錄 1. 問(wèn)題描述 2. 解題分析 3. 代碼及測(cè)試 4. 后記 1. 問(wèn)題描述 ...
閱讀 2857·2021-09-10 10:51
閱讀 2222·2021-09-02 15:21
閱讀 3214·2019-08-30 15:44
閱讀 882·2019-08-29 18:34
閱讀 1662·2019-08-29 13:15
閱讀 3330·2019-08-26 11:37
閱讀 2706·2019-08-26 10:46
閱讀 1117·2019-08-26 10:26
