Problema de las monedas por búsqueda en escalada
El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).
En la representación se usarán los siguientes tipos:
Moneda, que es un número entero representado el valor de la monedaSolucion, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista más corta con la misma suma.
Usando la búsqueda en escalada, definir la función
|
1 |
cambio :: Int -> Solucion |
tal que (cambio n) es la solución del problema de las monedas, para obtener la cantidad n, por búsqueda en escalada. Por ejemplo,
|
1 |
cambio 199 == [2,2,5,20,20,50,100] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
module Escalada_Monedas where import BusquedaEnEscalada import Test.Hspec (Spec, hspec, it, shouldBe) -- Las monedas son números enteros. type Moneda = Int -- monedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. monedas :: [Moneda] monedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Solucion = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type Estado = (Int, [Moneda]) -- (inicial n) es el estado inicial del problema de las monedas, para -- obtener la cantidad n. inicial :: Int -> Estado inicial n = (n, []) -- (esFinal e) se verifica si e es un estado final del problema -- de las monedas. esFinal :: Estado -> Bool esFinal (v,_) = v == 0 -- (sucesores e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- λ> sucesores (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesores :: Estado -> [Estado] sucesores (r,p) = [(r-c,c:p) | c <- monedas, r-c >= 0] cambio :: Int -> Solucion cambio n = snd (head (buscaEscalada sucesores esFinal (inicial n))) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ cambio 199 `shouldBe` [2,2,5,20,20,50,100] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0003 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada # Las monedas son números enteros. Moneda = int # monedas es la lista del tipo de monedas disponibles. Se supone que # hay un número infinito de monedas de cada tipo. monedas: list[Moneda] = [1,2,5,10,20,50,100] # Las soluciones son listas de monedas. Solucion = list[Moneda] # Los estados son pares formados por la cantidad que falta y la lista # de monedas usadas. Estado = tuple[int, list[Moneda]] # inicial(n) es el estado inicial del problema de las monedas, para # obtener la cantidad n. def inicial(n: int) -> Estado: return (n, []) # esFinal(e) se verifica si e es un estado final del problema # de las monedas. def esFinal(e: Estado) -> bool: return e[0] == 0 # sucesores(e) es la lista de los sucesores del estado e en el # problema de las monedas. Por ejemplo, # λ> sucesores((199,[])) # [(198,[1]),(197,[2]),(194,[5]),(189,[10]), # (179,[20]),(149,[50]),(99,[100])] def sucesores(e: Estado) -> list[Estado]: (r,p) = e return [(r - c, [c] + p) for c in monedas if r - c >= 0] def cambio(n: int) -> Optional[Solucion]: r = buscaEscalada(sucesores, esFinal, inicial(n)) if r is None: return None return r[1] # Verificación # ============ def test_monedas() -> None: assert cambio(199) == [2,2,5,20,20,50,100] # La verificación es # src> poetry run pytest -q Escalada_Monedas.py # 1 passed in 0.12s |