-
Notifications
You must be signed in to change notification settings - Fork 0
/
Escalada_Monedas.hs
51 lines (41 loc) · 1.71 KB
/
Escalada_Monedas.hs
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
-- Escalada_Monedas.hs
-- Problema de las monedas por búsqueda en escalada.
-- José A. Alonso Jiménez https://jaalonso.github.com
-- =====================================================================
module Tema_23.Escalada_Monedas where
-- Hay que elegir una de las siguientes importaciones:
import Tema_23.BusquedaEnEscalada
-- import I1M.BusquedaEnEscalada
-- El problema del cambio de monedas consiste en determinar cómo
-- conseguir una cantidad usando el menor número de monedas disponibles.
-- 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 Soluciones = [Moneda]
-- Los estados son pares formados por la cantidad que falta y la lista
-- de monedas usadas.
type NodoMonedas = (Int, [Moneda])
-- (sucesoresMonedas e) es la lista de los sucesores del estado e en el
-- problema de las monedas. Por ejemplo,
-- λ> sucesoresMonedas (199,[])
-- [(198,[1]),(197,[2]),(194,[5]),(189,[10]),
-- (179,[20]),(149,[50]),(99,[100])]
sucesoresMonedas :: NodoMonedas -> [NodoMonedas]
sucesoresMonedas (r,p) =
[(r-c,c:p) | c <- monedas, r-c >= 0]
-- (esFinalMonedas e) se verifica si e es un estado final del problema
-- de las monedas.
esFinalMonedas :: NodoMonedas -> Bool
esFinalMonedas (v,_) = v==0
-- (cambio n) es la solución del problema de las monedas por búsqueda en
-- escalada. Por ejemplo,
-- cambio 199 == [2,2,5,20,20,50,100]
cambio :: Int -> Soluciones
cambio n =
snd (head (buscaEscalada sucesoresMonedas
esFinalMonedas
(n,[])))