{"id":6130,"date":"2021-03-08T06:00:31","date_gmt":"2021-03-08T04:00:31","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6130"},"modified":"2021-03-15T09:52:50","modified_gmt":"2021-03-15T07:52:50","slug":"sumas-parciales","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/sumas-parciales\/","title":{"rendered":"Sumas parciales"},"content":{"rendered":"

Los sufijos de la lista [3,7,2,5,4,6] son<\/p>\n

\n   [3,7,2,5,4,6]\n     [7,2,5,4,6]\n       [2,5,4,6]\n         [5,4,6]\n           [4,6]\n             [6]\n              []\n<\/pre>\n
y la lista de sus sumas es [27,24,17,15,10,6,0].<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n   sumasParciales :: [Integer] -> [Integer]\n   <\/pre>\n
tal que (sumasParciales xs) es la lista de las sumas de los sufijos de xs. Por ejemplo,<\/p>\n
\n   sumasParciales [3,7,2,5,4,6]  ==  [27,24,17,15,10,6,0]\n   sumasParciales [1..10]        ==  [55,54,52,49,45,40,34,27,19,10,0]\n   sum (sumasParciales [1..5*10^6])  ==  41666679166667500000\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (tails)\n\n-- 1\u00aa soluci\u00f3n\nsumasParciales1 :: [Integer] -> [Integer]\nsumasParciales1 xs = map sum (tails xs)\n\n-- 2\u00aa soluci\u00f3n\nsumasParciales2 :: [Integer] -> [Integer]\nsumasParciales2 []     = [0]\nsumasParciales2 (x:xs) = (x + s):s:ss\n  where (s:ss) = sumasParciales2 xs\n\n-- 3\u00aa soluci\u00f3n\nsumasParciales3 :: [Integer] -> [Integer]\nsumasParciales3 = foldr (\\x (s:ss) -> (x + s) : (s:ss)) [0]\n\n-- 4\u00aa soluci\u00f3n\nsumasParciales4 :: [Integer] -> [Integer]\nsumasParciales4 xs = scanl (-) (sum xs) xs\n\n-- 5\u00aa soluci\u00f3n\nsumasParciales5 :: [Integer] -> [Integer]\nsumasParciales5 xs = reverse (0 : scanl1 (+) (reverse xs))\n\n-- 6\u00aa soluci\u00f3n\nsumasParciales6 :: [Integer] -> [Integer]\nsumasParciales6 = scanr (+) 0\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sum (sumasParciales1 [1..3*10^4])\n--    9000450005000\n--    (19.70 secs, 40,132,872,616 bytes)\n--    \u03bb> sum (sumasParciales2 [1..3*10^4])\n--    9000450005000\n--    (0.04 secs, 16,932,840 bytes)\n--    \u03bb> sum (sumasParciales3 [1..3*10^4])\n--    9000450005000\n--    (0.02 secs, 13,880,608 bytes)\n--    \u03bb> sum (sumasParciales4 [1..3*10^4])\n--    9000450005000\n--    (0.03 secs, 12,178,080 bytes)\n--    \u03bb> sum (sumasParciales5 [1..3*10^4])\n--    9000450005000\n--    (0.02 secs, 9,974,600 bytes)\n--    \u03bb> sum (sumasParciales6 [1..3*10^4])\n--    9000450005000\n--    (0.02 secs, 10,694,368 bytes)\n--\n--    \u03bb> sum (sumasParciales2 [1..3*10^6])\n--    9000004500000500000\n--    (3.13 secs, 1,685,139,696 bytes)\n--    \u03bb> sum (sumasParciales3 [1..3*10^6])\n--    9000004500000500000\n--    (2.37 secs, 1,380,492,448 bytes)\n--    \u03bb> sum (sumasParciales4 [1..3*10^6])\n--    9000004500000500000\n--    (1.84 secs, 1,211,188,264 bytes)\n--    \u03bb> sum (sumasParciales5 [1..3*10^6])\n--    9000004500000500000\n--    (1.22 secs, 987,790,392 bytes)\n--    \u03bb> sum (sumasParciales6 [1..3*10^6])\n--    9000004500000500000\n--    (1.34 secs, 1,059,792,344 bytes)\n--\n--    \u03bb> sum (sumasParciales5 [1..5*10^6])\n--    41666679166667500000\n--    (2.36 secs, 1,844,332,576 bytes)\n--    \u03bb> sum (sumasParciales6 [1..5*10^6])\n--    41666679166667500000\n--    (2.03 secs, 1,964,365,912 bytes)\n<\/pre>\n
Nuevas soluciones<\/h4>\n
    \n
  • En los comentarios se pueden escribir nuevas soluciones.\n
  • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
    Los sufijos de la lista [3,7,2,5,4,6] son [3,7,2,5,4,6] [7,2,5,4,6] [2,5,4,6] [5,4,6] [4,6] [6] [] y la lista de sus sumas es [27,24,17,15,10,6,0]. Definir la funci\u00f3n sumasParciales :: [Integer] -> [Integer] tal que (sumasParciales xs) es la lista de las sumas de los sufijos de xs. Por ejemplo, sumasParciales [3,7,2,5,4,6] == [27,24,17,15,10,6,0] sumasParciales [1..10] == [55,54,52,49,45,40,34,27,19,10,0]…<\/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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6130"}],"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=6130"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6130\/revisions"}],"predecessor-version":[{"id":6192,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6130\/revisions\/6192"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}