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 el 19 ene. 2018 a las 12:13
  • 1
    Sabiendo n, dando valores a b puedes calcular c reduciendo la complejidad algorítmica. 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
    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
    el 20 ene. 2018 a las 18:56

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

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