Project Euler 93：Arithmetic expressions 算术表达式

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

算术表达式

使用集合{1, 2, 3, 4}中每个数字恰好一次以及(+, −, *, /)四则运算和括号，可以得到不同的正整数。

例如，

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

注意不允许直接把数字连起来，如12 + 34。

使用集合{1, 2, 3, 4}，可以得到31个不同的数，其中最大值是36，以及1到28之间所有的数。

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

解题

表示感觉不知道如何下手！！！？？？

在先找打答案，然后看论坛中的讲解，找到一个很笨的方法。

1.先找出运算符和括号的所有匹配表达式

2.这里的表达式是中序表达式，转换成后续表达式，在转换成后序表达式的过程中去除括号

3.后序表达式是最用于求解的了，对每个表达式，求解

4.对固定的a b c d 求解后，需要判断解是否是1到n的值，若是，则记录最大值n

5.对所有的a b c d 找出最大的n

上面的计算结果都是负的。。。不明白

下面看到论坛中Python实现的，程序中进行了注释，感觉就是运气得出的答案。

# coding=gbk

import time as time 
from itertools import permutations
from itertools import combinations
from itertools import product
# 解题思路：
# 对0-9内人去4个数
# 四种运算任意组合
# 对取得4个数和四种运算组合的一种进行计算，
##   取得4个数再任意排列，和唯一的运算符组合进行计算 
# 但是为什么不考虑括号的问题，不加括号也算了，为什么四则运算的先后顺序也变了，我表示很费解。但是结果还对了
# 四个运算符取三个，就是运算符的所以可能
ops_set = list(product("+-*/","+-*/","+-*/"))

print 0/3
print 12/3
print 13/3
l = [1,2,3,4]
for i in range(4):
    print l.pop()
def calc(ls,ops):
    l = [float(i) for i in ls ]
    
    t = l.pop()
    for op in ops:
        if op== '+':
            t+= l.pop()
        elif op=='-':
            t -=l.pop()
        elif op=='*':
            t *=l.pop()
        else:
            k=l.pop()
            if k==0:
                return 0
            t/=k
    print ls ,ops ,t 
    if int(t) == t:
        return abs(int(t))
    
    return 0

def getlongest(ls):
    l = list(permutations(ls,4))
#     print l 
    s = sorted(list(set([calc(ll,ops) for ops in ops_set for ll in l])))
    last_n = 0 
    for n in s:
        if n==0:continue
        if n == last_n+1:
            last_n = n
            continue
        break 
    return last_n 

def run():
    maxx=[0]
    for l in permutations(range(10),4):
#         print l 
        x = getlongest(l)
        if x>maxx[0]:
            maxx = [x,l]
    print maxx 
    
t0 = time.time()
run() 
t1 = time.time()
print "running time=",(t1-t0),"s"

View Code

表示现在还无法理解，以后继续完善