知恵袋の油分け算の問題をPythonで解いてみました。(^_^;
７Lと９Lの空の容器と水の入った大きな水槽がある。これらの容器を使って水をくんだり移し替えたリする操作を繰り返し、９Lの容器に８Lの水を入れるためには、最低何回の操作が必要であるか。
ただし、1回の操作とは、次のア〜ウのうちいずれか一つだけであるものとする。
ア どちらか一方の容器で、大きな水槽から水をくむ。
イ どちらか一方の容器から、他方の容器に水を移し替える。
ウ どちらか一方の容器から、大きな水槽に水を移し替える。
「８Lずつに分ける」じゃなくて、「９Lの容器に８Lの水を入れる」というのがポイントですね。(^_^;
プログラムは、以前、Javaで作ったプログラムを参考にしました。
ちなみに、「do..whileの代替」構文で、条件を前の方に持ってきたのは、
「if t==[]: continue」を使えるようにするためです。(^_^;
● MeasuringWithJugs1.py
# coding: UTF-8 # MeasuringWithJugs1.py # 油分け算 from time import time class Point: def __init__(self, x, y,dx,dy,mx,my): self. x,self. y = x, y # 中小容器中の量 self.dx,self.dy = dx, dy # 増分 self.mx,self.my = mx, my # 中小容器に入る最大量 self.z = (mx+my)-(x+y) # 大容器中の量 def nextTurn(self): t = self.mx+self.my u,v = self.x+self.dx,self.y+self.dy if u> self.mx or (v< 0 and u!=0): self.dx,self.dy = -1, 1 elif v> self.my: self.dx,self.dy = 0,-1 elif u< 0: self.dx,self.dy = 1, 0 self.x+=self.dx; self.y+=self.dy self.z = t-self.x-self.y return self.isInArea() def isInArea(self): return 0<=self.x<=self.mx and 0<=self.y<=self.my def isGoal(self,a,b): return self.x==a and self.y==b def liState(self): if (self.x==0 and self.y == 0)or\ (self.x==0 and self.dx==-1)or(self.x==self.mx and self.dx==1)or\ (self.y==0 and self.dy==-1)or(self.y==self.my and self.dy==1): return [self.z,self.x,self.y] return [] def toStr(lst): return '[%s]'%','.join(['%2s'%x for x in lst]) def main(): tm = time() # Timer Start M,N = 9,7 GX,GY = 8,0 p = Point(0,0,1,0,M,N) cnt,ans = 0,[] while True: if cnt==0: pass # 初回スキップ elif not p.nextTurn(): break # do..whileの代替 t = p.liState() ## print(t) if t==[]: continue ans.append(t) if p.isGoal(GX,GY): g = cnt cnt+=1 print('[ A, B, C]') # 表を作成 print('----------') for n in range(g+1): print('%s %2d'%(toStr(ans[n]),n)) print('----------') for n in reversed(range(g,len(ans))): print('%s %2d'%(toStr(ans[n]),len(ans)-1-n)) t = [a[1] for a in ans] # 2列目を取り出す r = list(reversed(t)) # 逆順 print(u'∴ %2d 回'%min(t.index(GX),r.index(GX))) # 小さい方をとる print("Runtime : %.3f [sec]"%(time()-tm)) # Timer Stop & Disp if __name__ == '__main__': main()
●実行結果
[ A, B, C] ---------- [16, 0, 0] 0 [ 7, 9, 0] 1 [ 7, 2, 7] 2 [14, 2, 0] 3 [14, 0, 2] 4 [ 5, 9, 2] 5 [ 5, 4, 7] 6 [12, 4, 0] 7 [12, 0, 4] 8 [ 3, 9, 4] 9 [ 3, 6, 7] 10 [10, 6, 0] 11 [10, 0, 6] 12 [ 1, 9, 6] 13 [ 1, 8, 7] 14 [ 8, 8, 0] 15 ---------- [16, 0, 0] 0 [ 9, 0, 7] 1 [ 9, 7, 0] 2 [ 2, 7, 7] 3 [ 2, 9, 5] 4 [11, 0, 5] 5 [11, 5, 0] 6 [ 4, 5, 7] 7 [ 4, 9, 3] 8 [13, 0, 3] 9 [13, 3, 0] 10 [ 6, 3, 7] 11 [ 6, 9, 1] 12 [15, 0, 1] 13 [15, 1, 0] 14 [ 8, 1, 7] 15 [ 8, 8, 0] 16 ∴ 14 回 Runtime : 0.015 [sec]
●参考図
Ｃ
＋－＋－②－＋－⑥－＋－⑩－＋－⑭－＋
｜ ｜ ｜＼｜ ｜＼｜ ｜＼｜ ｜＼｜
⑫－＋－＋－＋－＋－＋－＋－＋－＋－⑬
｜＼｜ ｜ ｜＼｜ ｜＼｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜ ｜ ｜＼｜ ｜＼｜ ｜＼｜
⑧－＋－＋－＋－＋－＋－＋－＋－＋－⑨
｜＼｜ ｜＼｜ ｜ ｜＼｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜ ｜＼｜ ｜ ｜＼｜ ｜＼｜
④－＋－＋－＋－＋－＋－＋－＋－＋－⑤
｜＼｜ ｜＼｜ ｜＼｜ ｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜ ｜＼｜ ｜＼｜ ｜ ｜＼｜
◎－＋－③－＋－⑦－＋－⑪－＋－⑮－①Ｂ
Ｃ
①－⑮－＋－⑪－＋－⑦－＋－③－＋－＋
｜＼｜＼｜ ｜＼｜ ｜＼｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜＼｜ ｜＼｜ ｜＼｜ ｜＼｜
⑤－＋－＋－＋－＋－＋－＋－＋－＋－④
｜＼｜ ｜＼｜＼｜ ｜＼｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜ ｜＼｜＼｜ ｜＼｜ ｜＼｜
⑨－＋－＋－＋－＋－＋－＋－＋－＋－⑧
｜＼｜ ｜＼｜ ｜＼｜＼｜ ｜＼｜ ｜
＋－＋－＋－＋－＋－＋－＋－＋－＋－＋
｜ ｜＼｜ ｜＼｜ ｜＼｜＼｜ ｜＼｜
⑬－＋－＋－＋－＋－＋－＋－＋－＋－⑫
｜＼｜ ｜＼｜ ｜＼｜ ｜＼｜＼｜ ｜
◎－⑭－＋－⑩－＋－⑥－＋－②－⑯－＋Ｂ
※参考URL
●油分け算 - rscの日記
●油分け算の問題をJavaで解いてみた。
●知恵袋の油分け算の問題をPythonで解いてみた。(2)
