Java - Ayuda con este ejercicio en java

   
Vista:

Ayuda con este ejercicio en java

Publicado por Juan Carlos (1 intervención) el 26/08/2014 19:27:52
Descripción del problema.



Si tomamos un entero positivo N lo podemos escribir de M formas distintas como suma de K enteros positivos elevados al cuadrado. Dos formas se consideran iguales si sólo difieren en el orden de los sumandos. Nota: El 0 no es un entero positivo.



Ejemplo.



El número 98 se puede escribir de 6 formas distintas como suma de 5 números elevados al cuadrado:



98 = 1 ^2 + 1 ^2 + 4 ^2 + 4 ^2 + 8 ^2
98 = 1 ^2 + 2 ^2 + 2 ^2 + 5 ^2 + 8 ^2
98 = 1 ^2 + 3 ^2 + 4 ^2 + 6 ^2 + 6 ^2
98 = 1 ^2 + 4 ^2 + 4 ^2 + 4 ^2 + 7 ^2
98 = 2 ^2 + 2 ^2 + 4 ^2 + 5 ^2 + 7 ^2
98 = 4 ^2 + 4 ^2 + 4 ^2 + 5 ^2 + 5 ^2



La forma 1 ^2 + 2 ^2 + 2 ^2 + 5 ^2 + 8 ^2 y la forma 2 ^2 + 8 ^2 + 1 ^2 + 2 ^2 + 5 ^2 son la misma porque sólo difieren en el orden de los sumandos, por lo cual, en el ejemplo, se contó sólo una de ellas.



Problema.



Escribe un programa que, dados N y K, encuentre el número M de formas en que se puede escribir N como la suma de K números elevados al cuadrado.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Ayuda con este ejercicio en java

Publicado por Tom (910 intervenciones) el 27/08/2014 09:20:20
Básicamente, te han propuesto jugar con lo que en Teoría de Números llaman Particiones.

En tu caso, supongo que la idea es ir generando todas las particiones posibles y comprobando que el número de partes es el solicitado y que cada parte es el cuadrado de otro número ... (a no ser, claro, que se te ocurra un algoritmo más eficaz).


http://www.site.uottawa.ca/~ivan/F49-int-part.pdf
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar