{"id":8514,"date":"2024-03-14T06:00:25","date_gmt":"2024-03-14T04:00:25","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8514"},"modified":"2024-03-17T19:14:14","modified_gmt":"2024-03-17T17:14:14","slug":"14-mar-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/14-mar-24\/","title":{"rendered":"Reconocimiento de potencias de 4"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   esPotenciaDe4 :: Integral a => a -> Bool\n<\/pre>\n<p>tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   esPotenciaDe4 16                ==  True\n   esPotenciaDe4 17                ==  False\n   esPotenciaDe4 (4^(4*10^5))      ==  True\n   esPotenciaDe4 (1 + 4^(4*10^5))  ==  False\n<\/pre>\n<p><!--more--><\/p>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Reconocimiento_de_potencias_de_4 where\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_1 :: Integral a => a -> Bool\nesPotenciaDe4_1 0 = False\nesPotenciaDe4_1 1 = True\nesPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_2 :: Integral a => a -> Bool\nesPotenciaDe4_2 n = n `pertenece` potenciasDe4\n\n-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,\n--    take 5 potenciasDe4  ==  [1,4,16,64,256]\npotenciasDe4 :: Integral a => [a]\npotenciasDe4 = [4^x | x <- [0..]]\n\n-- (pertenece x ys) se verifica si x pertenece a la lista ordenada\n-- (posiblemente infinita xs). Por ejemplo,\n--    pertenece 8 [2,4..]  ==  True\n--    pertenece 9 [2,4..]  ==  False\npertenece :: Integral a => a -> [a] -> Bool\npertenece x ys = x == head (dropWhile (<x) ys)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_3 :: Integral a => a -> Bool\nesPotenciaDe4_3 n = n `pertenece` potenciasDe4_2\n\n-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,\n--    take 5 potenciasDe4  ==  [1,4,16,64,256]\npotenciasDe4_2 :: Integral a => [a]\npotenciasDe4_2 = iterate (*4) 1\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_4 :: Integral n => n -> Bool\nesPotenciaDe4_4 n =\n  n == head (dropWhile (<n) (iterate (*4) 1))\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_5 :: Integral n => n -> Bool\nesPotenciaDe4_5 n =\n  n == until (>=n) (*4) 1\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> Bool) -> Spec\nspecG esPotenciaDe4 = do\n  it \"e1\" $\n    esPotenciaDe4 16 `shouldBe` True\n  it \"e2\" $\n    esPotenciaDe4 17 `shouldBe` False\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG esPotenciaDe4_1\n  describe \"def. 2\" $ specG esPotenciaDe4_2\n  describe \"def. 3\" $ specG esPotenciaDe4_3\n  describe \"def. 4\" $ specG esPotenciaDe4_4\n  describe \"def. 5\" $ specG esPotenciaDe4_5\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    10 examples, 0 failures\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esPotenciaDe4_1 (4^(4*10^4))\n--    True\n--    (0.18 secs, 233,903,248 bytes)\n--    \u03bb> esPotenciaDe4_2 (4^(4*10^4))\n--    True\n--    (2.01 secs, 756,125,712 bytes)\n--    \u03bb> esPotenciaDe4_3 (4^(4*10^4))\n--    True\n--    (0.05 secs, 212,019,464 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(4*10^4))\n--    True\n--    (0.05 secs, 212,019,368 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(4*10^4))\n--    True\n--    (0.07 secs, 209,779,888 bytes)\n--\n--    \u03bb> esPotenciaDe4_3 (4^(2*10^5))\n--    True\n--    (0.64 secs, 5,184,667,280 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(2*10^5))\n--    True\n--    (0.64 secs, 5,184,667,200 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(2*10^5))\n--    True\n--    (0.63 secs, 5,173,467,656 bytes)\n--\n--    \u03bb> esPotenciaDe4_3 (4^(4*10^5))\n--    True\n--    (2.27 secs, 20,681,727,464 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(4*10^5))\n--    True\n--    (2.30 secs, 20,681,727,320 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(4*10^5))\n--    True\n--    (2.28 secs, 20,659,327,352 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom itertools import count, dropwhile, islice\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Callable, Iterator\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_1(n: int) -> bool:\n    if n == 0:\n        return False\n    if n == 1:\n        return True\n    return n % 4 == 0 and esPotenciaDe4_1(n \/\/ 4)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# potenciassDe4() es la lista de las potencias de 4. Por ejemplo,\n#    >>> list(islice(potenciasDe4(), 5))\n#    [1, 4, 16, 64, 256]\ndef potenciasDe4() -> Iterator[int]:\n    return (4 ** n for n in count())\n\n# pertenece(x, ys) se verifica si x pertenece a la lista ordenada\n# (posiblemente infinita xs). Por ejemplo,\n#    >>> pertenece(8, count(2, 2))\n#    True\n#    >>> pertenece(9, count(2, 2))\n#    False\ndef pertenece(x: int, ys: Iterator[int]) -> bool:\n    return next(dropwhile(lambda y: y < x, ys), None) == x\n\ndef esPotenciaDe4_2(n: int) -> bool:\n    return pertenece(n, potenciasDe4())\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# iterate(f, x) es el iterador obtenido aplicando f a x y continuando\n# aplicando f al resultado anterior. Por ejemplo,\n#    >>> list(islice(iterate(lambda x : 4 * x, 1), 5))\n#    [1, 4, 16, 64, 256]\ndef iterate(f: Callable[[int], int], x: int) -> Iterator[int]:\n    r = x\n    while True:\n        yield r\n        r = f(r)\n\ndef potenciasDe4_2() -> Iterator[int]:\n    return iterate(lambda x : 4 * x, 1)\n\ndef esPotenciaDe4_3(n: int) -> bool:\n    return pertenece(n, potenciasDe4_2())\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_4(n: int) -> bool:\n    return next(dropwhile(lambda y: y < n,\n                          iterate(lambda x : 4 * x, 1)),\n                          None) == n\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_5(n: int) -> bool:\n    r = 1\n    while r < n:\n        r = 4 * r\n    return r == n\n\n# Verificaci\u00f3n\n# ============\n\ndef test_esPotenciaDe4() -> None:\n    for esPotenciaDe4 in [esPotenciaDe4_1, esPotenciaDe4_2,\n                          esPotenciaDe4_3, esPotenciaDe4_4,\n                          esPotenciaDe4_5]:\n        assert esPotenciaDe4(16)\n        assert not esPotenciaDe4(17)\n    assert list(islice(potenciasDe4(), 5)) == [1, 4, 16, 64, 256]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_esPotenciaDe4()\n#    Verificado\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('esPotenciaDe4_1(4**(2*10**4))')\n#    0.33 segundos\n#    >>> tiempo('esPotenciaDe4_2(4**(2*10**4))')\n#    0.63 segundos\n#    >>> tiempo('esPotenciaDe4_3(4**(2*10**4))')\n#    0.04 segundos\n#    >>> tiempo('esPotenciaDe4_4(4**(2*10**4))')\n#    0.05 segundos\n#    >>> tiempo('esPotenciaDe4_5(4**(2*10**4))')\n#    0.04 segundos\n#\n#    >>> tiempo('esPotenciaDe4_3(4**(3*10**5))')\n#    2.29 segundos\n#    >>> tiempo('esPotenciaDe4_4(4**(3*10**5))')\n#    2.28 segundos\n#    >>> tiempo('esPotenciaDe4_5(4**(3*10**5))')\n#    2.31 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n esPotenciaDe4 :: Integral a => a -> Bool tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo, esPotenciaDe4 16 == True esPotenciaDe4 17 == False esPotenciaDe4 (4^(4*10^5)) == True esPotenciaDe4 (1 + 4^(4*10^5)) == False<\/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\/8514"}],"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=8514"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8514\/revisions"}],"predecessor-version":[{"id":8515,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8514\/revisions\/8515"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}