Как написать программу, чтобы получить все методы, чтобы получить 2016, используя числа от 9 до 1?

Question

Вы можете добавить любой оператор (включая скобки и + - */**) от 9 8 7 6 5 4 3 2 1. Например, 98*76-5432*1=2016 9*8*7*(6+5-4-3)*(2-1)=2016

Я написал программу, как этот

from __future__ import division 
s = ['+','-','*','/','','(',')'] 

def calc(s): 
    a=s.split() 
    return eval(''.join(a)) 
a=['','9','','8','','7','','6','','5','','4','','3','','2','','1.',''] 

def test(tmp): 
    if tmp == 20: 
     try: 
      z = eval(''.join(a)) 
      if z == 2016: 
       print ''.join(a) 
     except: 
      pass 
     return 
    for i in s: 
     #print a 
     a[tmp] = i 
     test(tmp+2) 
for j in s: 
    a[0] = j 
    test(2) 

Но это неправильно, потому что между числами существует множество операторов.

Answer 1

Существует хорошо известный трюк для вопросов, связанных с построением арифметических выражений с помощью скобок: часто проще использовать обратную полировку.

Вот код, который делает это.

# Compute "a op b", returning None if the result 
# is no good (eg: 9/0 or too big). 
def do_op(a, op, b): 
    if op == '+': 
     return a + b 
    if op == '-': 
     return a - b 
    if op == '*': 
     return a * b 
    if op == '/': 
     if b == 0 or a % b != 0: 
      return None 
     return a // b 
    if op == '**': 
     # Disallow arguments that would result 
     # in fractions or huge numbers, being careful 
     # to allow valid results. 
     if a == 1: 
      return a 
     if a == -1: 
      return -1 if b % 2 else 1 
     if a == 0 and b == 0: 
      return None 
     if b < 0 or b > 20 or a > 10000 or a < -10000: 
      return None 
     return a ** b 
    assert False 

# Generates expressions that result in the given target. 
# ops is the a record of the operations applied so far, 
# stack is the evaluation stack, and num is the first 
# digit that we've not pushed yet. 
def sums(ops, stack, num, target): 
    if not num and len(stack) == 1: 
     if stack[0] == target: 
      yield ops 
     return 

    # If num is 7, say, try pushing 7, 76, 765, 7654, ..., 7654321. 
    k = num 
    for i in xrange(num, 0, -1): 
     for s in sums(ops + [k], stack + [k], i-1, target): 
      yield s 
     k = 10 * k + (i - 1) 

    # If we've less that 2 things on the stack, we can't apply 
    # any operations. 
    if len(stack) < 2: 
     return 

    # Try each of the possible ops in turn. 
    for op in ['+', '-', '*', '/', '**']: 
     result = do_op(stack[-2], op, stack[-1]) 
     if result is None: 
      continue 
     for s in sums(ops + [op], stack[:-2] + [result], num, target): 
      yield s 


# Convert a list of operations that represent an expression in RPN 
# into infix notation. Every operation is bracketed, even when 
# that's redundant. 
def to_infix(ops): 
    stack = [] 
    for p in ops: 
     if isinstance(p, int): 
      stack = stack + [p] 
     else: 
      stack = stack[:-2] + ['(%s%s%s)' % (stack[-2], p, stack[-1])] 

    assert len(stack) == 1 
    return stack[0] 

# Starting with an empty stack (and no operations), with 9 as the first 
# unused digit, generate all expressions that evaluate to 2016. 
for s in sums([], [], 9, 2016): 
    print to_infix(s) 

Это занимает несколько минут, чтобы бежать, но есть много (более 25000) действительных выражений, оценивающих к 2016 году

Мой любимый (((98 * 76) -5432) * 1).