Números malvados y odiosos
Un número malvado es un número natural cuya expresión en base 2 (binaria) contiene un número par de unos.
Un número odioso es un número natural cuya expresión en base 2 (binaria) contiene un número impar de unos.
Podemos representar los números malvados y odiosos mediante el siguiente tipo de dato
|
1 |
data MalvadoOdioso = Malvado | Odioso deriving Show |
Definir la función
|
1 |
malvadoOdioso :: Integer -> MalvadoOdioso |
tal que (malvadoOdioso n) devuelve el tipo de número que es n. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> malvadoOdioso 11 Odioso λ> malvadoOdioso 12 Malvado λ> malvadoOdioso3 (10^20000000) Odioso λ> malvadoOdioso3 (1+10^20000000) Malvado |
Nota: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.
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 |
import Data.List (genericLength) import Data.Bits (popCount) data MalvadoOdioso = Malvado | Odioso deriving (Eq, Show) -- 1ª solución -- =========== malvadoOdioso :: Integer -> MalvadoOdioso malvadoOdioso n | (even . numeroUnosBin) n = Malvado | otherwise = Odioso -- (numeroUnosBin n) es el número de unos de la representación binaria -- del número decimal n. Por ejemplo, -- numeroUnosBin 11 == 3 -- numeroUnosBin 12 == 2 numeroUnosBin :: Integer -> Integer numeroUnosBin = genericLength . filter (/= 0) . intBin -- (intBin n) es el número binario correspondiente al número decimal n. -- Por ejemplo, -- intBin 11 == [1,1,0,1] -- intBin 12 == [0,0,1,1] intBin :: Integer -> [Integer] intBin n | n < 2 = [n] | otherwise = n `mod` 2 : intBin (n `div` 2) -- 2ª solución -- =========== malvadoOdioso2 :: Integer -> MalvadoOdioso malvadoOdioso2 n | (even . numeroIntBin) n = Malvado | otherwise = Odioso -- (numeroIntBin n) es el número de unos que contiene la representación -- binaria del número decimal n. Por ejemplo, -- numeroIntBin 11 == 3 -- numeroIntBin 12 == 2 numeroIntBin :: Integer -> Integer numeroIntBin n | n < 2 = n | otherwise = n `mod` 2 + numeroIntBin (n `div` 2) -- 3ª solución -- =========== malvadoOdioso3 :: Integer -> MalvadoOdioso malvadoOdioso3 n | (even . popCount) n = Malvado | otherwise = Odioso -- Comparación de eficiencia -- ========================= -- λ> malvadoOdioso (10^40000) -- Odioso -- (3.25 secs, 1,167,416,968 bytes) -- λ> malvadoOdioso2 (10^40000) -- Odioso -- (4.03 secs, 1,164,863,744 bytes) -- λ> malvadoOdioso3 (10^40000) -- Odioso -- (0.00 secs, 165,312 bytes) |
He llegado a dos soluciones, pero ninguna de ellas tiene eficiencia suficiente para calcular la «maldad» de números mayores a 10^200000 en un tiempo razonable.