{"id":8469,"date":"2024-02-09T06:00:38","date_gmt":"2024-02-09T04:00:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8469"},"modified":"2024-02-18T20:02:04","modified_gmt":"2024-02-18T18:02:04","slug":"09-feb-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/09-feb-24\/","title":{"rendered":"Cuadrado m\u00e1s cercano"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   cuadradoCercano :: Integer -> Integer\n<\/pre>\n<p>tal que <code>cuadradoCercano n<\/code> es el n\u00famero cuadrado m\u00e1s cercano a <code>n<\/code>, donde <code>n<\/code> es un entero positivo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   cuadradoCercano 2       == 1\n   cuadradoCercano 6       == 4\n   cuadradoCercano 8       == 9\n   cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000\n<\/pre>\n<p><!--more--><\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Cuadrado_mas_cercano where\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncuadradoCercano1 :: Integer -> Integer\ncuadradoCercano1 n\n  | n - b < c - n = b\n  | otherwise     = c\n  where a = raizEntera1 n\n        b = a^2\n        c = (a+1)^2\n\n-- (raizEntera x) es el mayor entero cuyo cuadrado no es mayor que\n-- x. Por ejemplo,\n--    raizEntera 8   ==  2\n--    raizEntera 9   ==  3\n--    raizEntera 10  ==  3\nraizEntera1 :: Integer -> Integer\nraizEntera1 x =\n  last (takeWhile (\\n -> n^2 <= x) [1..])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncuadradoCercano2 :: Integer -> Integer\ncuadradoCercano2 n\n  | n - b < c - n = b\n  | otherwise     = c\n  where a = raizEntera2 n\n        b = a^2\n        c = (a+1)^2\n\nraizEntera2 :: Integer -> Integer\nraizEntera2 x = aux (1,x)\n    where aux (a,b) | d == x    = c\n                    | c == a    = c\n                    | x <= d    = aux (a,c)\n                    | otherwise = aux (c,b)\n            where c = (a+b) `div` 2\n                  d = c^2\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncuadradoCercano3 :: Integer -> Integer\ncuadradoCercano3 n\n  | n - b < c - n = b\n  | otherwise     = c\n  where a = raizEntera3 n\n        b = a^2\n        c = (a+1)^2\n\nraizEntera3 :: Integer -> Integer\nraizEntera3 0 = 0\nraizEntera3 1 = 1\nraizEntera3 n = until aceptable mejora n\n  where mejora x    = (x + n `div` x) `div` 2\n        aceptable x = x^2 <= n\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ncuadradoCercano4 :: Integer -> Integer\ncuadradoCercano4 = (^ 2) . round . sqrt . fromIntegral\n\n-- La 4\u00aa soluci\u00f3n es incorrecta. Por ejemplo,\n--    \u03bb> cuadradoCercano4 (10^46)\n--    9999999999999998322278400000000070368744177664\n--    \u03bb> cuadradoCercano3 (10^46)\n--    10000000000000000000000000000000000000000000000\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> Integer) -> Spec\nspecG cuadradoCercano = do\n  it \"e1\" $\n    cuadradoCercano 2 `shouldBe` 1\n  it \"e2\" $\n    cuadradoCercano 6 `shouldBe` 4\n  it \"e3\" $\n    cuadradoCercano 8 `shouldBe` 9\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG cuadradoCercano1\n  describe \"def. 2\" $ specG cuadradoCercano2\n  describe \"def. 3\" $ specG cuadradoCercano3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    9 examples, 0 failures\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_cuadradoCercano :: Positive Integer -> Bool\nprop_cuadradoCercano (Positive x) =\n  all (== cuadradoCercano1 x)\n      [cuadradoCercano2 x,\n       cuadradoCercano3 x]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_cuadradoCercano\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> cuadradoCercano1 (10^14)\n--    100000000000000\n--    (4.59 secs, 5,920,475,784 bytes)\n--    \u03bb> cuadradoCercano2 (10^14)\n--    100000000000000\n--    (0.01 secs, 512,472 bytes)\n--    \u03bb> cuadradoCercano3 (10^14)\n--    100000000000000\n--    (0.01 secs, 494,248 bytes)\n--\n--    \u03bb> length (show (cuadradoCercano2 (10^20000)))\n--    20001\n--    (3.94 secs, 1,446,675,504 bytes)\n--    \u03bb> length (show (cuadradoCercano3 (10^20000)))\n--    20001\n--    (4.50 secs, 926,647,904 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import count, takewhile\nfrom math import sqrt\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# raizEntera(x) es el mayor entero cuyo cuadrado no es mayor que\n# x. Por ejemplo,\n#    raizEntera(8)   ==  2\n#    raizEntera(9)   ==  3\n#    raizEntera(10)  ==  3\ndef raizEntera1(x: int) -> int:\n    return list(takewhile(lambda n: n**2 <= x, count(1)))[-1]\n\ndef cuadradoCercano1(n: int) -> int:\n    a = raizEntera1(n)\n    b = a**2\n    c = (a+1)**2\n    if n - b < c - n:\n        return b\n    return c\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef raizEntera2(x: int) -> int:\n    def aux(a: int, b: int) -> int:\n        c = (a+b) \/\/ 2\n        d = c**2\n        if d == x:\n            return c\n        if c == a:\n            return c\n        if x <= d:\n            return aux(a,c)\n        return aux(c,b)\n    return aux(1,x)\n\ndef cuadradoCercano2(n: int) -> int:\n    a = raizEntera2(n)\n    b = a**2\n    c = (a+1)**2\n    if n - b < c - n:\n        return b\n    return c\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef raizEntera3(n: int) -> int:\n    if n == 0:\n        return 0\n    if n == 1:\n        return 1\n    x = n\n    while x * x > n:\n        x = (x + n \/\/ x) \/\/ 2\n    return x\n\ndef cuadradoCercano3(n: int) -> int:\n    a = raizEntera3(n)\n    b = a**2\n    c = (a+1)**2\n    if n - b < c - n:\n        return b\n    return c\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef cuadradoCercano4(n: int) -> int:\n    return round(sqrt(n)) ** 2\n\n# La 4\u00aa soluci\u00f3n es incorrecta. Por ejemplo,\n#    >>> cuadradoCercano4(10**46)\n#    9999999999999998322278400000000070368744177664\n#    >>> cuadradoCercano3(10**46)\n#    10000000000000000000000000000000000000000000000\n\n# Verificaci\u00f3n\n# ============\n\ndef test_cuadradoCercano() -> None:\n    for cuadradoCercano in [cuadradoCercano1, cuadradoCercano2,\n                            cuadradoCercano3, cuadradoCercano4]:\n        assert cuadradoCercano(2) == 1\n        assert cuadradoCercano(6) == 4\n        assert cuadradoCercano(8) == 9\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_cuadradoCercano()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_cuadradoCercano_equiv(x: int) -> None:\n    r = cuadradoCercano1(x)\n    assert cuadradoCercano2(x) == r\n    assert cuadradoCercano3(x) == r\n    assert cuadradoCercano4(x) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_cuadradoCercano_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('cuadradoCercano1(10**14)')\n#    2.88 segundos\n#    >>> tiempo('cuadradoCercano2(10**14)')\n#    0.00 segundos\n#    >>> tiempo('cuadradoCercano3(10**14)')\n#    0.00 segundos\n#\n#    >>> tiempo('cuadradoCercano2(10**6000)')\n#    1.21 segundos\n#    >>> tiempo('cuadradoCercano3(10**6000)')\n#    2.08 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n cuadradoCercano :: Integer -> Integer tal que cuadradoCercano n es el n\u00famero cuadrado m\u00e1s cercano a n, donde n es un entero positivo. Por ejemplo, cuadradoCercano 2 == 1 cuadradoCercano 6 == 4 cuadradoCercano 8 == 9 cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8469"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8469"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8469\/revisions"}],"predecessor-version":[{"id":8470,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8469\/revisions\/8470"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8469"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8469"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8469"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}