Puntos en el círculo
En el círculo de radio 2 hay 6 puntos cuyas coordenadas son puntos naturales:
|
1 |
(0,0),(0,1),(0,2),(1,0),(1,1),(2,0) |
y en de radio 3 hay 11:
|
1 |
(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
|
1 |
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,
|
1 2 3 4 5 |
circulo 1 == 3 circulo 2 == 6 circulo 3 == 11 circulo 4 == 17 circulo 100 == 7955 |
|
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 |
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.
|
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 |
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.