0votos

Desglose en billetes en Haskell

por josejuan hace 4 años

La restricción habitual en este tipo de desgloses es "usar la mayor cantidad de monedas/billetes grandes posibles" con el fin de tener en caja la mayor probabilidad de poder seguir desglosando. Con dicha restricción, sólo hay que dividir de mayor a menor hasta resto 0.

Desglose en billetes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
data Soporte = Billete | Moneda deriving (Eq, Show) 
 
data Timbre a = Timbre { soporte :: Soporte, valor :: a } deriving Eq 
                        
data Efectivo a = Efectivo { timbre :: Timbre a, unds :: a } 
 
instance (Integral a, Show a) => Show (Efectivo a) where 
  show (Efectivo (Timbre t v) u) = show u ++ " " ++ show t ++ 
                                     (if u > 1 then "s" else "") ++ " de " ++ show v ++ " euros" 
 
timbres :: Integral a => [Timbre a] 
timbres = map (Timbre Billete) [500, 200, 100, 50, 20, 10, 5] ++ map (Timbre Moneda ) [2, 1] 
 
desglose :: Integral a => a -> [Efectivo a] 
desglose 0 = [] 
desglose n = let (m@(Timbre _ v):_) = dropWhile ((>n).valor) timbres 
             in  Efectivo m (n `div` v): desglose (n `mod` v) 
 
main = mapM_ (putStrLn.show) $ desglose 1234567890987654321 
2 comentarios
0votos

Escrito por nRikee hace 4 años

"Usar la menor cantidad de monedas/billetes", ¿no?
0votos

Escrito por josejuan hace 4 años

Parece obvio que, buscando un importe exacto, las expresiones:
  • usar el mayor posible de grandes.
  • usar el menor posible de pequeños.
  • usar el menor posible de cualquiera.

Son equivalentes, de ahí que sea comprensible la cuestión que planteas pero, siendo equivalentes ¡mi premisa es correcta! :)

El motivo por el que he usado esa forma y no alguna de las otras, es que el algoritmo, precisamente, "busca el mayor número de billetes grandes posibles" que, de forma inmediata, nos da "el menor número de billetes posibles".

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.