El problema del cambio con el menor n\u00famero de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor n\u00famero de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 c\u00e9ntimos se puede obtener 6 c\u00e9ntimos de 4 formas<\/p>\n
\n 1, 1, 1, 1, 1, 1\n 1, 1, 1, 3\n 1, 1, 4\n 3, 3\n<\/pre>\nEl menor n\u00famero de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.<\/p>\n
Definir<\/p>\n
\n monedas :: [Int] -> Int -> Maybe Int\n<\/pre>\ntal que (monedas ms x) es el menor n\u00famero de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,<\/p>\n
\n monedas [1,3,4] 6 == Just 2\n monedas [2,5,10] 3 == Nothing\n monedas [1,2,5,10,20,50,100,200] 520 == Just 4\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array ((!), array)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmonedas :: [Int] -> Int -> Maybe Int\nmonedas ms x\n | null cs = Nothing\n | otherwise = Just (minimum (map length cs))\n where cs = cambios ms x\n\n-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas\n-- de ms. Por ejemplo,\n-- \u03bb> cambios [1,5,10] 12\n-- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]]\n-- \u03bb> cambios [2,5,10] 3\n-- []\n-- \u03bb> cambios [1,3,4] 6\n-- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]\ncambios :: [Int] -> Int -> [[Int]]\ncambios _ 0 = [[]]\ncambios [] _ = []\ncambios (k:ks) m\n | m < k = []\n | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++\n cambios ks m\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmonedas2 :: [Int] -> Int -> Maybe Int\nmonedas2 ms n\n | sol == infinito = Nothing\n | otherwise = Just sol\n where\n sol = aux n\n aux 0 = 0\n aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x])\n\ninfinito :: Int\ninfinito = 10^30\n\nminimo :: [Int] -> Int\nminimo [] = infinito\nminimo xs = minimum xs\n\nsiguiente :: Int -> Int\nsiguiente x | x == infinito = infinito\n | otherwise = 1 + x\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmonedas3 :: [Int] -> Int -> Maybe Int\nmonedas3 ms n \n | sol == infinito = Nothing\n | otherwise = Just sol\n where\n sol = v ! n\n v = array (0,n) [(i,f i) | i <- [0..n]]\n f 0 = 0\n f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> monedas [1,2,5,10,20,50,100,200] 27\n-- Just 3\n-- (0.02 secs, 871,144 bytes)\n-- \u03bb> monedas2 [1,2,5,10,20,50,100,200] 27\n-- Just 3\n-- (15.44 secs, 1,866,519,080 bytes)\n-- \u03bb> monedas3 [1,2,5,10,20,50,100,200] 27\n-- Just 3\n-- (0.01 secs, 157,232 bytes)\n-- \n-- \u03bb> monedas [1,2,5,10,20,50,100,200] 188\n-- Just 7\n-- (14.20 secs, 1,845,293,080 bytes)\n-- \u03bb> monedas3 [1,2,5,10,20,50,100,200] 188\n-- Just 7\n-- (0.01 secs, 623,376 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"El problema del cambio con el menor n\u00famero de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor n\u00famero de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 c\u00e9ntimos se puede…<\/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,500,286,28,10,340,141,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\/5944"}],"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=5944"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5944\/revisions"}],"predecessor-version":[{"id":5967,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5944\/revisions\/5967"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}