{"id":2683,"date":"2016-12-12T06:00:34","date_gmt":"2016-12-12T04:00:34","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2683"},"modified":"2016-12-19T07:56:28","modified_gmt":"2016-12-19T05:56:28","slug":"mayores-que-la-mitad","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/mayores-que-la-mitad\/","title":{"rendered":"Mayores que la mitad"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mayoresMitad :: Ord a => [a] -> [a]\n<\/pre>\n<p>tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   sort (mayoresMitad [1,6,3,4])    ==  [4,6]\n   sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]\n   sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]\n   length (mayoresMitad3 [1..10^6]) ==  500000\n<\/pre>\n<p><strong>Nota<\/strong>: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort)\n\n-- 1\u00aa soluci\u00f3n:\nmayoresMitad1 :: Ord a => [a] -> [a]\nmayoresMitad1 xs =\n  [x | x <- xs\n     , length (filter (<=x) xs) > k]\n  where k = length xs `div` 2 \n\n-- 2\u00aa soluci\u00f3n\nmayoresMitad2 :: Ord a => [a] -> [a]\nmayoresMitad2 xs = aux xs\n  where aux [] = []\n        aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys\n                   | otherwise                        = aux ys\n        k = length xs `div` 2 \n\n-- 3\u00aa soluci\u00f3n\nmayoresMitad3 :: Ord a => [a] -> [a]\nmayoresMitad3 xs = drop k (sort xs)\n  where k = length xs `div` 2 \n\n-- Comprobaci\u00f3n de eficiencia\n--    \u03bb> length (mayoresMitad1 [1..4*10^3])\n--    2000\n--    (3.79 secs, 442,631,712 bytes)\n--    \u03bb> length (mayoresMitad2 [1..4*10^3])\n--    2000\n--    (11.82 secs, 1,463,762,192 bytes)\n--    \u03bb> length (mayoresMitad3 [1..4*10^3])\n--    2000\n--    (0.02 secs, 0 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n mayoresMitad :: Ord a => [a] -> [a] tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo, sort (mayoresMitad [1,6,3,4]) == [4,6] sort (mayoresMitad [1,6,3,4,7]) == [4,6,7] sort&#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":[4],"tags":[8,30,46,38,28,11,6,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2683"}],"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=2683"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2683\/revisions"}],"predecessor-version":[{"id":2713,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2683\/revisions\/2713"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2683"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2683"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2683"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}