Su tarea es construir un número natural utilizando el menor número de unidades y solo los operadores +
o -
. Por ejemplo, el número siete se puede escribir 1+1+1+1+1+1+1=7
, pero también se puede escribir como 11-1-1-1-1=7
. El primero usa 7
unos, mientras que el último solo usa 6
. Su tarea es devolver el número mínimo de los que pueden ser utilizados dan la entrada de algún número natural, n
.
Este es el código golf, por lo que gana el código válido más corto en bytes.
Casos de prueba
Entrada => Salida
0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21
code-golf
number-theory
codeputer
fuente
fuente
VALID OUTPUTS
. Es su elección, pero en general a las personas les gusta negrita o cursiva en lugar de LETRAS MAYÚSCULAS (hacen que parezca gritar en lugar de énfasis). Negrita es**bold text**
y cursiva es*italics text*
. También puede usar### Text
para texto en negrita. De todos modos, ¡bienvenido a PPCG!Respuestas:
JavaScript (ES6),
12712687 bytesDebería funcionar hasta aproximadamente 10
1415, momento en el que comenzará a encontrarse con los límites enteros de JavaScript. Explicación:Esto usa la
n*9
magia dos veces; en primer lugar, me da la longitud de la próxima repunidad, en segundo lugar, si los dos primeros dígitos den*9
son55
o más, entonces tenemos que restarn
de la próxima repunidad, de lo contrario, tenemos que restar la repunidad anterior (que se calcula restando 1 y dividido por 10). Esto debería funcionar hasta 10 15 .fuente
Pyth,
1916 bytesBanco de pruebas
Algoritmo de fuerza bruta. Las cadenas necesarias se generan tomando todas las listas cuyos elementos tienen una
['+', '-', '']
longitud igual al número de 1s que se están probando, agregando un 1 a cada uno y concatenando a una sola cadena. Estas cadenas se evalúan y comparan con la entrada. Esto se repite hasta que se encuentra una cadena exitosa.Algunas cadenas con un líder
+
o-
se prueban, pero esto no es un problema. Sin embargo, sería si la entrada fuera negativa.Puede correr hasta la longitud 9 antes de que sea demasiado lento.
Explicación:
fuente
JavaScript (ES6), 92 bytes
Explicación
Función recursiva. Esto genera todas las posibles permutaciones de
1
s separados por cualquiera+
,-
o nada. Lo hace incrementando un número de base 3, convirtiéndolo en una matriz de dígitos, convirtiendo cada dígito0
a-
,1
en+
y2
a una cadena vacía, luego uniéndolos con1
s. La cadena resultante eseval
d como una declaración de JavaScript que devuelve el resultado de la ecuación.Debido a que los operadores están unidos con
1
s en el medio (como+1+1+1+
), haylength - 1
1
s. El primer operador es ignorado (porque+1
=1
,<nothing>1
=1
y es un número de modo que nunca habrá un líder0
para-
) y el operador final también se ignora (añadiendo.0
a la ecuación).Versión de salida superior, 96 bytes
La otra versión no puede devolver salidas superiores a ~ 10 debido al límite de la pila de llamadas de recursión. Esta versión utiliza un bucle for en lugar de recursividad, por lo que puede devolver salidas de hasta ~ 33. Sin embargo, la cantidad de tiempo requerida aumenta exponencialmente, por lo que no recomiendo probarlo.
fuente