python解24点程序及算法

目录

算法

大致的思路是对输入的数值进行表达式的全排列,然后计算选出合法的组合
定义F(S)为对S集合进行四则运算,S为正整数集合。
24点的解可以看作是F(a,b,c,d)=24。很明显如果F(a,b,c,d)=24有解,则F(F(F(a,b),c),d)=24或F(F(a,b),F(c,d))=24有解

程序

#!/usr/bin/python
arr=[]
nums=raw_input("please input 4 integer:")
num=nums.split(' ')
for i in num:
    arr.append(float(i))

def perm(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+1:]
            for p in perm(rest, n-1):
                yield v + p

def F(a,b):
    arr={}
    for i in a:
        for j in b:
            va=a[i]
            vb=b[j]
            arr.update({"("+i+"+"+j+")":va+vb})
            arr.update({"("+i+"-"+j+")":va-vb})
            arr.update({"("+j+"-"+i+")":vb-va})
            arr.update({"("+i+"*"+j+")":va*vb})
            vb>0 and arr.update({"("+i+"/"+j+")":va/vb})
            va>0 and arr.update({"("+j+"/"+i+")":vb/va})
    return arr

for i in perm(arr):
      dic=[{"a":i[0]},{"b":i[1]},{"c":i[2]},{"d":i[3]}]
      alist=F(F(F(dic[0],dic[1]),dic[2]),dic[3])
      blist=F(F(dic[0],dic[1]),F(dic[2],dic[3]))
      for i in alist:
          if alist[i]==24.0:
             print i.replace('a',str(dic[0]['a'])).replace('b',str(dic[1]['b'])).replace('c',str(dic[2]['c'])).replace('d',str(dic[3]['d']))
      for i in blist:
          if blist[i]==24.0:
             print i.replace('a',str(dic[0]['a'])).replace('b',str(dic[1]['b'])).replace('c',str(dic[2]['c'])).replace('d',str(dic[3]['d']))

执行效果