Reconocimiento de potencias de 2
Definir la función
|
1 |
esPotenciaDeDos :: Integer -> Bool |
tal que (esPotenciaDeDos n) se verifica si n es una potencia de dos (suponiendo que n es mayor que 0). Por ejemplo.
|
1 2 3 4 5 6 7 |
esPotenciaDeDos 1 == True esPotenciaDeDos 2 == True esPotenciaDeDos 6 == False esPotenciaDeDos 8 == True esPotenciaDeDos 1024 == True esPotenciaDeDos 1026 == False esPotenciaDeDos (2^(10^8)) == True |
Soluciones
|
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 |
import Data.Bits ((.&.)) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== esPotenciaDeDos1 :: Integer -> Bool esPotenciaDeDos1 1 = True esPotenciaDeDos1 n | even n = esPotenciaDeDos1 (n `div` 2) | otherwise = False -- 2ª solución -- =========== esPotenciaDeDos2 :: Integer -> Bool esPotenciaDeDos2 n = n == head (dropWhile (<n) potenciasDeDos) -- potenciasDeDos es la lista de las potencias de dos. Por ejemplo, -- take 10 potenciasDeDos == [1,2,4,8,16,32,64,128,256,512] potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- 3ª solución -- =========== esPotenciaDeDos3 :: Integer -> Bool esPotenciaDeDos3 x = all (==2) (primeFactors x) -- 4ª solución -- =========== -- Usando la función (.&.) de la librería Data.Bits. Dicha función -- calcula el número correspondiente a la conjunción de las -- representaciones binarias de sus argumentos. Por ejemplo, -- 6 .&. 3 == 2 -- ya que -- la representación binaria de 6 es [1,1,0] -- la representación binaria de 3 es [1,1] -- la conjunción es [1,0] -- la representación decimal de [1,0] es 2 -- -- Otros ejemplos: -- 4 .&. 3 == [1,0,0] .&. [1,1] == 0 -- 8 .&. 7 == [1,0,0,0] .&. [1,1,1] = 0 esPotenciaDeDos4 :: Integer -> Bool esPotenciaDeDos4 n = n .&. (n-1) == 0 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_esPotenciaDeDos :: Positive Integer -> Bool prop_esPotenciaDeDos (Positive n) = all (== esPotenciaDeDos1 n) [ esPotenciaDeDos2 n , esPotenciaDeDos3 n , esPotenciaDeDos4 n ] -- La comprobación es -- λ> quickCheck prop_esPotenciaDeDos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esPotenciaDeDos1 (2^(3*10^5)) -- True -- (3.51 secs, 5,730,072,544 bytes) -- λ> esPotenciaDeDos2 (2^(3*10^5)) -- True -- (3.12 secs, 5,755,639,952 bytes) -- λ> esPotenciaDeDos3 (2^(3*10^5)) -- True -- (2.92 secs, 5,758,872,040 bytes) -- λ> esPotenciaDeDos4 (2^(3*10^5)) -- True -- (0.03 secs, 715,152 bytes) |
El código se encuentra en GitHub.