Triángulo aritmético
Los triángulos aritméticos se forman como sigue
|
1 2 3 4 5 6 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Definir las funciones
|
1 2 |
linea :: Integer -> [Integer] triangulo :: Integer -> [[Integer]] |
tales que
linea nes la línea n-ésima de los triángulos aritméticos. Por ejemplo,
|
1 2 3 |
linea 4 == [7,8,9,10] linea 5 == [11,12,13,14,15] head (linea (10^20)) == 4999999999999999999950000000000000000001 |
triangulo nes el triángulo aritmético de alturan. Por ejemplo,
|
1 2 |
triangulo 3 == [[1],[2,3],[4,5,6]] triangulo 4 == [[1],[2,3],[4,5,6],[7,8,9,10]] |
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
import Test.QuickCheck -- 1ª definición de línea -- ====================== linea1 :: Integer -> [Integer] linea1 n = [suma1 (n-1)+1..suma1 n] -- (suma n) es la suma de los n primeros números. Por ejemplo, -- suma 3 == 6 suma1 :: Integer -> Integer suma1 n = sum [1..n] -- 2ª definición de línea -- ====================== linea2 :: Integer -> [Integer] linea2 n = [s+1..s+n] where s = suma1 (n-1) -- 3ª definición de línea -- ====================== linea3 :: Integer -> [Integer] linea3 n = [s+1..s+n] where s = suma2 (n-1) suma2 :: Integer -> Integer suma2 n = (1+n)*n `div` 2 -- Comprobación de equivalencia de linea -- ===================================== -- La propiedad es prop_linea :: Positive Integer -> Bool prop_linea (Positive n) = all (== linea1 n) [linea2 n, linea3 n] -- La comprobación es -- λ> quickCheck prop_linea -- +++ OK, passed 100 tests. -- Comparación de eficiencia de linea -- ================================== -- La comparación es -- λ> last (linea1 (10^7)) -- 50000005000000 -- (5.10 secs, 3,945,159,856 bytes) -- λ> last (linea2 (10^7)) -- 50000005000000 -- (3.11 secs, 2,332,859,512 bytes) -- λ> last (linea3 (10^7)) -- 50000005000000 -- (0.16 secs, 720,559,384 bytes) -- 1ª definición de triangulo -- ========================== triangulo1 :: Integer -> [[Integer]] triangulo1 n = [linea1 m | m <- [1..n]] -- 2ª definición de triangulo -- ========================== triangulo2 :: Integer -> [[Integer]] triangulo2 n = [linea2 m | m <- [1..n]] -- 3ª definición de triangulo -- ========================== triangulo3 :: Integer -> [[Integer]] triangulo3 n = [linea3 m | m <- [1..n]] -- Comprobación de equivalencia de triangulo -- ========================================= -- La propiedad es prop_triangulo :: Positive Integer -> Bool prop_triangulo (Positive n) = all (== triangulo1 n) [triangulo2 n, triangulo3 n] -- La comprobación es -- λ> quickCheck prop_triangulo -- +++ OK, passed 100 tests. -- Comparación de eficiencia de triangulo -- ====================================== -- La comparación es -- λ> last (last (triangulo1 (3*10^6))) -- 4500001500000 -- (2.25 secs, 1,735,919,184 bytes) -- λ> last (last (triangulo2 (3*10^6))) -- 4500001500000 -- (1.62 secs, 1,252,238,872 bytes) -- λ> last (last (triangulo3 (3*10^6))) -- 4500001500000 -- (0.79 secs, 768,558,776 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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
from timeit import Timer, default_timer from hypothesis import given, strategies as st # 1ª definición de línea # ====================== # suma(n) es la suma de los n primeros números. Por ejemplo, # suma(3) == 6 def suma1(n: int) -> int: return sum(range(1, n + 1)) def linea1(n: int) -> list[int]: return list(range(suma1(n - 1) + 1, suma1(n) + 1)) # 2ª definición de línea # ====================== def linea2(n: int) -> list[int]: s = suma1(n-1) return list(range(s + 1, s + n + 1)) # 3ª definición de línea # ====================== def suma2(n: int) -> int: return (1 + n) * n // 2 def linea3(n: int) -> list[int]: s = suma2(n-1) return list(range(s + 1, s + n + 1)) # Comprobación de equivalencia de linea # ===================================== @given(st.integers(min_value=1, max_value=1000)) def test_suma(n): r = linea1(n) assert linea2(n) == r assert linea3(n) == r # La comprobación es # src> poetry run pytest -q triangulo_aritmetico.py # 1 passed in 0.15s # Comparación de eficiencia # ========================= def tiempo(e): """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('linea1(10**7)') # 0.53 segundos # >>> tiempo('linea2(10**7)') # 0.40 segundos # >>> tiempo('linea3(10**7)') # 0.29 segundos # 1ª definición de triangulo # ========================== def triangulo1(n: int) -> list[list[int]]: return [linea1(m) for m in range(1, n + 1)] # 2ª definición de triangulo # ========================== def triangulo2(n: int) -> list[list[int]]: return [linea2(m) for m in range(1, n + 1)] # 3ª definición de triangulo # ========================== def triangulo3(n: int) -> list[list[int]]: return [linea3(m) for m in range(1, n + 1)] # Comprobación de equivalencia de triangulo # ========================================= @given(st.integers(min_value=1, max_value=1000)) def test_triangulo(n): r = triangulo1(n) assert triangulo2(n) == r assert triangulo3(n) == r # La comprobación es # src> poetry run pytest -q triangulo_aritmetico.py # 1 passed in 3.44s # Comparación de eficiencia de triangulo # ====================================== # # La comparación es # >>> tiempo('triangulo1(10**4)') # 2.58 segundos # >>> tiempo('triangulo2(10**4)') # 1.91 segundos # >>> tiempo('triangulo3(10**4)') # 1.26 segundos |
El código se encuentra en GitHub.