Ternas pitagóricas
Una terna (x,y,z) de enteros positivos es pitagórica si x² + y² = z² y x < y < z.
Definir la función
|
1 |
pitagoricas :: Int -> [(Int,Int,Int)] |
tal que pitagoricas n es la lista de todas las ternas pitagóricas cuyas componentes están entre 1 y n. Por ejemplo,
|
1 2 |
pitagoricas 10 == [(3,4,5),(6,8,10)] pitagoricas 15 == [(3,4,5),(5,12,13),(6,8,10),(9,12,15)] |
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 |
import Test.QuickCheck -- 1ª solución -- =========== pitagoricas1 :: Int -> [(Int,Int,Int)] pitagoricas1 n = [(x,y,z) | x <- [1..n] , y <- [1..n] , z <- [1..n] , x^2 + y^2 == z^2 , x < y && y < z] -- 2ª solución -- =========== pitagoricas2 :: Int -> [(Int,Int,Int)] pitagoricas2 n = [(x,y,z) | x <- [1..n] , y <- [x+1..n] , z <- [ceiling (sqrt (fromIntegral (x^2+y^2)))..n] , x^2 + y^2 == z^2] -- 3ª solución -- =========== pitagoricas3 :: Int -> [(Int,Int,Int)] pitagoricas3 n = [(x,y,z) | x <- [1..n] , y <- [x+1..n] , let z = round (sqrt (fromIntegral (x^2+y^2))) , y < z , z <= n , x^2 + y^2 == z^2] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pitagoricas :: Positive Int -> Bool prop_pitagoricas (Positive n) = all (== pitagoricas1 n) [pitagoricas2 n, pitagoricas3 n] -- La comprobación es -- λ> quickCheck prop_pitagoricas -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (pitagoricas1 200) -- 127 -- (12.25 secs, 12,680,320,400 bytes) -- λ> length (pitagoricas2 200) -- 127 -- (1.61 secs, 1,679,376,824 bytes) -- λ> length (pitagoricas3 200) -- 127 -- (0.06 secs, 55,837,072 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 |
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 pitagoricas1(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(1, n+1) for z in range(1, n+1) if x**2 + y**2 == z**2 and x < y < z] # 2ª solución # =========== def pitagoricas2(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(x+1, n+1) for z in range(ceil(sqrt(x**2+y**2)), n+1) if x**2 + y**2 == z**2] # 3ª solución # =========== def pitagoricas3(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(x+1, n+1) for z in [ceil(sqrt(x**2+y**2))] if y < z <= n and x**2 + y**2 == z**2] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=50)) def test_pitagoricas(n: int) -> None: r = pitagoricas1(n) assert pitagoricas2(n) == r assert pitagoricas3(n) == r # La comprobación es # src> poetry run pytest -q ternas_pitagoricas.py # 1 passed in 1.83s # Comparación de eficiencia de pitagoricas # ====================================== 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('pitagoricas1(200)') # 4.76 segundos # >>> tiempo('pitagoricas2(200)') # 0.69 segundos # >>> tiempo('pitagoricas3(200)') # 0.02 segundos |
El código se encuentra en GitHub.