{"id":5791,"date":"2020-04-15T05:30:40","date_gmt":"2020-04-15T03:30:40","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5791"},"modified":"2020-04-29T07:29:04","modified_gmt":"2020-04-29T05:29:04","slug":"menor-no-expresable-como-suma","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/menor-no-expresable-como-suma\/","title":{"rendered":"Menor no expresable como suma"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   menorNoSuma :: [Integer] -> Integer\n<\/pre>\n<p>tal que (menorNoSuma xs) es el menor n\u00famero que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de n\u00fameros enteros positivos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   menorNoSuma [6,1,2]    ==  4\n   menorNoSuma [1,2,3,9]  ==  7\n   menorNoSuma [5]        ==  1\n   menorNoSuma [1..20]    ==  211\n   menorNoSuma [1..10^6]  ==  500000500001\n<\/pre>\n<p>Comprobar con QuickCheck que para todo n,<\/p>\n<pre lang=\"text\">\n   menorNoSuma [1..n] == 1 + sum [1..n]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n\n-- =============\n\nimport Data.List (sort, subsequences)\nimport Test.QuickCheck\n    \nmenorNoSuma1 :: [Integer] -> Integer\nmenorNoSuma1 xs =\n  head [n | n <- [1..], n `notElem` sumas xs]\n\n-- (sumas xs) es la lista de las sumas de los subconjuntos de xs. Por ejemplo,\n--    sumas [1,2,6]  ==  [0,1,2,3,6,7,8,9]\n--    sumas [6,1,2]  ==  [0,6,1,7,2,8,3,9]\nsumas :: [Integer] -> [Integer]\nsumas xs = map sum (subsequences xs)\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nmenorNoSuma2 :: [Integer] -> Integer\nmenorNoSuma2  = menorNoSumaOrd . reverse . sort \n\n-- (menorNoSumaOrd xs) es el menor n\u00famero que no se puede escribir como\n-- suma de un subconjunto de xs, donde xs es una lista de n\u00fameros\n-- naturales ordenada de mayor a menor. Por ejemplo,\n--    menorNoSumaOrd [6,2,1]  ==  4\nmenorNoSumaOrd [] = 1\nmenorNoSumaOrd (x:xs) | x > y     = y\n                      | otherwise = y+x\n  where y = menorNoSumaOrd xs\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> menorNoSuma1 [1..20]\n--    211\n--    (20.40 secs, 28,268,746,320 bytes)\n--    \u03bb> menorNoSuma2 [1..20]\n--    211\n--    (0.01 secs, 0 bytes)\n           \n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_menorNoSuma :: (Positive Integer) -> Bool\nprop_menorNoSuma (Positive n) =\n  menorNoSuma2 [1..n] == 1 + sum [1..n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_menorNoSuma\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n menorNoSuma :: [Integer] -> Integer tal que (menorNoSuma xs) es el menor n\u00famero que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de n\u00fameros enteros positivos. Por ejemplo, menorNoSuma [6,1,2] == 4 menorNoSuma [1,2,3,9] == 7 menorNoSuma [5] == 1 menorNoSuma&#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":[7],"tags":[8,71,27,11,6,32,14,88,40,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5791"}],"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=5791"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5791\/revisions"}],"predecessor-version":[{"id":5835,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5791\/revisions\/5835"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5791"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5791"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5791"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}