0093 算术表达式
* * * *
拉格朗日计划
* * * *
算术表达式

使用集合$\{1, 2, 3, 4\}$中每个数字恰好一次作为运算数,再加上四则运算$+, -, \times, /$和括号,可以表示许多不同的整数,例如 \begin{aligned} 8 & = (4 \times (1 + 3)) / 2 \\ 14 & = 4 \times (3 + 1 / 2) \\ 19 & = 4 \times (2 + 3) − 1 \\ 36 & = 3 \times 4 \times (2 + 1) \end{aligned} 按上述规则$\{1, 2, 3, 4\}$共可以表示31个不同的数,其中最大的是36,且可以表示1到28之间(包括1和28)的所有整数。

考虑所有由四个不同的一位数$a < b < c < d$组成的集合,求其中可以从1开始连续表示最多个正整数的集合,用字符串abcd的形式给出答案。

本题难度:



解答

显然a应当大于0,除此以外似乎只能暴力搜索。共有不超过$\binom{9}{4}\times 4!$种数字排列、$4^3$种运算符选择、和$3\times 2$种运算顺序,总计算量大约是百万级, 结果是$1258$,对应的可连续表达的数最大是51。

注:以下为Python3代码,因代码中需要使用Python3整数除法的新特性。

import itertools

m=0
r=""
for w in itertools.combinations(list("123456789"),4):
    t=set()
    for a,b,c,d in itertools.permutations(list(w)):
        for x,y,z in itertools.product(["+","-","*","/"],repeat=3):
            for s in ["(("+a+x+b+")"+y+c+")"+z+d,"("+a+x+b+")"+y+"("+c+z+d+")","("+a+x+"("+b+y+c+"))"+z+d,a+x+"(("+b+y+c+")"+z+d+")","("+a+x+b+")"+y+"("+c+z+d+")",a+x+"("+b+y+"("+c+z+d+"))"]:
                try:
                    q=1.0*eval(s)
                    if q>0 and q.is_integer():
                        t.add(int(q))
                except:
                    continue
    p=sorted(list(t))
    i=0
    while i < len(p) and p[i]==i+1:
        i+=1
    if i>m:
        m=i
        r="".join(sorted([a,b,c,d]))

print(r,m)