1

Necesito realizar un programa en el cual introduzca un número, y me diga las ternas pitágoricas (a,b,c) tales que a sea el número introducido. Esto es;

ternasPitagoricas :: Integer -> [(Integer, Integer, Integer)]
ternasPitagoricas 25 == [(25,60,65),(25,312,313)]
ternasPitagoricas 20 == [(20,15,25),(20,21,29),(20,48,52),(20,99,101)]

Lo he intentando de la siguiente forma, pero es muy ineficiente, pues para números bajos funciona, pero cuando piden un número alto no lo llega a realizar.

ternasPitagoricas :: Integer -> [(Integer, Integer, Integer)]
ternasPitagoricas n = [(n,b,c) | c <- [2..n^2], b <- [2..c-1], n^2 + b^2 == c^2]

Necesito que la función sirva para ternasPitagoricas 20^100000, pero no llego a conseguirlo.

Por si no sabéis lo que es una terna pitagórica : https://es.wikipedia.org/wiki/Terna_pitagórica

Muchas gracias.

3
  • 1
    Para la próxima vez, intenta que el código se vea como bloque y no como líneas sueltas (Basta seleccionar todas las líneas y seleccionar Control-K). Tienes ayuda en es.stackoverflow.com/editing-help Commented el 19 ene. 2018 a las 12:13
  • 1
    Sabiendo n, dando valores a b puedes calcular c reduciendo la complejidad algorítmica. Commented el 19 ene. 2018 a las 12:30
  • @ChemaCortes Entiendo lo que quieres decir, pero no sé cómo plantear en Haskell lo que me dices. Es decir, no se escribirlo. Muchas gracias, y la proxima vez escribiré todo como un bloque (no sabía cómo se hacía).
    – Carlos
    Commented el 19 ene. 2018 a las 12:39

1 respuesta 1

1

Si conoces a y estás probando valores de c, entonces puedes calcular el valor de b y evitar probar todos sus valores posibles:

b = (round . sqrt . fromIntegral) (c^2 - a^2)

Veamos si se puede hacer mejor...

Empezando por las matemáticas, tenemos que para números reales ℝ:

∀ a ∈ ℝ , ∃ b,c ∈ ℝ ⇒ a² + b² = c²

En cambio, para números enteros ℤ sólo se cumple para algunos casos que son las llamadas ternas pitagóricas.

Veamos algunas restricciones que podemos deducir para b y c:

De a² + b² = c², se ve que b será siempre estrictamente menor que c: 1 ≤ b < c que, expresado en haskell sería: b <- [1..c-1].

Así mismo, podemos deducir las siguientes restriciones para c: a < c ≤ (a²+1)/2 que en haskell sería:

c <- [a+1..a^2+1 `div` 2]

Todo junto:

ternasPitagoricas :: Integer -> [(Integer, Integer, Integer)]
ternasPitagoricas a = [(a,b,c) | c <- [a+1..(a^2+1) `div` 2]
                               , let b = (round . sqrt . fromIntegral) (c^2 - a^2)
                               , a^2 + b^2 == c^2]

Por último, cuando dices:

Necesito que la función sirva para ternasPitagoricas 20^100000, pero no llego a conseguirlo.

Antes imponerte este objetivonción que necesitas, tienes que analizar mejor qué estás pidiendo, empezando por crear una función que funcione para pequeños casos y estudiar cómo es posible escalar para alcanzar objetivos mayores.

El número 20^100000 es un número gigantesco. La función anterior tendría que recorrer todos los números enteros desde este número hasta su cuadrado, 20^200000, lo que seguramente serían unos cuantos siglos de cálculo.

Pero hay otro problema aún más irresoluble: este número es imposible de representar como número de coma flotante sin usar librerías especializadas. Si te das cuenta, el cálculo de b usa sqrt, que no es usable para números muy muy grandes.

No conozco formas de calcular más rápido las ternas. Realmente es un problema matemático y aquí estamos para resolver problemas de programación.

1
  • Muchas gracias
    – Carlos
    Commented el 20 ene. 2018 a las 18:56

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.