2022年 11月 3日

python:24点程序

关于使用eval实现的方法网上很多,这里给出一种用递归穷举的实现。

下面是使用递归算法的穷举实现:

# 穷举2个数的+、-、*、/运算及其结果
def c(t):
    a = t[0][0]
    b = t[1][0]
    aa = t[0][1]
    bb = t[1][1]
    if a == 0 and b == 0:
        return [(0, '{}+{}'.format(aa,bb))]
    if a!= 0 and b!=0:
        return [(a+b, '({}+{})'.format(aa,bb)),\
                 (a*b, '({}*{})'.format(aa,bb)),\
                 (a-b, '({}-{})'.format(aa,bb)),\
                 (a/b, '({}/{})'.format(aa,bb)),\
                 (b-a, '({}-{})'.format(bb,aa)),\
                 (b/a, '({}/{})'.format(bb,aa))]
    if b == 0:
        b = a
        a = 0
        t =bb
        bb=aa
        aa= t
    return [(a+b, '({}+{})'.format(aa,bb)),\
             (a*b, '({}*{})'.format(aa,bb)),\
             (a-b, '({}-{})'.format(aa,bb)),\
             (a/b, '({}/{})'.format(aa,bb)),\
             (b-a, '({}-{})'.format(bb,aa))]

# 使用递归穷举n个数的所有+、-、*、/运算及其结果
from itertools import combinations
def f(li):
    if len(li) == 2:
        return c(li)
    res = []
    for p in combinations(li, 2):
        lic = li.copy()
        lic.remove(p[0])
        lic.remove(p[1])
        for e in c(p):
            res = res + f(lic+[e])
    return res

# 处理浮点数的精度问题
def sim(t):
    k = round(t, 7)
    for i in range(7)[::-1]:
        #print(i, k, round(t, i))
        if k != round(t, i):
            break
    if int(k) == k:
        k = int(k)
    return(k)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

调用示例,计算1,2,3,4的所有+、-、*、/运算及其结果:

li = [1,2,3,4] 
p = list(zip(li, map(str, li)))
r = f(p)

s = set()
v = set()
for e in r:
    s.add((e[1][1:-1], sim(e[0])))
    v.add(sim(e[0]))

for value in sorted(list(v)):
    for e in s:
        if e[1] == value:
            print(e[0] + '=' + str(value))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

输出:

1-(3*(2*4))=-23
1-(2*(3*4))=-23
1-(4*(2*3))=-23
2*(1-(3*4))=-22
3*(1-(2*4))=-21
...
(1*4)*(2*3)=24
2*(3*(4/1))=24
... 此处省略其他56个值为24的算式
(2*3)/(1/4)=24
...
(1+3)*(2*4)=32
2*(4*(1+3))=32
(1+2)*(3*4)=36
4*(3*(1+2))=36
3*(4*(1+2))=36
(3*4)*(1+2)=36
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

上面用到了高效迭代库itertools,若不想用库可以用以下代码获得排列组合情况:

# 从lis序列中无放回的获取n个元素,返回所有可能的排列组合情况
def ff(lis, n):
    r=[]
    if n == 1:
        for i in lis:
            r.append([i])
        return r
    for i in range(0, len(lis)):
        first = lis[i]
        lis_c = lis.copy()
        del lis_c[i]
        r1 = f(lis_c, n-1)
        for ll in r1:
            ll.append(first)
            r.append(ll)
    return r
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

上面函数的示例:

li = [1,2,3,4]
A = ff(li,3)  # 内部有顺序的排列组合

m = map(lambda l: tuple(sorted(l)), A)
C = set(m) # 不考虑内部顺序的排列组合

print(A)
print(C)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

打印结果:

[[3, 2, 1], [4, 2, 1], [2, 3, 1], [4, 3, 1], [2, 4, 1], [3, 4, 1], [3, 1, 2], [4, 1, 2], [1, 3, 2], [4, 3, 2], [1, 4, 2], [3, 4, 2], [2, 1, 3], [4, 1, 3], [1, 2, 3], [4, 2, 3], [1, 4, 3], [2, 4, 3], [2, 1, 4], [3, 1, 4], [1, 2, 4], [3, 2, 4], [1, 3, 4], [2, 3, 4]]
{(2, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4)}
  • 1
  • 2