四則ソルバーver2.1
前回は全通りの括弧、数字、演算子 を組み合わせて計算させていたので
オーダーがすごく大きいことになりましたが、今回は若干再帰してますので若干オーダーが少ないはずです。
#coding:utf-8 from __future__ import division #整数割り算時の切り捨て解除 #演算子と文字列(出力用)のリスト funcs=[lambda x,y:x+y,lambda x,y:x-y,lambda x,y:y-x,lambda x,y:x*y,lambda x,y:x/y,lambda x,y:y/x] sikifuncs=[lambda x,y:"("+x+"+"+y+")",lambda x,y:"("+x+"-"+y+")",lambda x,y:"("+y+"-"+x+")",lambda x,y:"("+x+"*"+y+")",lambda x,y:"("+x+"/"+y+")",lambda x,y:"("+y+"/"+x+")"] def make(numlist,ans,siki): L=len(numlist) if L==1: if abs(numlist[0]-ans)<1/100000.0: return siki else:return False else: for i in range(6): for j in range(L-1): n=numlist[:] s=siki[:] try: n.insert(j,funcs[i](n.pop(j),n.pop(j))) s.insert(j,sikifuncs[i](s.pop(j),s.pop(j))) except ZeroDivisionError: continue res=make(n,ans,s) if res: return res return False #並び替え関数 def conb(numlist,x): if x==0: return [[]] else: return [[a]+b for i,a in enumerate(numlist) for b in conb(numlist[:i]+numlist[i+1:],x-1)] def solve(numlist,ans): numlists=conb(numlist,len(numlist)) for list in numlists: siki=map(str,list) res=make(list,ans,siki) if res: return res[0] return False
まぁ前回よりオーダーは小さくなったんですが、6数で解なしの時、つまり全通り処理するとき、すごい時間かかっちゃうので
ここを何とかしていきたいと思います。
実行結果
小数の出力結果は所要時間(秒)です
>>> solve([1,2,3],2.5) 0.00200009346008 '(3-(1/2))' >>> solve([1,1,5,8],10) 0.0150001049042 '(8/(1-(1/5)))' >>> solve([1,1,3,7,7],3.14) 0.861999988556 '((1/((1/7)+7))+3)' >>> solve([1,2,3,4,5,6],3.14) 104.361000061 '(((1+(2/5))/(4+6))+3)'