用Python形象地解決酒缸分酒問題
- 2019 年 10 月 10 日
- 筆記
本文1715字；預計閱讀12分鐘；
最近遇到一個有意思的題目，看上去不相關的兩個事物有著同樣的轉移狀態，並且設定規則後過程可以用程式模擬出來，遂記之。
0,問題提出
你有一個8升的酒罈，裡面裝滿了酒，另外還有兩個分別是5升和3升的空酒罈，3個酒罈都沒有刻度，現在需要倒出正好4升的酒，需要怎麼操作？
從題目來看，我們需要把3個缸的酒倒來倒去，直到某個酒缸裡面是4升酒。這個問題的解法很有趣，我們假設能裝5升酒的罈子叫A，3升的罈子是B，8升的罈子是C，開始的時候我們可以先在A罈子里裝滿酒也可以先在B罈子裝滿酒（只裝一部分我們是沒辦法知道是多少升的，沒有用）。
假設先給A裝滿酒，那麼A,B罈子的狀態就是(5,0)，表示這時候是A有5升酒，B有0升，這時候可以的做法是把A中的酒倒到B里，變成(2,3)，也可以從C倒3升到B，變成(5,3)，但這種情況下一步只能把A或B中的酒倒回C，回到開始狀態了；第三種情況是把A中的酒倒進C里，變成(0,0)，更加沒意義了。
1,撞球解法
於是有效做法是從(5,0)狀態變成(2,3)狀態，我們可以想像一個菱形的撞球桌，從一個地方發球，球經過和桌子邊緣的碰撞有一個彈射的路徑。來看一下一個從(5,0)出發的球，在一個5 x 3的撞球桌上，沿三角形邊線方向撞擊撞球，其路徑會是(2,3) (2,0) (0,2) (5,2) (4,3)，如圖
撞球彈射路徑
我們之前把(5,0)理解為A壇有5升酒，B壇有0升，那麼從(5,0)到(2,3)到(2,0)就可以理解為這兩個酒罈裡面液體的量的變化，也就是酒罈里的狀態轉移路徑。具體就是從A倒酒進B里，直到B滿了（變成(2,3)），再把B里的酒倒到C里，變成(2,0)，把B中剩餘的2升倒到C里，變成(0,2),這時候把B倒滿，變成(5,2)，B可以裝3升，目前是2升，所以從A倒酒進B里，B原來是2升，倒滿就是從A倒出了1升，所以A是4升，也就是(4,3)，達到要求。
實際中解這類題我們可以畫x*y的菱形手動畫路徑，但我們可以用程式模擬這一過程，下面用Python實現一下。
3,Python 模擬
可以通過計算方向和用反射定律去模擬球的軌跡，也可以取巧只通過路徑去模擬軌跡。首先這個撞球桌是菱形的，出發點在(5,0)或(0,3) （都能得到結果），我們從路徑上看，(5,0)只有一個路徑可以走，而(2,3)有兩條路可以走，分別到達(2,0)或者(5,0)，在(0,0)以及(5,3)這兩個點是沒有路徑的。
3種路徑的示意圖
我們再分析路徑的規律，x橫坐標的最大值，y是縱坐標最大值，設n球在橫坐標的位置，m為在縱坐標上的位置，對於點設n球在橫坐標的位置，m為在縱坐標上的位置，對於點(n,0)，n不等於0和不等於x時，都有兩條路，且從一條路過來必然下一步要走另一條路，這兩條路的規律是(n,y)以及(0,n)，當n大於y時，到不了(0,n)， 只能到(n-y,y)；根據這些規律模擬出邊界上各個頂點對應的路，程式碼如下：
t=8 e=4 x,y=5,3 if y>x: x,y=y,x #保證x>y #從路徑來看，一個點要麼沒有路徑，要麼有1條路徑，要麼2條，沒有其他情況； #0條對應：(0,0) & (x,y) #1條：(x,0) & (0,y) #2條：(n,m) 0<n<x 0<m<y r={} r[(0,0)]=[] r[(x,y)]=[] r[(x,0)]=[(x-y,y)] r[(0,y)]=[(y,0)] for n in range(1,x): if n<y: r[(n,0)]=[(0,n),(n,y)] else: r[(n,0)]=[(n-y,y),(n,y)] k=n+y if k>x: r[(n,y)]=[(n,0),(x,n+y-x)] else: r[(n,y)]=[(n,0),(n+y,0)] for m in range(1,y): #m必然要小於x if m<x: 不需要 r[(0,m)]=[(m,0),(x,m)] r[(x,m)]=[(0,m),(x+m-y,y)]
我們就可以從一個點(5,0)出發，看具體的效果：
w=[x,0] #上一個點 s=[x,0] plst=[s] #開始 while s[0]!=e and s[1]!=e: ss=(s[0],s[1]) sw=r[ss] slen=len(sw) if slen==1: w=s.copy() s[0]=sw[0][0] s[1]=sw[0][1] elif slen==2: if sw[0][0]==w[0] and sw[0][1]==w[1]: w=s.copy() s[0]=sw[1][0] s[1]=sw[1][1] elif sw[1][0]==w[0] and sw[1][1]==w[1]: w=s.copy() s[0]=sw[0][0] s[1]=sw[0][1] else: print(s,sw,slen) else: print(s,sw,slen) plst.append(s) print(plst)
當x=5，y=3時，以上程式碼輸出 [[5,0],[2,3],[2,0],[0,2],[5,2],[4,3]]，代表A，B兩個酒缸之內各有多少酒。
4,turtle可視化
路徑我們可以通過上面的程式碼算出來，從而得到這題的結果，但不夠形象，我們通過Python的turtle庫把這一過程畫出來，turtle是Python內置的一個畫圖庫，通過goto、left、right等命令控制一個小海龜（turtle）在畫布（canvas）上爬行，從而得到各種圖案，可以拿來繪製分形圖案、小豬佩奇等。這次的模擬路徑可視化也可以用pygame庫。
正常的畫布是一個直角坐標系，我們這裡需要一個縱軸和橫軸之間是60度的斜坐標系，因此通過以下函數轉換：
def drawToXY(x,y,turtle=turtle,sin=sin,pc=50): #sin=sin(60°)=sqrt(3)/2; pc轉換因子 turtle.goto(x*pc+0.5*y*pc,pc*sin*y) #直角坐標轉斜坐標
通過 drawToXY()我們可以很方便地繪製出撞球桌的外框：
def drawDiamond(x,y,turtle=turtle,pc=pc,sin=sin): #畫邊界 turtle.pensize(3) #佔3個像素的筆寬 drawToXY(x,0,turtle,sin) drawToXY(x,y,turtle,sin) drawToXY(0,y,turtle,sin) drawToXY(0,0,turtle,sin) #外框 turtle.pensize(1) #默認筆寬
繪製一個5 x 3的外框效果如下：
繪製外框之後再加上內部點的連接，就像把一個(X,Y)的方格變形為菱形，並加上邊界坐標，在turtle上寫文本通過語句 turtle.write(txt,font=("微軟雅黑",size,"normal"))實現。
繪製外框
之後便可以繪製從(5,0)出發的球的路徑了：
def drawPlst(plst,turtle=turtle,t2=t2): dt=25 dy=200 k=0 for p in plst: drawText(-180,dy-k*dt,str(p),t2,size=14) #在另一側寫下經過的邊界點 drawToXY(p[0],p[1],t1) k+=1 def drawText(x,y,txt,turtle=turtle,size=14): turtle.penup() turtle.goto(x,y) turtle.pendown() turtle.write(txt, font=("微軟雅黑", size, "normal")) plst=plst=[(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)] t1.color("red") #t1.speed(2) #繪製速度，[0,10] 數值越大速度越快 drawPlst(plst,t1,t2)
從(0,3)出發的效果：
拓展題目
我們在河邊分別有一個7升的水桶和5升的水桶，都沒有刻度，如何用最少的次數裝6升的水出來？
分析一下我們知道，最少次數的方式就是我們撞球路徑的做法，之前我們對酒缸C的處理和一條容量無限的河本質是一樣的。
所以這題的解法用程式模擬效果就是這樣:
還可以通過枚舉解決：給一個7升和一個5升的桶，可以得到[1,7+5]之間哪些容量的水。
相關程式碼同步於https://github.com/QLWeilcf/ LcfsPythonWork/blob/ master/ waterTankSimulator.py。戳閱讀原文可達。
