Exponente de la mayor potencia de x que divide a y
Definir la función
|
1 |
mayorExponente :: Integer -> Integer -> Integer |
tal que mayorExponente a b es el exponente de la mayor potencia de a que divide a b. Por ejemplo,
|
1 2 3 4 |
mayorExponente 2 8 == 3 mayorExponente 2 9 == 0 mayorExponente 5 100 == 2 mayorExponente 2 60 == 2 |
Nota: Se supone que a > 1 y b > 0.
Soluciones
A continuación se muestran las soluciones en Haskell y las 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 |
import Test.QuickCheck -- 1ª solución -- =========== mayorExponente1 :: Integer -> Integer -> Integer mayorExponente1 a b | rem b a /= 0 = 0 | otherwise = 1 + mayorExponente1 a (b `div` a) -- 2ª solución -- =========== mayorExponente2 :: Integer -> Integer -> Integer mayorExponente2 a b = aux b 0 where aux c r | rem c a /= 0 = r | otherwise = aux (c `div` a) (r + 1) -- 3ª solución -- =========== mayorExponente3 :: Integer -> Integer -> Integer mayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) /= 0] -- 4ª solución -- =========== mayorExponente4 :: Integer -> Integer -> Integer mayorExponente4 a b = fst (until (\ (_,c) -> rem c a /= 0) (\ (r,c) -> (r+1, c `div` a)) (0,b)) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_mayorExponente :: Integer -> Integer -> Property prop_mayorExponente a b = a > 1 && b > 0 ==> all (== mayorExponente1 a b) [mayorExponente2 a b, mayorExponente3 a b, mayorExponente4 a b] -- La comprobación es -- λ> quickCheck prop_mayorExponente -- +++ OK, passed 100 tests; 457 discarded. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> mayorExponente1 2 (2^(5*10^4)) -- 50000 -- (0.12 secs, 179,578,424 bytes) -- λ> mayorExponente2 2 (2^(5*10^4)) -- 50000 -- (0.13 secs, 181,533,376 bytes) -- λ> mayorExponente3 2 (2^(5*10^4)) -- 50000 -- (3.88 secs, 818,319,096 bytes) -- λ> mayorExponente4 2 (2^(5*10^4)) -- 50000 -- (0.13 secs, 181,133,344 bytes) -- -- λ> mayorExponente1 2 (2^(3*10^5)) -- 300000 -- (2.94 secs, 5,762,199,064 bytes) -- λ> mayorExponente2 2 (2^(3*10^5)) -- 300000 -- (2.91 secs, 5,773,829,624 bytes) -- λ> mayorExponente4 2 (2^(3*10^5)) -- 300000 -- (3.70 secs, 5,771,396,824 bytes) |
El código se encuentra en GitHub.
|
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 |
from itertools import islice from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Iterator from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def mayorExponente1(a: int, b: int) -> int: if b % a != 0: return 0 return 1 + mayorExponente1(a, b // a) # 2ª solución # =========== def mayorExponente2(a: int, b: int) -> int: def aux(c: int, r: int) -> int: if c % a != 0: return r return aux(c // a, r + 1) return aux(b, 0) # 3ª solución # =========== # naturales es el generador de los números naturales, Por ejemplo, # >>> list(islice(naturales(), 5)) # [0, 1, 2, 3, 4] def naturales() -> Iterator[int]: i = 0 while True: yield i i += 1 def mayorExponente3(a: int, b: int) -> int: return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0] # 4ª solución # =========== def mayorExponente4(a: int, b: int) -> int: r = 0 while b % a == 0: b = b // a r = r + 1 return r # Comprobación de equivalencia # ============================ def prueba1() -> None: for x in range(2, 11): for y in range(1, 11): print(x, y, mayorExponente4(x, y)) # La propiedad es @given(st.integers(min_value=2, max_value=10), st.integers(min_value=1, max_value=10)) def test_mayorExponente(a: int, b: int) -> None: r = mayorExponente1(a, b) assert mayorExponente2(a, b) == r assert mayorExponente3(a, b) == r assert mayorExponente4(a, b) == r # La comprobación es # src> poetry run pytest -q exponente_mayor.py # 1 passed in 0.16s # 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('mayorExponente1(2, 2**(2*10**4))') # 0.13 segundos # >>> tiempo('mayorExponente2(2, 2**(2*10**4))') # 0.13 segundos # >>> tiempo('mayorExponente3(2, 2**(2*10**4))') # 1.81 segundos # >>> tiempo('mayorExponente4(2, 2**(2*10**4))') # 0.12 segundos # # >>> tiempo('mayorExponente4(2, 2**(2*10**5))') # 12.19 segundos |
El código se encuentra en GitHub.