{"id":8257,"date":"2023-08-04T06:00:40","date_gmt":"2023-08-04T04:00:40","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8257"},"modified":"2023-08-02T13:21:58","modified_gmt":"2023-08-02T11:21:58","slug":"04-ago-23-b","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-ago-23-b\/","title":{"rendered":"Problema de las monedas por b\u00fasqueda en escalada"},"content":{"rendered":"<p>El problema del cambio de monedas consiste en determinar  conseguir una cantidad usando el menor n\u00famero de monedas disponibles. Se supone que se posee un n\u00famero ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como m\u00ednimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).<\/p>\n<p>En la representaci\u00f3n se usar\u00e1n los siguientes tipos:<\/p>\n<ul>\n<li><code>Moneda<\/code>, que es un n\u00famero entero representado el valor de la moneda<\/li>\n<li><code>Solucion<\/code>, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista m\u00e1s corta con la misma suma.<\/li>\n<\/ul>\n<p>Usando la <a href=\"https:\/\/bit.ly\/3Kk4A99\">b\u00fasqueda en escalada<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   cambio :: Int -> Solucion\n<\/pre>\n<p>tal que <code>(cambio n)<\/code> es la soluci\u00f3n del problema de las monedas, para obtener la cantidad <code>n<\/code>, por b\u00fasqueda en escalada. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   cambio 199  ==  [2,2,5,20,20,50,100]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Escalada_Monedas where\n\nimport BusquedaEnEscalada\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Las monedas son n\u00fameros enteros.\ntype Moneda = Int\n\n-- monedas es la lista del tipo de monedas disponibles. Se supone que\n-- hay un n\u00famero infinito de monedas de cada tipo.\nmonedas :: [Moneda]\nmonedas = [1,2,5,10,20,50,100]\n\n-- Las soluciones son listas de monedas.\ntype Solucion = [Moneda]\n\n-- Los estados son pares formados por la cantidad que falta y la lista\n-- de monedas usadas.\ntype Estado = (Int, [Moneda])\n\n-- (inicial n) es el estado inicial del problema de las monedas, para\n-- obtener la cantidad n.\ninicial :: Int -> Estado\ninicial n = (n, [])\n\n-- (esFinal e) se verifica si e es un estado final del problema\n-- de las monedas.\nesFinal :: Estado -> Bool\nesFinal (v,_) = v == 0\n\n-- (sucesores e) es la lista de los sucesores del estado e en el\n-- problema de las monedas. Por ejemplo,\n--   \u03bb> sucesores (199,[])\n--   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n--    (179,[20]),(149,[50]),(99,[100])]\nsucesores :: Estado -> [Estado]\nsucesores (r,p) =\n  [(r-c,c:p) | c <- monedas, r-c >= 0]\n\ncambio :: Int -> Solucion\ncambio n =\n  snd (head (buscaEscalada sucesores\n                           esFinal\n                           (inicial n)))\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    cambio 199  `shouldBe`  [2,2,5,20,20,50,100]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--\n--    Finished in 0.0003 seconds\n--    1 example, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Optional\n\nfrom src.BusquedaEnEscalada import buscaEscalada\n\n# Las monedas son n\u00fameros enteros.\nMoneda = int\n\n# monedas es la lista del tipo de monedas disponibles. Se supone que\n# hay un n\u00famero infinito de monedas de cada tipo.\nmonedas: list[Moneda] = [1,2,5,10,20,50,100]\n\n# Las soluciones son listas de monedas.\nSolucion = list[Moneda]\n\n# Los estados son pares formados por la cantidad que falta y la lista\n# de monedas usadas.\nEstado = tuple[int, list[Moneda]]\n\n# inicial(n) es el estado inicial del problema de las monedas, para\n# obtener la cantidad n.\ndef inicial(n: int) -> Estado:\n    return (n, [])\n\n# esFinal(e) se verifica si e es un estado final del problema\n# de las monedas.\ndef esFinal(e: Estado) -> bool:\n    return e[0] == 0\n\n# sucesores(e) es la lista de los sucesores del estado e en el\n# problema de las monedas. Por ejemplo,\n#   \u03bb> sucesores((199,[]))\n#   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n#    (179,[20]),(149,[50]),(99,[100])]\ndef sucesores(e: Estado) -> list[Estado]:\n    (r,p) = e\n    return [(r - c, [c] + p) for c in monedas if r - c >= 0]\n\ndef cambio(n: int) -> Optional[Solucion]:\n    r = buscaEscalada(sucesores, esFinal, inicial(n))\n    if r is None:\n        return None\n    return r[1]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_monedas() -> None:\n    assert cambio(199) == [2,2,5,20,20,50,100]\n\n# La verificaci\u00f3n es\n#    src> poetry run pytest -q Escalada_Monedas.py\n#    1 passed in 0.12s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor n\u00famero de monedas disponibles. Se supone que se posee un n\u00famero ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como m\u00ednimo 7 monedas (129 = 2 + 2&#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":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8257"}],"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=8257"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8257\/revisions"}],"predecessor-version":[{"id":8259,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8257\/revisions\/8259"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}