Menu Close

Números malvados y odiosos

José A. Alonso,

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

  data MalvadoOdioso = Malvado | Odioso deriving Show

Definir la función

  malvadoOdioso :: Integer -> MalvadoOdioso

tal que (malvadoOdioso n) devuelve el tipo de número que es n. Por ejemplo,

   λ> 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

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)
Medio
, , , , , , ,

3 soluciones de “Números malvados y odiosos”

  1. Responder
    agumaragu1

    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.

    data MalvadoOdioso = Malvado | Odioso deriving Show
 
malvadoOdioso1 :: Integer -> MalvadoOdioso
malvadoOdioso1 1 = Odioso
malvadoOdioso1 n | even n  =       malvadoOdioso1 q
                 | otherwise =   (contrario.malvadoOdioso1) q
  where contrario Malvado = Odioso
        contrario Odioso = Malvado
        q = div n 2
 
malvadoOdioso3 :: Integer -> MalvadoOdioso
malvadoOdioso3 n = aux n 0
  where aux 0 ac | even ac = Malvado
                 | otherwise = Odioso
        aux x ac = aux (div x 2) (ac + rem x 2)
  2. Responder
    jaibengue 
    import Data.Bits
 
data MalvadoOdioso = Malvado | Odioso
                   deriving Show
 
malvadoOdioso :: Integer -> MalvadoOdioso
malvadoOdioso n | (popCount n) `mod` 2 == 0 = Malvado
                | otherwise                 = Odioso
  3. Responder
    carbremor 
    import Data.Bits
data MalvadoOdioso = Malvado | Odioso deriving Show
 
malvadoOdioso :: Integer -> MalvadoOdioso
malvadoOdioso n
                | even (popCount n) == True   = Malvado
                | otherwise                   = Odioso
 
-- Eficiencia
-- λ> malvadoOdioso (1+10^20000000)
-- Malvado
-- (1.22 secs, 32,473,104 bytes)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.