sextos para octavos necesitan formar cuantos algorithm math dynamic-programming

algorithm - para - ¿Cómo expresar un entero usando los símbolos+*() y 1 con un costo mínimo?



cuantos octavos se necesitan para formar 1/2 (2)

La tarea es construir números enteros a partir de los símbolos + * ( ) (suma, multiplicación y corchetes) y el dígito 1 . Se le da un número entero y debe dar salida a una expresión utilizando el número mínimo de caracteres. Por ejemplo:

4 = 1+1+1+1 23 = 11+11+1 242 = (11+11)*11 1000 = 1+(1+1+1)*(1+1+1)*111 1997 = (1+1)*(1+1+1)*111+11*11*11


Aquí está mi solución recursiva. Funciona para 2000 elementos en aproximadamente 1.4 segundos en mi tableta:

import math def to_onestr(n, numbers=None, divs=None): if numbers is None: numbers = [None] * (n + 1) numbers[0] = ('''', False) if divs is None: divs = get_divs(n) if numbers[n] is None: s = str(n) # Default representation is 11111 or 1+1+1+1 if s == ''1''*len(s): res = (s, False) else: res = ("+".join([''1''] * n), True) # Find all representations d*k + r, d < k for d in divs: if d >= n: break k, r = divmod(n, d) if k < d: d, k = k, d k_res, r_res, d_res = to_onestr(k, numbers, divs), to_onestr(r, numbers, divs), to_onestr(d, numbers, divs) res_str, res_bool = '''', False if d != 1: res_str += ''({})*''.format(d_res[0]) if d_res[1] else d_res[0] + ''*'' res_str += ''({})''.format(k_res[0]) if k_res[1] else k_res[0] if d != 1 and len(k_res[0]) * d + d - 1 < len(res_str): res_str = ''+''.join([k_res[0]]*d) res_bool = True if r != 0: res_str += ''+{}''.format(r_res[0]) res_bool = True if len(res_str) < len(res[0]): res = (res_str, res_bool) numbers[n] = res return numbers[n] def get_divs(n): p = [1] * (n + 1) # Get all prime numbers + all numbers which contains only 1 + all numbers we could get from 11..1 by multiplication for i in range(2, int(math.ceil(math.sqrt(n)))): if p[i] == 1: for j in range(i * i, n, i): if j % i == 0: p[j] = 0 for x in xrange(2, len(str(n)) + 1): i = int(''1''*x) j = i while j <= n: p[j] = 1 j = j * i return [i for (i, v) in enumerate(p) if v == 1 and i > 1]

Pruebas de velocidad:

>>> timeit(''to_onestr(2000)'', ''from __main__ import to_onestr'', number=1) 1.1375278780336457 >>> timeit(''to_onestr(4000)'', ''from __main__ import to_onestr'', number=1) 3.6481025870678696 >>> timeit(''to_onestr(6000)'', ''from __main__ import to_onestr'', number=1) 7.732885259577177

También probado el enfoque @Anonymous

>>> timeit(''minconstruct(2000)'', ''from __main__ import minconstruct'', number=1) 12.012599471759474


Puede usar la programación dinámica y calcular, para cada número i <n, la expresión más corta que calcula i, y la expresión más corta que calcula i que se puede usar en un contexto multiplicativo. En general, la segunda expresión será más larga que la primera: por ejemplo, 2 puede construirse como ''1 + 1'', pero si quiere un ''2'' en una multiplicación, entonces será ''(1 + 1)''.

Aquí hay un código no optimizado que imprime las soluciones más cortas para todos los números hasta el 2000. Se ejecuta en una fracción de más de 2 segundos en mi computadora portátil, pero hay mucho margen para eliminar toda la construcción de cadenas del código. Se ejecuta en tiempo O (n ^ 2).

def getbest(a, b): return a or b if not (a and b) else min((a, b), key=len) def minconstruct(n): res = [[None, None] for _ in range(n + 1)] for i in xrange(1, n + 1): if set(str(i)) == set(''1''): res[i][0] = res[i][1] = str(i) for j in xrange(1, i // 2 + 1): sol = ''%s+%s'' % (res[j][0], res[i-j][0]) res[i][0] = getbest(res[i][0], sol) res[i][1] = getbest(res[i][1], ''('' + sol + '')'') for j in xrange(2, i): if i % j != 0: continue sol = ''%s*%s'' % (res[j][1], res[i//j][1]) res[i][0] = getbest(res[i][0], sol) res[i][1] = getbest(res[i][1], sol) return res r = minconstruct(2000) for i, x in enumerate(r[1:]): print ''%4d: %s'' % (i, x[0])