Menu Close

Triángulo aritmético

Los triángulos aritméticos se forman como sigue

    1
    2  3
    4  5  6
    7  8  9 10
   11 12 13 14 15
   16 17 18 19 20 21

Definir las funciones

   linea     :: Integer -> [Integer]
   triangulo :: Integer -> [[Integer]]

tales que

  • linea n es la línea n-ésima de los triángulos aritméticos. Por ejemplo,
     linea 4  ==  [7,8,9,10]
     linea 5  ==  [11,12,13,14,15]
     head (linea (10^20)) == 4999999999999999999950000000000000000001
  • triangulo n es el triángulo aritmético de altura n. Por ejemplo,
     triangulo 3  ==  [[1],[2,3],[4,5,6]]
     triangulo 4  ==  [[1],[2,3],[4,5,6],[7,8,9,10]]

Soluciones en Haskell

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.

Soluciones en Python

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.

Escribe tu solución

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