{"id":8341,"date":"2023-11-24T06:00:22","date_gmt":"2023-11-24T04:00:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8341"},"modified":"2024-05-17T18:42:55","modified_gmt":"2024-05-17T16:42:55","slug":"24-nov-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-nov-23\/","title":{"rendered":"Ra\u00edces enteras"},"content":{"rendered":"\n

Definir la funci\u00f3n<\/p>\n

\n   raizEnt :: Integer -> Integer -> Integer\n<\/pre>\n
tal que raizEnt x n<\/code> es la ra\u00edz entera n<\/code>-\u00e9sima de x<\/code>; es decir, el mayor n\u00famero entero y<\/code> tal que \(y^n \\leq x\). Por ejemplo,<\/p>\n
\n   raizEnt  8 3      ==  2\n   raizEnt  9 3      ==  2\n   raizEnt 26 3      ==  2\n   raizEnt 27 3      ==  3\n   raizEnt (10^50) 2 ==  10000000000000000000000000\n<\/pre>\n
Comprobar con QuickCheck que para todo n\u00famero natural n,<\/p>\n
\n    raizEnt (10^(2*n)) 2 == 10^n\n<\/pre>\n
<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Raices_enteras where\n\nimport Test.Hspec (Spec, hspec, it, shouldBe)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nraizEnt1 :: Integer -> Integer -> Integer\nraizEnt1 x n =\n  last (takeWhile (\\y -> y^n <= x) [0..])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nraizEnt2 :: Integer -> Integer -> Integer\nraizEnt2 x n =\n  floor ((fromIntegral x)**(1 \/ fromIntegral n))\n\n-- Nota. La soluci\u00f3n anterior falla para n\u00fameros grandes. Por ejemplo,\n--    \u03bb> raizEnt2 (10^50) 2 == 10^25\n--    False\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nraizEnt3 :: Integer -> Integer -> Integer\nraizEnt3 x n = aux (1,x)\n  where aux (a,b) | d == x    = c\n                  | c == a    = c\n                  | d < x     = aux (c,b)\n                  | otherwise = aux (a,c)\n          where c = (a+b) `div` 2\n                d = c^n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> raizEnt1 (10^14) 2\n--    10000000\n--    (6.15 secs, 6,539,367,976 bytes)\n--    \u03bb> raizEnt2 (10^14) 2\n--    10000000\n--    (0.00 secs, 0 bytes)\n--    \u03bb> raizEnt3 (10^14) 2\n--    10000000\n--    (0.00 secs, 25,871,944 bytes)\n--\n--    \u03bb> raizEnt2 (10^50) 2\n--    9999999999999998758486016\n--    (0.00 secs, 0 bytes)\n--    \u03bb> raizEnt3 (10^50) 2\n--    10000000000000000000000000\n--    (0.00 secs, 0 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_raizEnt :: Integer -> Bool\nprop_raizEnt n =\n  raizEnt3 (10^(2*m)) 2 == 10^m\n  where m = abs n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_raizEnt\n--    +++ OK, passed 100 tests.\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    raizEnt1  8 3 `shouldBe` 2\n  it \"e2\" $\n    raizEnt1  9 3 `shouldBe` 2\n  it \"e3\" $\n    raizEnt1 26 3 `shouldBe` 2\n  it \"e4\" $\n    raizEnt1 27 3 `shouldBe` 3\n  it \"e5\" $\n    raizEnt2  8 3 `shouldBe` 2\n  it \"e6\" $\n    raizEnt2  9 3 `shouldBe` 2\n  it \"e7\" $\n    raizEnt2 26 3 `shouldBe` 2\n  it \"e8\" $\n    raizEnt2 27 3 `shouldBe` 3\n  it \"e9\" $\n    raizEnt3  8 3 `shouldBe` 2\n  it \"e10\" $\n    raizEnt3  9 3 `shouldBe` 2\n  it \"e11\" $\n    raizEnt3 26 3 `shouldBe` 2\n  it \"e12\" $\n    raizEnt3 27 3 `shouldBe` 3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--    e5\n--    e6\n--    e7\n--    e8\n--    e9\n--    e10\n--    e11\n--    e12\n--\n--    Finished in 0.0007 seconds\n--    12 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom itertools import count, takewhile\nfrom math import floor\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\ndef raizEnt(x: int, n: int) -> int:\n    return list(takewhile(lambda y : y ** n <= x, count(0)))[-1]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef raizEnt2(x: int, n: int) -> int:\n    return floor(x ** (1 \/ n))\n\n# Nota. La soluci\u00f3n anterior falla para n\u00fameros grandes. Por ejemplo,\n#    >>> raizEnt2(10**50, 2) == 10 **25\n#    False\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef raizEnt3(x: int, n: int) -> int:\n    def aux(a: int, b: int) -> int:\n        c = (a + b) \/\/ 2\n        d = c ** n\n        if d == x:\n            return c\n        if c == a:\n            return c\n        if d < x:\n            return aux(c, b)\n        return aux(a, c)\n    return aux(1, x)\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('raizEnt(10**14, 2)')\n#    2.71 segundos\n#    >>> tiempo('raizEnt2(10**14, 2)')\n#    0.00 segundos\n#    >>> tiempo('raizEnt3(10**14, 2)')\n#    0.00 segundos\n#\n#    >>> raizEnt2(10**50, 2)\n#    10000000000000000905969664\n#    >>> raizEnt3(10**50, 2)\n#    10000000000000000000000000\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=1000))\ndef test_raizEntP(n: int) -> None:\n    assert raizEnt3(10**(2*n), 2) == 10**n\n\n# La comprobaci\u00f3n es\n#    >>> test_raizEnt)()\n#    >>>\n\n# Verificaci\u00f3n\n# ============\n\ndef test_raizEnt() -> None:\n    assert raizEnt(8, 3) == 2\n    assert raizEnt(9, 3) == 2\n    assert raizEnt(26, 3) == 2\n    assert raizEnt(27, 3) == 3\n    assert raizEnt2(8, 3) == 2\n    assert raizEnt2(9, 3) == 2\n    assert raizEnt2(26, 3) == 2\n    assert raizEnt2(27, 3) == 3\n    assert raizEnt3(8, 3) == 2\n    assert raizEnt3(9, 3) == 2\n    assert raizEnt3(26, 3) == 2\n    assert raizEnt3(27, 3) == 3\n    print(\"Verificado\")\n\n# La comprobaci\u00f3n es\n#    >>> test_raizEnt()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n raizEnt :: Integer -> Integer -> Integer tal que raizEnt x n es la ra\u00edz entera n-\u00e9sima de x; es decir, el mayor n\u00famero entero y tal que \(y^n \\leq x\). Por ejemplo, raizEnt 8 3 == 2 raizEnt 9 3 == 2 raizEnt 26 3 == 2 raizEnt 27 3 ==…<\/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\/8341"}],"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=8341"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8341\/revisions"}],"predecessor-version":[{"id":8571,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8341\/revisions\/8571"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8341"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8341"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8341"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}