Huecos binarios
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
|
1 2 |
longMayorHuecoBinario :: Int -> Int graficaLongMayorHuecoBinario :: Int -> IO () |
tales que
- (longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo,
|
1 2 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
|
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 |
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]] |