Menu Close

Suma de los primeros números naturales

Definir la función

   suma :: Integer -> Integer

tal suma n es la suma de los n primeros números. Por ejemplo,

   suma 3  ==  6
   length (show (suma (10^100)))  ==  200

Soluciones en Haskell

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.

Soluciones en Python

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

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.