Suma de los cuadrados de los primeros números naturales
Definir la función
|
1 |
sumaDeCuadrados :: Integer -> Integer |
tal que sumaDeCuadrados n es la suma de los cuadrados de los primeros n números; es decir, 1² + 2² + … + n². Por ejemplo,
|
1 2 3 |
sumaDeCuadrados 3 == 14 sumaDeCuadrados 100 == 338350 length (show (sumaDeCuadrados (10^100))) == 300 |
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 -- =========== sumaDeCuadrados1 :: Integer -> Integer sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]] -- 2ª solución -- =========== sumaDeCuadrados2 :: Integer -> Integer sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6 -- 3ª solución -- =========== sumaDeCuadrados3 :: Integer -> Integer sumaDeCuadrados3 1 = 1 sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1) -- 4ª solución -- =========== sumaDeCuadrados4 :: Integer -> Integer sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n]) -- 5ª solución -- =========== sumaDeCuadrados5 :: Integer -> Integer sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n]) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sumaDeCuadrados :: Positive Integer -> Bool prop_sumaDeCuadrados (Positive n) = all (== sumaDeCuadrados1 n) [sumaDeCuadrados2 n, sumaDeCuadrados3 n, sumaDeCuadrados4 n, sumaDeCuadrados5 n] -- La comprobación es -- λ> quickCheck prop_sumaDeCuadrados -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaDeCuadrados1 (2*10^6) -- 2666668666667000000 -- (1.90 secs, 1,395,835,576 bytes) -- λ> sumaDeCuadrados2 (2*10^6) -- 2666668666667000000 -- (0.01 secs, 563,168 bytes) -- λ> sumaDeCuadrados3 (2*10^6) -- 2666668666667000000 -- (2.37 secs, 1,414,199,400 bytes) -- λ> sumaDeCuadrados4 (2*10^6) -- 2666668666667000000 -- (1.33 secs, 1,315,836,128 bytes) -- λ> sumaDeCuadrados5 (2*10^6) -- 2666668666667000000 -- (0.71 secs, 1,168,563,384 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 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**6) # 1ª solución # =========== def sumaDeCuadrados1(n: int) -> int: return sum(x**2 for x in range(1, n + 1)) # 2ª solución # =========== def sumaDeCuadrados2(n: int) -> int: return n * (n + 1) * (2 * n + 1) // 6 # 3ª solución # =========== def sumaDeCuadrados3(n: int) -> int: if n == 1: return 1 return n**2 + sumaDeCuadrados3(n - 1) # 4ª solución # =========== def sumaDeCuadrados4(n: int) -> int: return reduce(add, (x**2 for x in range(1, n + 1))) # 5ª solución # =========== def sumaDeCuadrados5(n: int) -> int: x, r = 1, 0 while x <= n: r = r + x**2 x = x + 1 return r # 6ª solución # =========== def sumaDeCuadrados6(n: int) -> int: r = 0 for x in range(1, n + 1): r = r + x**2 return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_sumaDeCuadrados(n): r = sumaDeCuadrados1(n) assert sumaDeCuadrados2(n) == r assert sumaDeCuadrados3(n) == r assert sumaDeCuadrados4(n) == r assert sumaDeCuadrados5(n) == r assert sumaDeCuadrados6(n) == r # La comprobación es # src> poetry run pytest -q suma_de_los_cuadrados_de_los_primeros_numeros_naturales.py # 1 passed in 0.19s # 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('sumaDeCuadrados1(20000)') # 0.01 segundos # >>> tiempo('sumaDeCuadrados2(20000)') # 0.00 segundos # >>> tiempo('sumaDeCuadrados3(20000)') # 0.02 segundos # >>> tiempo('sumaDeCuadrados4(20000)') # 0.02 segundos # >>> tiempo('sumaDeCuadrados5(20000)') # 0.02 segundos # >>> tiempo('sumaDeCuadrados6(20000)') # 0.02 segundos # # >>> tiempo('sumaDeCuadrados1(10**7)') # 2.19 segundos # >>> tiempo('sumaDeCuadrados2(10**7)') # 0.00 segundos # >>> tiempo('sumaDeCuadrados4(10**7)') # 2.48 segundos # >>> tiempo('sumaDeCuadrados5(10**7)') # 2.53 segundos # >>> tiempo('sumaDeCuadrados6(10**7)') # 2.22 segundos |
El código se encuentra en GitHub.