Menu Close

Día: 11 octubre, 2022

Puntos en el círculo

En el círculo de radio 2 hay 6 puntos cuyas coordenadas son puntos naturales:

   (0,0),(0,1),(0,2),(1,0),(1,1),(2,0)

y en de radio 3 hay 11:

   (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)

Definir la función

   circulo :: Int -> Int

tal que circulo n es el la cantidad de pares de números naturales (x,y) que se encuentran en el círculo de radio n. Por ejemplo,

   circulo 1    ==  3
   circulo 2    ==  6
   circulo 3    ==  11
   circulo 4    ==  17
   circulo 100  ==  7955


Soluciones en Haskell

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
circulo1 :: Int -> Int
circulo1 n = length (enCirculo1 n)
 
enCirculo1 :: Int -> [(Int, Int)]
enCirculo1 n = [(x,y) | x <- [0..n],
                        y <- [0..n],
                        x*x+y*y <= n*n]
 
-- 2ª solución
-- ===========
 
circulo2 :: Int -> Int
circulo2 0 = 1
circulo2 n =
  2 * length (enSemiCirculo n) + ceiling(fromIntegral n / sqrt 2)
 
enSemiCirculo :: Int -> [(Int, Int)]
enSemiCirculo n =
  [(x,y) | x <- [0..floor (sqrt (fromIntegral (n * n)))],
           y <- [x+1..truncate (sqrt (fromIntegral (n*n - x*x)))]]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_circulo :: Positive Int -> Bool
prop_circulo (Positive n) =
  circulo1 n == circulo2 n
 
-- La comprobación es
--    λ> quickCheck prop_circulo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> circulo1 (2*10^3)
--    3143587
--    (3.58 secs, 1,744,162,600 bytes)
--    λ> circulo2 (2*10^3)
--    3143587
--    (0.41 secs, 266,374,208 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from math import sqrt, trunc, ceil
from timeit import Timer, default_timer
 
from hypothesis import given
from hypothesis import strategies as st
 
# 1ª solución
# ===========
 
def circulo1(n: int) -> int:
    return len([(x, y)
                for x in range(0, n + 1)
                for y in range(0, n + 1)
                if x * x + y * y <= n * n])
 
# 2ª solución
# ===========
 
def enSemiCirculo(n: int) -> list[tuple[int, int]]:
    return [(x, y)
            for x in range(0, ceil(sqrt(n**2)) + 1)
            for y in range(x+1, trunc(sqrt(n**2 - x**2)) + 1)]
 
def circulo2(n: int) -> int:
    if n == 0:
        return 1
    return (2 * len(enSemiCirculo(n)) + ceil(n / sqrt(2)))
 
# 3ª solución
# ===========
 
def circulo3(n: int) -> int:
    r = 0
    for x in range(0, n + 1):
        for y in range(0, n + 1):
            if x**2 + y**2 <= n**2:
                r = r + 1
    return r
 
# 4ª solución
# ===========
 
def circulo4(n: int) -> int:
    r = 0
    for x in range(0, ceil(sqrt(n**2)) + 1):
        for y in range(x + 1, trunc(sqrt(n**2 - x**2)) + 1):
            if x**2 + y**2 <= n**2:
                r = r + 1
    return 2 * r + ceil(n / sqrt(2))
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=1, max_value=100))
def test_circulo(n: int) -> None:
    r = circulo1(n)
    assert circulo2(n) == r
    assert circulo3(n) == r
    assert circulo4(n) == r
 
# La comprobación es
#    src> poetry run pytest -q puntos_dentro_del_circulo.py
#    1 passed in 0.60s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """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('circulo1(2000)')
#    0.71 segundos
#    >>> tiempo('circulo2(2000)')
#    0.76 segundos
#    >>> tiempo('circulo3(2000)')
#    2.63 segundos
#    >>> tiempo('circulo4(2000)')
#    1.06 segundos

El código se encuentra en GitHub.