Cuadrado más cercano

Definir la función

   cuadradoCercano :: Integer -> Integer

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,

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

cuadradoCercano 2 == 1

cuadradoCercano 6 == 4

cuadradoCercano 8 == 9

cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Cuadrado_mas_cercano where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
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

-- La 4ª solución es incorrecta. Por ejemplo,
--    λ> cuadradoCercano4 (10^46)
--    9999999999999998322278400000000070368744177664
--    λ> cuadradoCercano3 (10^46)
--    10000000000000000000000000000000000000000000000

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (Integer -> Integer) -> Spec
specG cuadradoCercano = do
  it "e1" $
    cuadradoCercano 2 `shouldBe` 1
  it "e2" $
    cuadradoCercano 6 `shouldBe` 4
  it "e3" $
    cuadradoCercano 8 `shouldBe` 9

spec :: Spec
spec = do
  describe "def. 1" $ specG cuadradoCercano1
  describe "def. 2" $ specG cuadradoCercano2
  describe "def. 3" $ specG cuadradoCercano3

-- La verificación es
--    λ> verifica
--
--    9 examples, 0 failures

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_cuadradoCercano :: Positive Integer -> Bool
prop_cuadradoCercano (Positive x) =
  all (== cuadradoCercano1 x)
      [cuadradoCercano2 x,
       cuadradoCercano3 x]

-- La comprobación es
--    λ> quickCheck prop_cuadradoCercano
--    +++ OK, passed 100 tests.

-- 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)
--
--    λ> 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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

module Cuadrado_mas_cercano where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

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

-- La 4ª solución es incorrecta. Por ejemplo,

-- λ> cuadradoCercano4 (10^46)

-- 9999999999999998322278400000000070368744177664

-- λ> cuadradoCercano3 (10^46)

-- 10000000000000000000000000000000000000000000000

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

specG :: (Integer -> Integer) -> Spec

specG cuadradoCercano = do

it "e1" $

cuadradoCercano 2 `shouldBe` 1

it "e2" $

cuadradoCercano 6 `shouldBe` 4

it "e3" $

cuadradoCercano 8 `shouldBe` 9

spec :: Spec

spec = do

describe "def. 1" $ specG cuadradoCercano1

describe "def. 2" $ specG cuadradoCercano2

describe "def. 3" $ specG cuadradoCercano3

-- La verificación es

-- λ> verifica

-- 9 examples, 0 failures

-- Equivalencia de las definiciones

-- ================================

-- La propiedad es

prop_cuadradoCercano :: Positive Integer -> Bool

prop_cuadradoCercano (Positive x) =

all (== cuadradoCercano1 x)

[cuadradoCercano2 x,

cuadradoCercano3 x]

-- La comprobación es

-- λ> quickCheck prop_cuadradoCercano

-- +++ OK, passed 100 tests.

-- 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)

-- λ> 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)

Soluciones en Python

from itertools import count, takewhile
from math import sqrt
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

# raizEntera(x) es el mayor entero cuyo cuadrado no es mayor que
# x. Por ejemplo,
#    raizEntera(8)   ==  2
#    raizEntera(9)   ==  3
#    raizEntera(10)  ==  3
def raizEntera1(x: int) -> int:
    return list(takewhile(lambda n: n**2 <= x, count(1)))[-1]

