python实现二十四点

给定n个数字,计算出一个满足24点的表达式:比如1,11,2,1:(11&＃43;1)*2/1

基本思路就是枚举计算顺序(在一开始进行一次全排列),括号,加减乘除。其实有很多是重复计算过了的。这个程序我为了高效找到一个解就算了,但是我们把程序稍微修改就可以找到所有的解(表达顺序可能会重复,比如1&＃43;2和2&＃43;1),同时也可以计算多个数字的组合。

def compute(x,y,op):if op&＃61;&＃61;&＃39;&＃43;&＃39;:return x&＃43;yelif op&＃61;&＃61;&＃39;*&＃39;:return x*yelif op&＃61;&＃61;&＃39;-&＃39;:return x-yelse:return x/y if y else Nonedef exp(p,iter&＃61;0):from itertools import permutationsif len(p)&＃61;&＃61;1:return [(p[0],str(p[0]))]operation &＃61; [&＃39;&＃43;&＃39;,&＃39;-&＃39;,&＃39;*&＃39;,&＃39;/&＃39;]ret &＃61; []p &＃61; permutations(p) if iter&＃61;&＃61;0 else [p]for array_n in p:#print(array_n)for num in range(1,len(array_n)):ret1 &＃61; exp(array_n[:num],iter&＃43;1)ret2 &＃61; exp(array_n[num:],iter&＃43;1)for op in operation:for va1,expression in ret1:if va1&＃61;&＃61;None:continuefor va2,expression2 in ret2:if va2&＃61;&＃61;None:continuecombined_exp &＃61; &＃39;{}{}&＃39; if expression.isalnum() else &＃39;({}){}&＃39;combined_exp &＃43;&＃61; &＃39;{}&＃39; if expression2.isalnum() else &＃39;({})&＃39;new_val &＃61; compute(va1,va2,op)ret.append((new_val,combined_exp.format(expression,op,expression2)))if iter&＃61;&＃61;0 and new_val&＃61;&＃61;24:return &＃39;&＃39;.join(e&＃43;&＃39;\n&＃39; for x,e in ret if x&＃61;&＃61;24)return ret
print(exp([2,3,4,11,1,3]))

做的一点优化:记忆式搜索

EXP &＃61; {}
def exp(array_n,target,iter&＃61;0):if len(array_n)&＃61;&＃61;1:return [(array_n[0],str(array_n[0]))]operation &＃61; [&＃39;&＃43;&＃39;,&＃39;-&＃39;,&＃39;*&＃39;,&＃39;/&＃39;]ret &＃61; []for num in range(1,len(array_n)):exp1 &＃61; array_n[:num]exp2 &＃61; array_n[num:]ret1 &＃61; EXP[exp1] if exp1 in EXP else exp(exp1,target,iter&＃43;1)ret2 &＃61; EXP[exp2] if exp2 in EXP else exp(exp2,target,iter&＃43;1)EXP[exp1] &＃61; ret1EXP[exp2] &＃61; ret2for op in operation:for va1,expression in ret1:if va1&＃61;&＃61;None:continuefor va2,expression2 in ret2:if va2&＃61;&＃61;None:continuecombined_exp &＃61; &＃39;{}{}&＃39; if expression.isalnum() else &＃39;({}){}&＃39;combined_exp &＃43;&＃61; &＃39;{}&＃39; if expression2.isalnum() else &＃39;({})&＃39;new_val &＃61; compute(va1,va2,op)ret.append((new_val,combined_exp.format(expression,op,expression2)))if iter&＃61;&＃61;0 and new_val&＃61;&＃61;target:#print(&＃39;ans&＃39;)return &＃39;&＃39;.join(e for x,e in ret if x&＃61;&＃61;target)return ret if iter else None
def search(array):record &＃61; set()from itertools import permutationsfor p in permutations(array):if p in record:continuerecord.add(p)ret &＃61; exp(tuple(p),100)if ret:print(ret);break