Suma de los primeros números naturales
Definir la función
1 |
suma :: Integer -> Integer |
tal suma n
es la suma de los n
primeros números. Por ejemplo,
1 2 |
suma 3 == 6 length (show (suma (10^100))) == 200 |
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 |
import Data.List (foldl') import Test.QuickCheck -- 1ª solución -- =========== suma1 :: Integer -> Integer suma1 n = sum [1..n] -- 2ª solución -- =========== suma2 :: Integer -> Integer suma2 n = (1+n)*n `div` 2 -- 3ª solución -- =========== suma3 :: Integer -> Integer suma3 1 = 1 suma3 n = n + suma3 (n-1) -- 4ª solución -- =========== suma4 :: Integer -> Integer suma4 n = foldl (+) 0 [0..n] -- 5ª solución -- =========== suma5 :: Integer -> Integer suma5 n = foldl' (+) 0 [0..n] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_suma :: Positive Integer -> Bool prop_suma (Positive n) = all (== suma1 n) [suma2 n, suma3 n, suma4 n, suma5 n] -- La comprobación es -- λ> quickCheck prop_suma -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> suma1 (5*10^6) -- 12500002500000 -- (1.23 secs, 806,692,792 bytes) -- λ> suma2 (5*10^6) -- 12500002500000 -- (0.02 secs, 559,064 bytes) -- λ> suma3 (5*10^6) -- 12500002500000 -- (3.06 secs, 1,214,684,352 bytes) -- λ> suma4 (5*10^6) -- 12500002500000 -- (1.25 secs, 806,692,848 bytes) -- λ> suma5 (5*10^6) -- 12500002500000 -- (0.26 secs, 440,559,048 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 102 103 |
from operator import add from functools import reduce from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given, strategies as st setrecursionlimit(10**8) # 1ª solución # =========== def suma1(n: int) -> int: return sum(range(1, n + 1)) # 2ª solución # =========== def suma2(n: int) -> int: return (1 + n) * n // 2 # 3ª solución # =========== def suma3(n: int) -> int: if n == 1: return 1 return n + suma3(n - 1) # 4ª solución # =========== def suma4(n: int) -> int: return reduce(add, range(1, n + 1)) # 5ª solución # =========== def suma5(n: int) -> int: x, r = 1, 0 while x <= n: r = r + x x = x + 1 return r # 6ª solución # =========== def suma6(n: int) -> int: r = 0 for x in range(1, n + 1): r = r + x return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_suma(n): r = suma1(n) assert suma2(n) == r assert suma3(n) == r assert suma4(n) == r assert suma5(n) == r assert suma6(n) == r # La comprobación es # src> poetry run pytest -q suma_de_los_primeros_numeros_naturales.py # 1 passed in 0.16s # 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('suma3(20000)') # 0.04 segundos # >>> tiempo('suma1(20000)') # 0.00 segundos # >>> tiempo('suma2(20000)') # 0.00 segundos # >>> tiempo('suma3(20000)') # 0.02 segundos # >>> tiempo('suma4(20000)') # 0.00 segundos # >>> tiempo('suma5(20000)') # 0.01 segundos # >>> tiempo('suma6(20000)') # 0.00 segundos # # >>> tiempo('suma1(10**8)') # 1.55 segundos # >>> tiempo('suma2(10**8)') # 0.00 segundos # >>> tiempo('suma4(10**8)') # 3.69 segundos # >>> tiempo('suma5(10**8)') # 7.04 segundos # >>> tiempo('suma6(10**8)') # 4.23 segundos |
El código se encuentra en GitHub