def cuadradoCercano1(n: int) -> int:
    a = raizEntera1(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 2ª solución
# ===========

def raizEntera2(x: int) -> int:
    def aux(a: int, b: int) -> int:
        c = (a+b) // 2
        d = c**2
        if d == x:
            return c
        if c == a:
            return c
        if x <= d:
            return aux(a,c)
        return aux(c,b)
    return aux(1,x)

def cuadradoCercano2(n: int) -> int:
    a = raizEntera2(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 3ª solución
# ===========

def raizEntera3(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    x = n
    while x * x > n:
        x = (x + n // x) // 2
    return x

def cuadradoCercano3(n: int) -> int:
    a = raizEntera3(n)
    b = a**2
    c = (a+1)**2
    if n - b < c - n:
        return b
    return c

# 4ª solución
# ===========

def cuadradoCercano4(n: int) -> int:
    return round(sqrt(n)) ** 2

# La 4ª solución es incorrecta. Por ejemplo,
#    >>> cuadradoCercano4(10**46)
#    9999999999999998322278400000000070368744177664
#    >>> cuadradoCercano3(10**46)
#    10000000000000000000000000000000000000000000000

# Verificación
# ============

def test_cuadradoCercano() -> None:
    for cuadradoCercano in [cuadradoCercano1, cuadradoCercano2,
                            cuadradoCercano3, cuadradoCercano4]:
        assert cuadradoCercano(2) == 1
        assert cuadradoCercano(6) == 4
        assert cuadradoCercano(8) == 9
    print("Verificado")

# La verificación es
#    >>> test_cuadradoCercano()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_cuadradoCercano_equiv(x: int) -> None:
    r = cuadradoCercano1(x)
    assert cuadradoCercano2(x) == r
    assert cuadradoCercano3(x) == r
    assert cuadradoCercano4(x) == r

# La comprobación es
#    >>> test_cuadradoCercano_equiv()
#    >>>

# 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('cuadradoCercano1(10**14)')
#    2.88 segundos
#    >>> tiempo('cuadradoCercano2(10**14)')
#    0.00 segundos
#    >>> tiempo('cuadradoCercano3(10**14)')
#    0.00 segundos
#
#    >>> tiempo('cuadradoCercano2(10**6000)')
#    1.21 segundos
#    >>> tiempo('cuadradoCercano3(10**6000)')
#    2.08 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

from itertools import count, takewhile

from math import sqrt

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

# raizEntera(x) es el mayor entero cuyo cuadrado no es mayor que

# x. Por ejemplo,

# raizEntera(8) == 2

# raizEntera(9) == 3

# raizEntera(10) == 3

def raizEntera1(x: int) -> int:

return list(takewhile(lambda n: n**2 <= x, count(1)))[-1]

def cuadradoCercano1(n: int) -> int:

a = raizEntera1(n)

b = a**2

c = (a+1)**2

if n - b < c - n:

return b

return c

# 2ª solución

# ===========

def raizEntera2(x: int) -> int:

def aux(a: int, b: int) -> int:

c = (a+b) // 2

d = c**2

if d == x:

return c

if c == a:

return c

if x <= d:

return aux(a,c)

return aux(c,b)

return aux(1,x)

def cuadradoCercano2(n: int) -> int:

a = raizEntera2(n)

b = a**2

c = (a+1)**2

if n - b < c - n:

return b

return c

# 3ª solución

# ===========

def raizEntera3(n: int) -> int:

if n == 0:

return 0

if n == 1:

return 1

x = n

while x * x > n:

x = (x + n // x) // 2

return x

def cuadradoCercano3(n: int) -> int:

a = raizEntera3(n)

b = a**2

c = (a+1)**2

if n - b < c - n:

return b

return c

# 4ª solución

# ===========

def cuadradoCercano4(n: int) -> int:

return round(sqrt(n)) ** 2

# La 4ª solución es incorrecta. Por ejemplo,

# >>> cuadradoCercano4(10**46)

# 9999999999999998322278400000000070368744177664

# >>> cuadradoCercano3(10**46)

# 10000000000000000000000000000000000000000000000

# Verificación

# ============

def test_cuadradoCercano() -> None:

for cuadradoCercano in [cuadradoCercano1, cuadradoCercano2,

cuadradoCercano3, cuadradoCercano4]:

assert cuadradoCercano(2) == 1

assert cuadradoCercano(6) == 4

assert cuadradoCercano(8) == 9

print("Verificado")

# La verificación es

# >>> test_cuadradoCercano()

# Verificado

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_cuadradoCercano_equiv(x: int) -> None:

r = cuadradoCercano1(x)

assert cuadradoCercano2(x) == r

assert cuadradoCercano3(x) == r

assert cuadradoCercano4(x) == r

# La comprobación es

# >>> test_cuadradoCercano_equiv()

# >>>

# 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('cuadradoCercano1(10**14)')

# 2.88 segundos

# >>> tiempo('cuadradoCercano2(10**14)')

# 0.00 segundos

# >>> tiempo('cuadradoCercano3(10**14)')

# 0.00 segundos

# >>> tiempo('cuadradoCercano2(10**6000)')

# 1.21 segundos

# >>> tiempo('cuadradoCercano3(10**6000)')

# 2.08 segundos

Cuadrado más cercano

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico