Ternas pitagóricas con suma dada
Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.
Definir la función
|
1 |
ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)] |
tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,
|
1 2 3 |
ternasPitagoricas 12 == [(3,4,5)] ternasPitagoricas 60 == [(10,24,26),(15,20,25)] ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import Data.List (nub,sort) import Test.QuickCheck -- 1ª solución -- -- =========== ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas1 x = [(a,b,c) | a <- [0..x], b <- [a+1..x], c <- [b+1..x], a^2 + b^2 == c^2, a+b+c == x] -- 2ª solución -- -- =========== ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas2 x = [(a,b,c) | a <- [1..x], b <- [a+1..x-a], let c = x-a-b, a^2+b^2 == c^2] -- 3ª solución -- -- =========== -- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse -- por -- a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2, -- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ). ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas3 x = nub [(d*a,d*b,d*c) | d <- [1..x], x `mod` d == 0, (a,b,c) <- aux (x `div` d)] where aux y = [(a,b,c) | m <- [2..limite], n <- [1..m-1], let [a,b] = sort [m^2 - n^2, 2*m*n], let c = m^2 + n^2, a+b+c == y] where limite = ceiling (sqrt (fromIntegral y)) -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_ternasPitagoricas :: Positive Integer -> Bool prop_ternasPitagoricas (Positive x) = all (== (ternasPitagoricas1 x)) [ternasPitagoricas2 x, ternasPitagoricas3 x] -- La comprobación es -- λ> quickCheck prop_ternasPitagoricas -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> ternasPitagoricas1 200 -- [(40,75,85)] -- (1.90 secs, 2,404,800,856 bytes) -- λ> ternasPitagoricas2 200 -- [(40,75,85)] -- (0.06 secs, 19,334,232 bytes) -- λ> ternasPitagoricas3 200 -- [(40,75,85)] -- (0.01 secs, 994,224 bytes) -- -- λ> ternasPitagoricas2 3000 -- [(500,1200,1300),(600,1125,1275),(750,1000,1250)] -- (4.41 secs, 4,354,148,136 bytes) -- λ> ternasPitagoricas3 3000 -- [(500,1200,1300),(600,1125,1275),(750,1000,1250)] -- (0.05 secs, 17,110,360 bytes) |
El código se encuentra en GitHub.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
from math import ceil, sqrt from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st # 1ª solución -- # =========== def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]: return [(a, b, c) for a in range(0, x+1) for b in range(a+1, x+1) for c in range(b+1, x+1) if a**2 + b**2 == c**2 and a + b + c == x] # 2ª solución -- # =========== def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]: return [(a, b, c) for a in range(1, x+1) for b in range(a+1, x-a+1) for c in [x - a - b] if a**2 + b**2 == c**2] # 3ª solución -- # =========== # Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse # por # a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2, # con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ). def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]: def aux(y: int) -> list[tuple[int, int, int]]: return [(a, b, c) for m in range(2, 1 + ceil(sqrt(y))) for n in range(1, m) for a in [min(m**2 - n**2, 2*m*n)] for b in [max(m**2 - n**2, 2*m*n)] for c in [m**2 + n**2] if a+b+c == y] return list(set(((d*a, d*b, d*c) for d in range(1, x+1) for (a, b, c) in aux(x // d) if x % d == 0))) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=50)) def test_ternasPitagoricas(n: int) -> None: r = set(ternasPitagoricas1(n)) assert set(ternasPitagoricas2(n)) == r assert set(ternasPitagoricas3(n)) == r # La comprobación es # src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.py # 1 passed in 0.35s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('ternasPitagoricas1(300)') # 2.83 segundos # >>> tiempo('ternasPitagoricas2(300)') # 0.01 segundos # >>> tiempo('ternasPitagoricas3(300)') # 0.00 segundos # # >>> tiempo('ternasPitagoricas2(3000)') # 1.48 segundos # >>> tiempo('ternasPitagoricas3(3000)') # 0.02 segundos |
El código se encuentra en GitHub.