{"id":3705,"date":"2018-02-07T06:00:09","date_gmt":"2018-02-07T04:00:09","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3705"},"modified":"2018-02-14T08:14:54","modified_gmt":"2018-02-14T06:14:54","slug":"huecos-binarios","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/huecos-binarios\/","title":{"rendered":"Huecos binarios"},"content":{"rendered":"<p>Los huecos binarios de un n\u00famero natural n son las listas de cer0 entre dos unos en la representaci\u00f3n binaria de n. Por ejemplo, puesto que la representaci\u00f3n 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\u00f3n binaria de 529 es 1000010001.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   longMayorHuecoBinario        :: Int -> Int\n   graficaLongMayorHuecoBinario :: Int -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     longMayorHuecoBinario 20    ==  2\n     longMayorHuecoBinario 529   ==  4\n     longMayorHuecoBinario 2018  ==  3\n<\/pre>\n<ul>\n<li>(graficaLongMayorHuecoBinario n) dibuja la gr\u00e1fica de las longitudes de los mayores huecos binarios de los n primeros n\u00fameros naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png?resize=640%2C480\" alt=\"Huecos_binarios_200\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-3706\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png?w=640&amp;ssl=1 640w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png?resize=300%2C225&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png?resize=100%2C75&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2018\/02\/Huecos_binarios_200.png?resize=150%2C112&amp;ssl=1 150w\" sizes=\"(max-width: 640px) 100vw, 640px\" data-recalc-dims=\"1\" \/><\/a><\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group)\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nlongMayorHuecoBinario :: Int -> Int\nlongMayorHuecoBinario n =\n  maximum (0 : map length (huecosBinarios (decimalAbinario n)))\n\n-- (decimalAbinario x) es la representaci\u00f3n binaria del n\u00famero c. Por\n-- ejemplo, \n--    decimalAbinario 20   ==  [0,0,1,0,1]\n--    decimalAbinario 529  ==  [1,0,0,0,1,0,0,0,0,1] \ndecimalAbinario :: Int -> [Int]\ndecimalAbinario x\n  | x < 2     = [x]\n  | otherwise = x `mod` 2 : decimalAbinario (x `div` 2)\n\n-- (huecosBinarios xs) es la lista de los ceros consecutivos de xs entre\n-- dos elementos distintos de cero. Por ejemplo,\n--    huecosBinarios [0,0,1,0,1]            ==  [[0,0],[0]]\n--    huecosBinarios [1,0,0,0,1,0,0,0,0,1]  ==  [[0,0,0],[0,0,0,0]]\nhuecosBinarios :: [Int] -> [[Int]]\nhuecosBinarios xs =\n  [ys | ys <- group xs, 0 `elem` ys]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nlongMayorHuecoBinario2 :: Int -> Int\nlongMayorHuecoBinario2 =\n  maximum . (0 :) . map length . huecosBinarios . decimalAbinario\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nlongMayorHuecoBinario3 :: Int -> Int\nlongMayorHuecoBinario3 = maximum . longHuecosBinarios\n\n-- (longHuecosBinarios n) es la lista de las longitudes de los huecos\n-- binarios de n. Por ejemplo,\n--    longHuecosBinarios 20  ==  [2,1,0]\n--    longHuecosBinarios 529  ==  [3,4,0]\nlongHuecosBinarios :: Int -> [Int]\nlongHuecosBinarios 1 = [0]\nlongHuecosBinarios n | mod n 2 == 1 = longHuecosBinarios (div n 2)\n                     | mod n 4 == 2 = 1 : h : t\n                     | otherwise = 1 + h : t\n  where (h : t) = longHuecosBinarios (div n 2)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum [longMayorHuecoBinario x | x <- [1..100000]]\n--    16\n--    (5.51 secs, 941,090,272 bytes)\n--    \u03bb> maximum [longMayorHuecoBinario2 x | x <- [1..100000]]\n--    16\n--    (5.54 secs, 933,093,168 bytes)\n--    \u03bb> maximum [longMayorHuecoBinario3 x | x <- [1..100000]]\n--    16\n--    (6.00 secs, 966,584,848 bytes)\n\ngraficaLongMayorHuecoBinario :: Int -> IO ()\ngraficaLongMayorHuecoBinario n =\n  plotList [ Key Nothing\n           , Title (\"graficaLongMayorHuecoBinario \" ++ show n)\n           , PNG (\"Huecos_binarios_\" ++ show n ++ \".png\")\n           ]\n           [longMayorHuecoBinario k | k <- [0..n-1]]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Los huecos binarios de un n\u00famero natural n son las listas de cer0 entre dos unos en la representaci\u00f3n binaria de n. Por ejemplo, puesto que la representaci\u00f3n 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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[376,13,28,10,15,11,309,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3705"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=3705"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3705\/revisions"}],"predecessor-version":[{"id":3750,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3705\/revisions\/3750"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3705"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3705"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3705"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}