Menu Close

Día: 26 enero, 2022

Cuadrado más cercano

Definir la función

   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,

   cuadradoCercano 2       == 1
   cuadradoCercano 6       == 4
   cuadradoCercano 8       == 9
   cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000

Soluciones

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:

9º curso de Exercitium (2021-22)

Hoy (26 de enero de 2022) comienza el noveno curso de Exercitium con los mismos objetivos

También el procedimiento es el mismo que en los cursos anteriores:

  • diariamente se propone un nuevo ejercicio,
  • en los comentarios se pueden escribir distintas soluciones
  • a los siete días de la propuesta, se publican las soluciones seleccionadas.

Tanto la publicación del enunciado como la solución se anuncian en Twitter.

En cada curso, los contenidos de los ejercicios avanzan conforme se iban introduciendo en el curso.

En la siguiente tabla se resume los cursos anteriores, donde

  • en la 1ª columna hay un enlace al diario de clase del curso de (las entradas están en orden cronológico inverso),
  • en la 2ª un enlace al primer ejercicio del curso,
  • en la 3ª un enlace al último ejercicio del curso y
  • en la 4ª el número de ejercicios propuesto en el curso.

La tabla es

Curso Desde Hasta Ejercicios
2013-14 21-abril-2014 25-julio-2014 70
2014-15 30-octubre-2014 26-junio-2015 171
2015-16 21-octubre-2015 02-junio-2016 176
2016-17 03-noviembre-2016 09-junio-2017 149
2017-18 03-noviembre-2017 12-junio-2018 151
2018-19 09-noviembre-2018 10-junio-2019 143
2019-20 11-noviembre-2019 05-junio-2020 176
2020-21 12-enero-2021 24-junio-2021 110

En la tabla anterior el último enlace a los diarios de los cursos es el de 2019-10 ya que es el último curso que impartí antes de jubilarme. Por ello, aunque mantenga la misma dinámica, el número de soluciones de los alumnos de la asignatura sea menor.