Menu Close

Huecos binarios

José A. Alonso,

Los huecos binarios de un número natural n son las listas de cer0 entre dos unos en la representación binaria de n. Por ejemplo, puesto que la representación binaria de 20 es 10100 tiene dos huecos binarios de longitudes 1 y 2. La longitud del mayor hueco binario de 529 es 4 ya que la representación binaria de 529 es 1000010001.

Definir las funciones

   longMayorHuecoBinario        :: Int -> Int
   graficaLongMayorHuecoBinario :: Int -> IO ()

tales que

  • (longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo, 
     longMayorHuecoBinario 20    ==  2
     longMayorHuecoBinario 529   ==  4
     longMayorHuecoBinario 2018  ==  3
  • (graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja
    Huecos_binarios_200

Soluciones

import Data.List (group)
import Graphics.Gnuplot.Simple
 
-- 1ª solución
-- ===========
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario n =
  maximum (0 : map length (huecosBinarios (decimalAbinario n)))
 
-- (decimalAbinario x) es la representación binaria del número c. Por
-- ejemplo, 
--    decimalAbinario 20   ==  [0,0,1,0,1]
--    decimalAbinario 529  ==  [1,0,0,0,1,0,0,0,0,1] 
decimalAbinario :: Int -> [Int]
decimalAbinario x
  | x < 2     = [x]
  | otherwise = x `mod` 2 : decimalAbinario (x `div` 2)
 
-- (huecosBinarios xs) es la lista de los ceros consecutivos de xs entre
-- dos elementos distintos de cero. Por ejemplo,
--    huecosBinarios [0,0,1,0,1]            ==  [[0,0],[0]]
--    huecosBinarios [1,0,0,0,1,0,0,0,0,1]  ==  [[0,0,0],[0,0,0,0]]
huecosBinarios :: [Int] -> [[Int]]
huecosBinarios xs =
  [ys | ys <- group xs, 0 `elem` ys]
 
-- 2ª solución
-- ===========
 
longMayorHuecoBinario2 :: Int -> Int
longMayorHuecoBinario2 =
  maximum . (0 :) . map length . huecosBinarios . decimalAbinario
 
-- 3ª solución
-- ===========
 
longMayorHuecoBinario3 :: Int -> Int
longMayorHuecoBinario3 = maximum . longHuecosBinarios
 
-- (longHuecosBinarios n) es la lista de las longitudes de los huecos
-- binarios de n. Por ejemplo,
--    longHuecosBinarios 20  ==  [2,1,0]
--    longHuecosBinarios 529  ==  [3,4,0]
longHuecosBinarios :: Int -> [Int]
longHuecosBinarios 1 = [0]
longHuecosBinarios n | mod n 2 == 1 = longHuecosBinarios (div n 2)
                     | mod n 4 == 2 = 1 : h : t
                     | otherwise = 1 + h : t
  where (h : t) = longHuecosBinarios (div n 2)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximum [longMayorHuecoBinario x | x <- [1..100000]]
--    16
--    (5.51 secs, 941,090,272 bytes)
--    λ> maximum [longMayorHuecoBinario2 x | x <- [1..100000]]
--    16
--    (5.54 secs, 933,093,168 bytes)
--    λ> maximum [longMayorHuecoBinario3 x | x <- [1..100000]]
--    16
--    (6.00 secs, 966,584,848 bytes)
 
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
  plotList [ Key Nothing
           , Title ("graficaLongMayorHuecoBinario " ++ show n)
           , PNG ("Huecos_binarios_" ++ show n ++ ".png")
           ]
           [longMayorHuecoBinario k | k <- [0..n-1]]
Inicial
, , , , , , ,

10 soluciones de “Huecos binarios”

  1. Responder
    angruicam1 
    import Data.List (group)
import Data.Bits (testBit, finiteBitSize, countLeadingZeros)
import Graphics.Gnuplot.Simple (plotList, Attribute (Title, Key))
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario 0 = 1
longMayorHuecoBinario n =
  maximum
  . (0:)
  . map length
  . filter (not . head)
  . group
  $ [testBit n i | i <- [0..finiteBitSize n - countLeadingZeros n - 1]]
 
-- Gráfica
-- =======
 
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
  plotList
  [Title (“graficaLongMayorHuecoBinario “ ++ show n),
   Key Nothing]
  (map longMayorHuecoBinario [0..n])
  2. Responder
    jaibengue 
    import Data.List
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario =
  maximum
  .(0:)
  .map length
  .filter (xs -> head xs == 0)
  .group
  .toBin
 
  where toBin 0 = []
        toBin n = (n `mod` 2) : toBin (n `div` 2)
  3. Responder
    albcarcas1 
    import Data.List
import Graphics.Gnuplot.Simple
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario =
  maximum . map length . filter (elem 0) . group . int2bin
 
int2bin :: Int -> [Int]
int2bin 0 = []
int2bin n = (mod n 2) : int2bin (div n 2)
 
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
  plotList [Title ("Grafica Longitud Mayor Hueco Binario " ++ show n),
            Key Nothing]
           (map longMayorHuecoBinario [0..n])
    • Responder
      José A. Alonso Publicar autor

      Falla para los números sin huecos binarios. Por ejemplo,

      λ> longMayorHuecoBinario 3
*** Exception: Prelude.maximum: empty list
      • Responder
        albcarcas1

        Es cierto, se soluciona añadiendo el 0 a la lista de longitudes para que la función maximum pueda elegirlo si el número no tiene huecos binarios.
        Muchas gracias

        longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario = maximum.(0:).map length.filter (elem 0).group.int2bin
  4. Responder
    jaiturrod 
    import Data.List
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario n =
  length (head (reverse (sort (filter (elem 0) (group (dec2bin n))))))
 
dec2bin :: Int -> [Int]
dec2bin 0 = []
dec2bin n = dec2bin (n `div` 2) ++ [n `mod` 2]
  5. Responder
    agumaragu1 
    import Graphics.Gnuplot.Simple
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario = maximum . huecos
 
huecos :: Int -> [Int]
huecos 1 = [0]
huecos n | mod n 2 == 1 = huecos (div n 2)
         | mod n 4 == 2 = 1 : h : t
         | otherwise = 1 + h : t
  where (h : t) = huecos (div n 2)
 
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
  plotList [] $ map longMayorHuecoBinario [1..n]
  6. Responder
    anadebla 
    import Data.List
import Graphics.Gnuplot.Simple
 
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario  =
  maximum . longitudes . filtraCeros . sort . group . int2bin
  where filtraCeros = filter ((x:xs) -> x == 0)
 
int2bin :: Int -> [Int]
int2bin n | n < 2     = [n]
          | otherwise = mod n 2 : int2bin (div n 2)
 
longitudes :: [[a]] -> [Int]
longitudes = map length
 
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
  plotList
  [Title ("graficaLongMayorHuecoBinario" ++ show n),
   Key Nothing]
  (map longMayorHuecoBinario [0..n])
    • Responder
      José A. Alonso Publicar autor

      Falla para los números sin huecos binarios. Por ejemplo,

      λ> longMayorHuecoBinario 3
*** Exception: Prelude.maximum: empty list
  7. Responder
    carbremor 
    import Numeric
import Data.Char
import Graphics.Gnuplot.Simple
import Test.Hspec
 
-- Añadimos (0:) para evitar errores en números, como 3 o 63.
 
longMayorHuecoBinario :: Integer -> Int
longMayorHuecoBinario  = maximum . (0:) . map length . filter ((==0).head) . group . digitos . toBin
 
graficaLongMayorHuecoBinario :: Int-> IO ()
graficaLongMayorHuecoBinario n  = plotList [] (take n mayoresHuecosBinarios)
 
toBin :: Integer -> Integer
toBin n = read (showIntAtBase 2 intToDigit n "")
 
-- λ> toBin 558745840
-- 100001010011011100100011110000
-- (0.01 secs, 117,680 bytes)
 
digitos :: Integer -> [Integer]
digitos n = [read [d] | d <- show n]
 
mayoresHuecosBinarios :: [Int]
mayoresHuecosBinarios = [longMayorHuecoBinario n | n <- [0..]]
 
-- ---------------------------------------------------------------------
-- § Verificación                                                     --
-- ---------------------------------------------------------------------
 
verifica :: IO ()
verifica = hspec $ do
describe "longMayorHuecoBinario" $ do
     it "e1" $ do 
        longMayorHuecoBinario 20 `shouldBe`
         2
     it "e2" $ do
        longMayorHuecoBinario 529 `shouldBe`
         4
     it "e3" $ do
        longMayorHuecoBinario 2018 `shouldBe`
         3
     it "e4" $ do
       longMayorHuecoBinario 3 `shouldBe`
         0
 
-- λ> verifica
-- longMayorHuecoBinario
  -- e1
  -- e2
  -- e3
  -- e4
 
Finished in 0.0026 seconds
4 examples, 0 failures

Escribe tu solución

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