Huecos binarios

PorJosé A. Alonso 7-febrero-201814-febrero-2018

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 ()

1 2	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

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

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

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

10 Comentarios

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])

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])

Responder

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)

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)

Responder

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])

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 dice:

7-febrero-2018 a las 19:46

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

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

1
2

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

Responder
1. albcarcas1 dice:
  
  8-febrero-2018 a las 14:30
  
  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
  
  Haskell
  
  longMayorHuecoBinario :: Int -> Int longMayorHuecoBinario = maximum.(0:).map length.filter (elem 0).group.int2bin
  
  1
  2
  
  longMayorHuecoBinario :: Int -> Int
  longMayorHuecoBinario = maximum.(0:).map length.filter (elem 0).group.int2bin
  
  Responder

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]

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]

Responder

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]

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]

Responder

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])

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 dice:

12-febrero-2018 a las 08:21

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

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

1
2

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

Responder

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

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`

it "e2" $ do

longMayorHuecoBinario 529 `shouldBe`

it "e3" $ do

longMayorHuecoBinario 2018 `shouldBe`

it "e4" $ do

longMayorHuecoBinario 3 `shouldBe`

-- λ> verifica

-- longMayorHuecoBinario

-- e1

-- e2

-- e3

-- e4

Finished in 0.0026 seconds

4 examples, 0 failures

Responder

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico