Su tarea es escribir un programa que, en la entrada n, genere la expresión mínima de cada número del 1 al n en orden. El programa más corto en bytes gana.
Una expresión mínima combina los 1 con la suma y la multiplicación para dar como resultado el número dado, utilizando la menor cantidad posible de 1. Por ejemplo, 23
se expresa 23=((1+1+1)(1+1)+1)(1+1+1)+1+1
con once, que es mínimo.
Requisitos:
- El programa debe tomar como entrada un número natural positivo n.
- La salida debe estar en este formato:
20 = ((1+1+1)(1+1+1)+1)(1+1)
- Su salida puede no tener paréntesis innecesarios, como
8 = ((1+1)(1+1))(1+1)
. - El signo de multiplicación
*
es opcional. - Los espacios son opcionales.
- No tiene que generar todas las ecuaciones posibles para un valor dado: por ejemplo, tiene la opción de generar
4=1+1+1+1
o4=(1+1)(1+1)
. No tiene que dar salida a ambos. - El programa más corto (en bytes) en cada idioma gana.
1 = 1 2 = 1 + 1 3 = 1 + 1 + 1 4 = 1 + 1 + 1 + 1 5 = 1 + 1 + 1 + 1 + 1 6 = (1 + 1 + 1) (1 + 1) 7 = (1 + 1 + 1) (1 + 1) +1 8 = (1 + 1 + 1 + 1) (1 + 1) 9 = (1 + 1 + 1) (1 + 1 + 1) 10 = (1 + 1 + 1) (1 + 1 + 1) +1 11 = (1 + 1 + 1) (1 + 1 + 1) + 1 + 1 12 = (1 + 1 + 1) (1 + 1) (1 + 1) 13 = (1 + 1 + 1) (1 + 1) (1 + 1) +1 14 = ((1 + 1 + 1) (1 + 1) +1) (1 + 1) 15 = (1 + 1 + 1 + 1 + 1) (1 + 1 + 1) 16 = (1 + 1 + 1 + 1) (1 + 1) (1 + 1) 17 = (1 + 1 + 1 + 1) (1 + 1) (1 + 1) +1 18 = (1 + 1 + 1) (1 + 1 + 1) (1 + 1) 19 = (1 + 1 + 1) (1 + 1 + 1) (1 + 1) +1 20 = ((1 + 1 + 1) (1 + 1 + 1) +1) (1 + 1)
Aquí hay algunos casos de prueba más: (recuerde que también se permiten otras expresiones con el mismo número de 1)
157=((1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1
444=((1+1+1)(1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)
1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1
15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1
45197=((((1+1+1)(1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1+1)+1+1
¡Buena suerte! - La tortuga 🐢
code-golf
math
arithmetic
La tortuga
fuente
fuente
n=20
) y 2) dice al principio que la complejidad del entero, que es distinta de la ecuación, tiene que salir, pero no incluye eso en cualquiera de los ejemplos excepto el primero.Respuestas:
Pyth, 60 bytes
Demostración
El compilador en línea puede llegar a 1223 antes del tiempo de espera, gracias a la memorización automática de funciones de Pyth.
En nota abreviada,
Utiliza una función recursiva
'
, que calcula todos los productos posibles y sumas que podrían dar el resultado deseado, encuentra la cadena más corta con cada operación final, luego las compara por1
conteo y devuelve la primera.Utiliza una función auxiliar
y
, que paréntesis de una expresión solo si necesita ser entre paréntesis.Fuera de línea, estoy ejecutando el programa con la entrada
15535
, y está casi completo. Los resultados se imprimen de forma incremental, por lo que es fácil ver el progreso.Líneas finales de la salida:
En notación abreviada,
fuente
CJAM,
1051029896 bytesPruébelo en línea en el intérprete de CJam .
Prueba de funcionamiento
El intérprete en línea es demasiado lento para los casos de prueba más grandes. Incluso con el intérprete de Java, los casos de prueba más grandes tomarán mucho tiempo y requerirán una cantidad significativa de memoria.
Con suficiente tiempo, produciría estas soluciones para los próximos casos de prueba:
fuente
Julia, 229 bytes
Esto es realmente bastante rápido. Asignar la función
f
y ejecutarla@time f(15535)
proporciona la salida (solo las dos últimas líneas)y para
@time f(45197)
, daEntonces, ¿qué está haciendo el código? Simple:
C
contiene la cantidad actualC
para el número,K
es una matriz de indicadores que realiza un seguimiento de si la expresión es, fundamentalmente, una suma o un producto, con el propósito de tratar con los corchetes, yE
contiene laE
propia expresión. Avanzando des=1
principio a finn
, el código busca la representación mínima del números
en términos de valores más bajos, buscando una suma o un producto. Si se trata de un producto, comprueba los dos componentes y pone corchetes alrededor de ellos si son sumas. Esa verificación se realiza en funciónF
, para guardar bytes (porque tiene que hacerse dos veces, para los dos factores).fuente