093. 算术表达式(Arithmetic expressions)

使用集合\(\{1,2,3,4\}\)中每个数字恰好一次、加减乘除\((+,-,*,/)\)四则运算以及括号,可以得到不同的正整数。例如:

$$ \begin{align*} &8 = (4 * (1 + 3)) / 2\\ &14 = 4 * (3 + 1 / 2)\\ &19 = 4 * (2 + 3) − 1\\ &36 = 3 * 4 * (2 + 1) \end{align*} $$
需要注意的是,把数字直接连接起来如\(12+34\)是不被允许的。使用集合\(\{1,2,3,4\}\)可以得到\(31\)个不同的数,其中最大值是\(36\),以及\(1\)\(28\)之间所有的整数。

若使用包含有四个不同数字\(a<b<c<d\)的集合可以得到从\(1\)\(n\)之间所有的整数,求其中使得\(n\)最大的集合,并将你的答案写成字符串\(abcd\)

分析:这道题我并没有找到除暴力方法以外的其它方法,主要思路是按照题目的要求遍历所有可能形成的算术表达式,再用\(python\)自带的\(eval\)函数对这些表达式求值,找到每一个整数组合能够形成的连续正整数的个数,然后返回其中形成的正整数个数最多的整数组合即可。为了遍历所有可能形成的算术表达式,需要考虑三种排列组合:

所以在不考虑算术表达式本身的有效性(除数不能为零)的情况下,我们可以形成的总的算术表达式共有\(3024\cdot64\cdot5=967680\)种。前两个排列数应该比较好理解,这里重点解释一下最后一个排列数。假设我们已经选定了四个整数\(a,b,c,d\)以及三种运算符\(\overline{op_1},\overline{op_2},\overline{op_3}\),则我们可以使用括号人为指定三个运算符的运算顺序,形成的全排列数为六种,分别如下:

可以看到,运算顺序\(1,3,2\)和运算顺序\(3,1,2\)在本质上是等价的,只需要保留一种,所以最后可以形成的不同的运算顺序共有五种。

因此,给定某四个整数的组合、选择不同的运算符以及运算顺序,我们可以计算出对应的算术表达式的结果(需要对除数为零的情况特殊处理,因此使用了\(try\cdots except\cdots\)语句),然后计算其中出现连续正整数的个数,最后我们找到出现连续正整数个数最多的整数组合,把它们拼接成字符串返回,即为题目所求。代码如下:

# time cost = 12.2 s ± 42 ms

from itertools import permutations,product,count,combinations

def eval_arith_expression(dp,op):
    arr = []
    expr = (dp[0],op[0],dp[1],op[1],dp[2],op[2],dp[3])
    s1 = "%d%s%d%s%d%s%d" % expr
    s2 = "(%d%s%d)%s(%d%s%d)" % expr
    s3 = "(%d%s(%d%s%d))%s%d" % expr
    s4 = "%d%s((%d%s%d)%s%d)" % expr
    s5 = "%d%s(%d%s(%d%s%d))" % expr
    for s in [s1,s2,s3,s4,s5]:
        try:
            arr.append(eval(s))
        except ZeroDivisionError:
            pass
    return arr

def consecutive_integers_number(integers):
    c = 0
    numbers = []
    operators = list(product(["+","-","*","/"],repeat=3))
    digits_perm = list(permutations(integers,4))
    for dp in digits_perm:
        for op in operators:
            numbers += eval_arith_expression(dp,op)
    for i in count(1):
        if i in numbers:
            c += 1
        else:
            return c

def main():
    d = {}
    for p in combinations(range(1,10),4):
        d[tuple(p)] = consecutive_integers_number(p)
    res = max(d,key=d.get)
    return "".join([str(x) for x in res])