Cuadrado más cercano
Definir la función
|
1 |
cuadradoCercano :: Integer -> Integer |
tal que (cuadradoCercano n) es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,
|
1 2 3 4 |
cuadradoCercano 2 == 1 cuadradoCercano 6 == 4 cuadradoCercano 8 == 9 cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000 |
Soluciones
|
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 102 103 104 105 106 107 108 109 110 111 112 113 |
import Test.QuickCheck -- 1ª solución -- =========== cuadradoCercano1 :: Integer -> Integer cuadradoCercano1 n | n - b < c - n = b | otherwise = c where a = raizEntera1 n b = a^2 c = (a+1)^2 -- (raizEntera x) es el mayor entero cuyo cuadrado no es mayor que -- x. Por ejemplo, -- raizEntera 8 == 2 -- raizEntera 9 == 3 -- raizEntera 10 == 3 raizEntera1 :: Integer -> Integer raizEntera1 x = last (takeWhile (\n -> n^2 <= x) [1..]) -- 2ª solución -- =========== cuadradoCercano2 :: Integer -> Integer cuadradoCercano2 n | n - b < c - n = b | otherwise = c where a = raizEntera2 n b = a^2 c = (a+1)^2 raizEntera2 :: Integer -> Integer raizEntera2 x = aux (1,x) where aux (a,b) | d == x = c | c == a = c | x <= d = aux (a,c) | otherwise = aux (c,b) where c = (a+b) `div` 2 d = c^2 -- 3ª solución -- =========== cuadradoCercano3 :: Integer -> Integer cuadradoCercano3 n | n - b < c - n = b | otherwise = c where a = raizEntera3 n b = a^2 c = (a+1)^2 raizEntera3 :: Integer -> Integer raizEntera3 0 = 0 raizEntera3 1 = 1 raizEntera3 n = until aceptable mejora n where mejora x = (x + n `div` x) `div` 2 aceptable x = x^2 <= n -- 4ª solución -- =========== cuadradoCercano4 :: Integer -> Integer cuadradoCercano4 = (^ 2) . round . sqrt . fromIntegral -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_cuadradoCercano :: Positive Integer -> Bool prop_cuadradoCercano (Positive x) = all (== cuadradoCercano1 x) [cuadradoCercano2 x, cuadradoCercano3 x, cuadradoCercano4 x] -- La comprobación es -- λ> quickCheck prop_cuadradoCercano -- +++ OK, passed 100 tests. -- Aunque ha pasado los 100 tests, las definiciones no son -- equivalentes. Por ejemplo, -- λ> cuadradoCercano3 (10^46) == cuadradoCercano (10^46) -- False -- λ> cuadradoCercano3 (10^46) -- 9999999999999998322278400000000070368744177664 -- λ> cuadradoCercano (10^46) -- 10000000000000000000000000000000000000000000000 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> cuadradoCercano1 (10^14) -- 100000000000000 -- (4.59 secs, 5,920,475,784 bytes) -- λ> cuadradoCercano2 (10^14) -- 100000000000000 -- (0.01 secs, 512,472 bytes) -- λ> cuadradoCercano3 (10^14) -- 100000000000000 -- (0.01 secs, 494,248 bytes) -- λ> cuadradoCercano4 (10^14) -- 100000000000000 -- (0.01 secs, 475,152 bytes) -- -- λ> length (show (cuadradoCercano2 (10^20000))) -- 20001 -- (3.94 secs, 1,446,675,504 bytes) -- λ> length (show (cuadradoCercano3 (10^20000))) -- 20001 -- (4.50 secs, 926,647,904 bytes) |
El código se encuentra en GitHub
La elaboración de las soluciones se muestra en el siguiente vídeo: