Reconocimiento de potencias de 4
Definir la función
|
1 |
esPotenciaDe4 :: Integral a => a -> Bool |
tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,
|
1 2 3 4 |
esPotenciaDe4 16 == True esPotenciaDe4 17 == False esPotenciaDe4 (4^(4*10^5)) == True esPotenciaDe4 (1 + 4^(4*10^5)) == False |
1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
module Reconocimiento_de_potencias_de_4 where import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== esPotenciaDe4_1 :: Integral a => a -> Bool esPotenciaDe4_1 0 = False esPotenciaDe4_1 1 = True esPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4) -- 2ª solución -- =========== esPotenciaDe4_2 :: Integral a => a -> Bool esPotenciaDe4_2 n = n `pertenece` potenciasDe4 -- potenciassDe4 es la lista de las potencias de 4. Por ejemplo, -- take 5 potenciasDe4 == [1,4,16,64,256] potenciasDe4 :: Integral a => [a] potenciasDe4 = [4^x | x <- [0..]] -- (pertenece x ys) se verifica si x pertenece a la lista ordenada -- (posiblemente infinita xs). Por ejemplo, -- pertenece 8 [2,4..] == True -- pertenece 9 [2,4..] == False pertenece :: Integral a => a -> [a] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- 3ª solución -- =========== esPotenciaDe4_3 :: Integral a => a -> Bool esPotenciaDe4_3 n = n `pertenece` potenciasDe4_2 -- potenciassDe4 es la lista de las potencias de 4. Por ejemplo, -- take 5 potenciasDe4 == [1,4,16,64,256] potenciasDe4_2 :: Integral a => [a] potenciasDe4_2 = iterate (*4) 1 -- 4ª solución -- =========== esPotenciaDe4_4 :: Integral n => n -> Bool esPotenciaDe4_4 n = n == head (dropWhile (<n) (iterate (*4) 1)) -- 5ª solución -- =========== esPotenciaDe4_5 :: Integral n => n -> Bool esPotenciaDe4_5 n = n == until (>=n) (*4) 1 -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> Bool) -> Spec specG esPotenciaDe4 = do it "e1" $ esPotenciaDe4 16 `shouldBe` True it "e2" $ esPotenciaDe4 17 `shouldBe` False spec :: Spec spec = do describe "def. 1" $ specG esPotenciaDe4_1 describe "def. 2" $ specG esPotenciaDe4_2 describe "def. 3" $ specG esPotenciaDe4_3 describe "def. 4" $ specG esPotenciaDe4_4 describe "def. 5" $ specG esPotenciaDe4_5 -- La verificación es -- λ> verifica -- -- 10 examples, 0 failures -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esPotenciaDe4_1 (4^(4*10^4)) -- True -- (0.18 secs, 233,903,248 bytes) -- λ> esPotenciaDe4_2 (4^(4*10^4)) -- True -- (2.01 secs, 756,125,712 bytes) -- λ> esPotenciaDe4_3 (4^(4*10^4)) -- True -- (0.05 secs, 212,019,464 bytes) -- λ> esPotenciaDe4_4 (4^(4*10^4)) -- True -- (0.05 secs, 212,019,368 bytes) -- λ> esPotenciaDe4_5 (4^(4*10^4)) -- True -- (0.07 secs, 209,779,888 bytes) -- -- λ> esPotenciaDe4_3 (4^(2*10^5)) -- True -- (0.64 secs, 5,184,667,280 bytes) -- λ> esPotenciaDe4_4 (4^(2*10^5)) -- True -- (0.64 secs, 5,184,667,200 bytes) -- λ> esPotenciaDe4_5 (4^(2*10^5)) -- True -- (0.63 secs, 5,173,467,656 bytes) -- -- λ> esPotenciaDe4_3 (4^(4*10^5)) -- True -- (2.27 secs, 20,681,727,464 bytes) -- λ> esPotenciaDe4_4 (4^(4*10^5)) -- True -- (2.30 secs, 20,681,727,320 bytes) -- λ> esPotenciaDe4_5 (4^(4*10^5)) -- True -- (2.28 secs, 20,659,327,352 bytes) |
2. Soluciones en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
from itertools import count, dropwhile, islice from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Callable, Iterator setrecursionlimit(10**6) # 1ª solución # =========== def esPotenciaDe4_1(n: int) -> bool: if n == 0: return False if n == 1: return True return n % 4 == 0 and esPotenciaDe4_1(n // 4) # 2ª solución # =========== # potenciassDe4() es la lista de las potencias de 4. Por ejemplo, # >>> list(islice(potenciasDe4(), 5)) # [1, 4, 16, 64, 256] def potenciasDe4() -> Iterator[int]: return (4 ** n for n in count()) # pertenece(x, ys) se verifica si x pertenece a la lista ordenada # (posiblemente infinita xs). Por ejemplo, # >>> pertenece(8, count(2, 2)) # True # >>> pertenece(9, count(2, 2)) # False def pertenece(x: int, ys: Iterator[int]) -> bool: return next(dropwhile(lambda y: y < x, ys), None) == x def esPotenciaDe4_2(n: int) -> bool: return pertenece(n, potenciasDe4()) # 3ª solución # =========== # iterate(f, x) es el iterador obtenido aplicando f a x y continuando # aplicando f al resultado anterior. Por ejemplo, # >>> list(islice(iterate(lambda x : 4 * x, 1), 5)) # [1, 4, 16, 64, 256] def iterate(f: Callable[[int], int], x: int) -> Iterator[int]: r = x while True: yield r r = f(r) def potenciasDe4_2() -> Iterator[int]: return iterate(lambda x : 4 * x, 1) def esPotenciaDe4_3(n: int) -> bool: return pertenece(n, potenciasDe4_2()) # 4ª solución # =========== def esPotenciaDe4_4(n: int) -> bool: return next(dropwhile(lambda y: y < n, iterate(lambda x : 4 * x, 1)), None) == n # 5ª solución # =========== def esPotenciaDe4_5(n: int) -> bool: r = 1 while r < n: r = 4 * r return r == n # Verificación # ============ def test_esPotenciaDe4() -> None: for esPotenciaDe4 in [esPotenciaDe4_1, esPotenciaDe4_2, esPotenciaDe4_3, esPotenciaDe4_4, esPotenciaDe4_5]: assert esPotenciaDe4(16) assert not esPotenciaDe4(17) assert list(islice(potenciasDe4(), 5)) == [1, 4, 16, 64, 256] print("Verificado") # La verificación es # >>> test_esPotenciaDe4() # Verificado # 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('esPotenciaDe4_1(4**(2*10**4))') # 0.33 segundos # >>> tiempo('esPotenciaDe4_2(4**(2*10**4))') # 0.63 segundos # >>> tiempo('esPotenciaDe4_3(4**(2*10**4))') # 0.04 segundos # >>> tiempo('esPotenciaDe4_4(4**(2*10**4))') # 0.05 segundos # >>> tiempo('esPotenciaDe4_5(4**(2*10**4))') # 0.04 segundos # # >>> tiempo('esPotenciaDe4_3(4**(3*10**5))') # 2.29 segundos # >>> tiempo('esPotenciaDe4_4(4**(3*10**5))') # 2.28 segundos # >>> tiempo('esPotenciaDe4_5(4**(3*10**5))') # 2.31 segundos |