Se le da un número entero no negativo n
y un número entero p >= 2
. Necesitas agregar algunas p
potencias ( p=2
significa cuadrados, p=3
significa cubos) juntas para obtener n
. Esto es siempre para cualquier no negativo n
, pero no sabes muchos p
poderes (de cualquier número entero positivo ) que necesitarás.
Esta es su tarea: encontrar el número mínimo de p
potencias que puede sumar n
.
Ejemplos
>>> min_powers(7, 2)
4 # you need at least four squares to add to 7
# Example: (2)^2 + (1)^2 + (1)^2 + (1)^2 = 4 + 1 + 1 + 1 = 7
>>> min_powers(4, 2)
1 # you need at least one square to add to 4
# Example: (2)^2 = 4
>>> min_powers(7, 3)
7 # you need at least seven cubes to add to 7
# Example: 7*(1)^3 = 7
>>> min_powers(23, 3)
9 # you need at least nine cubes to add to 23
# Example: 2*(2)^3 + 7*(1)^2 = 2*8 + 7*1 = 23
Un artículo relacionado de Wikipedia sobre este problema, el problema de Waring .
Reglas
Su código debe ser un programa o una función.
La entrada es dos enteros
n
yp
en cualquier orden. Puede suponer que todas las entradas son válidas (n
es cualquier número entero positivo,p >= 2
La salida es un número entero que representa el número de potencias necesarias para sumar
n
.Este es el código de golf, por lo que gana el programa más corto , no necesariamente el más eficiente.
Todos y cada uno de los elementos integrados están permitidos.
Como siempre, si el problema no está claro, hágamelo saber. ¡Buena suerte y buen golf!
fuente
Respuestas:
Pyth,
2019 bytesGuardado 1 byte gracias a FryAmTheEggman.
Toma entrada en dos líneas,
p
primero y luegon
.Pruébalo en línea. Banco de pruebas.
Explicación
El código define una función recursiva
y(b)
que devuelve el resultadomin_powers(b, p)
.fuente
Mathematica
6150 bytesCon 11 bytes guardados por LegionMammal978.
Cuando se limita a las potencias de contar números, este problema es sencillo (en Mathematica). Cuando se extiende para incluir poderes de enteros, es una pesadilla.
Casos de prueba
PowersRepresentationsp[n,k,p]
encuentra todos los casos en los quen
se puede expresar como una suma dek
enteros positivos elevados a lap
enésima potencia.Por ejemplo,
Comprobación,
fuente
Java -
183177bytes183 bytes
Sin golf
Resultado
fuente
p(32,2)
devuelve5
cuando debería devolver2
(4^2 + 4^2 = 32
).Python 2, 66 bytes
Intenta restando recursivamente cada una de las
p
potencias que deja el resto no negativo, calculando su valor en cada resto y tomando el mínimo más 1. En 0, las salidas 0.La comprobación fea
if n/k**p
(equivalente aif k**p<=n
) es evitar que la función entre en los negativos e intente quitar lamin
lista vacía. Si Python tienemin([])=infinity
, esto no sería necesario.fuente
C (gcc) , 122 bytes
Pruébalo en línea!
fuente