Problema del cambio de monedas

PorJosé A. Alonso 4-enero-201819-febrero-2018

El problema del cambio 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 número de formas de obtener y usando los tipos de monedas de ms. Por ejemplo, con monedas de 1, 5 y 10 céntimos se puede obtener 12 céntimos de 4 formas

   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

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

Definir las funciones

   numeroCambios :: [Int] -> Int -> Int
   sucCambios :: [Int]
   grafica_cambios :: Int -> IO ()

numeroCambios :: [Int] -> Int -> Int

sucCambios :: [Int]

grafica_cambios :: Int -> IO ()

tales que

(numeroCambios ms x) es el número de formas de obtener x usando los tipos de monedas de ms. Por ejemplo,

     numeroCambios [1,5,10] 12  ==  4
     numeroCambios [4,1,3] 6    ==  4
     numeroCambios [1,5,10] 50  ==  36

numeroCambios [1,5,10] 12 == 4

numeroCambios [4,1,3] 6 == 4

numeroCambios [1,5,10] 50 == 36

sucCambios es la sucesión cuyo k-ésimo término es el número de cambios de k usando monedas de 1, 2, 5 y 10 céntimos. Por ejemplo,

   λ> take 20 sucCambios
   [1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34]

1 2	λ> take 20 sucCambios [1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34]

(grafica_cambios n) dibuja la gráfica de los n primeros términos de la sucesión sucCambios. Por ejemplo, (grafica_cambios 50) dibuja

Soluciones

import Data.List (sort)
import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int
numeroCambios ms = aux (sort ms) 
  where
    aux _      0 = 1
    aux []     _ = 0
    aux (m:ms) x | x < m     = 0
                 | otherwise = aux (m:ms) (x - m) + aux ms x

cambios :: [Int] -> Int -> [[Int]]
cambios xs y = aux (sort xs) y
  where
    aux _      0 = [[]]
    aux []     _ = []
    aux (k:ks) m | m < k     = []
                 | otherwise = [k:zs | zs <- aux (k:ks) (m - k)] ++
                               aux ks m
                               
sucCambios :: [Int]
sucCambios = [numeroCambios [1,2,5,10] k | k <- [0..]]

grafica_cambios :: Int -> IO ()
grafica_cambios n =
  plotList [ Title "Cambios con monedas de 1, 2, 5 y 10"
           , Key Nothing
           , XLabel "Objetivo"
           , YLabel "Numero de cambios"
           , PNG "Problema_del_cambio_de_monedas.png"
           ]
           (take n sucCambios)

import Data.List (sort)

import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int

numeroCambios ms = aux (sort ms)

where

aux _ 0 = 1

aux [] _ = 0

aux (m:ms) x | x < m = 0

| otherwise = aux (m:ms) (x - m) + aux ms x

cambios :: [Int] -> Int -> [[Int]]

cambios xs y = aux (sort xs) y

where

aux _ 0 = [[]]

aux [] _ = []

aux (k:ks) m | m < k = []

| otherwise = [k:zs | zs <- aux (k:ks) (m - k)] ++

aux ks m

sucCambios :: [Int]

sucCambios = [numeroCambios [1,2,5,10] k | k <- [0..]]

grafica_cambios :: Int -> IO ()

grafica_cambios n =

plotList [ Title "Cambios con monedas de 1, 2, 5 y 10"

, Key Nothing

, XLabel "Objetivo"

, YLabel "Numero de cambios"

, PNG "Problema_del_cambio_de_monedas.png"

]

(take n sucCambios)

8 Comentarios

import Graphics.Gnuplot.Simple

cambio :: [Int] -> Int -> [[Int]]
cambio _  0 = [[]]
cambio [] _ = []
cambio xxs@(x:xs) n | n >= x    = map (x:) (cambio xxs (n - x)) ++ cambio xs n
                    | otherwise = cambio xs n


numeroCambios ms x = length (cambio ms x)



sucCambios :: [Int]
sucCambios = [numeroCambios [1,2,5,10] x | x <- [0..]]

grafica_cambios :: Int -> IO()
grafica_cambios n  = plotList [] (take n sucCambios)

import Graphics.Gnuplot.Simple

cambio :: [Int] -> Int -> [[Int]]

cambio _ 0 = [[]]

cambio [] _ = []

cambio xxs@(x:xs) n | n >= x = map (x:) (cambio xxs (n - x)) ++ cambio xs n

| otherwise = cambio xs n

numeroCambios ms x = length (cambio ms x)

sucCambios :: [Int]

sucCambios = [numeroCambios [1,2,5,10] x | x <- [0..]]

grafica_cambios :: Int -> IO()

grafica_cambios n = plotList [] (take n sucCambios)

Responder

import Graphics.Gnuplot.Simple
cambiosposibles :: [Int] -> Int -> [[Int]]
cambiosposibles _  0 = [[]]
cambiosposibles [] _ = []
cambiosposibles xxs@(x:xs) n | n >= x    = map (x:) (cambiosposibles xxs (n - x)) ++ cambiosposibles xs n
                    | otherwise = cambiosposibles xs n
 
numeroCambios ms x = length (cambiosposibles ms x)
        
sucCambios :: [Int]
sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO ()
grafica_cambios x = plotList [Title "Cambios con monedas de 1,2,5 y 10", XLabel "objetivo", YLabel "Numero de cambios", Key Nothing] (take x sucCambios)

import Graphics.Gnuplot.Simple

cambiosposibles :: [Int] -> Int -> [[Int]]

cambiosposibles _ 0 = [[]]

cambiosposibles [] _ = []

cambiosposibles xxs@(x:xs) n | n >= x = map (x:) (cambiosposibles xxs (n - x)) ++ cambiosposibles xs n

| otherwise = cambiosposibles xs n

numeroCambios ms x = length (cambiosposibles ms x)

sucCambios :: [Int]

sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO ()

grafica_cambios x = plotList [Title "Cambios con monedas de 1,2,5 y 10", XLabel "objetivo", YLabel "Numero de cambios", Key Nothing] (take x sucCambios)

Responder

numeroCambios :: [Int] -> Int -> Int
numeroCambios [] _ = 0
numeroCambios _ 0 = 1
numeroCambios (x:xs) n | n > 0 = numeroCambios (x:xs) (n-x) + numeroCambios xs n
                       | otherwise = 0

sucCambios :: [Int]
sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO()
grafica_cambios n = plotList [Title "Cambios con monedas de 1, 2, 5 y 10", XLabel "Objetivo", YLabel "Numero de cambios", Key Nothing] (take n sucCambios)

numeroCambios :: [Int] -> Int -> Int

numeroCambios [] _ = 0

numeroCambios _ 0 = 1

numeroCambios (x:xs) n | n > 0 = numeroCambios (x:xs) (n-x) + numeroCambios xs n

| otherwise = 0

sucCambios :: [Int]

sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO()

grafica_cambios n = plotList [Title "Cambios con monedas de 1, 2, 5 y 10", XLabel "Objetivo", YLabel "Numero de cambios", Key Nothing] (take n sucCambios)

Responder

numeroCambios :: [Int] -> Int -> Int
numeroCambios [] _ = 0
numeroCambios _ 0 = 1
numeroCambios xss@(x:xs) n | n > 0 = numeroCambios xss (n-x) + numeroCambios xs n
                           | otherwise = 0

numeroCambios :: [Int] -> Int -> Int

numeroCambios [] _ = 0

numeroCambios _ 0 = 1

numeroCambios xss@(x:xs) n | n > 0 = numeroCambios xss (n-x) + numeroCambios xs n

| otherwise = 0

Responder

import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int
numeroCambios _ 0 = 1
numeroCambios xs n = sum [numeroCambios (drop p xs) y | (x,p) <- zip xs [0..], let y = n-x, y >=0]

sucCambios :: [Int]
sucCambios = map (numeroCambios [1, 2, 5, 10]) [0..]

grafica_cambios :: Int -> IO()
grafica_cambios n = plotList [Title "Cambios con monedas de 1, 2, 5 y 10", XLabel "Objetivo", YLabel "Numero de cambios", Key Nothing] (take n sucCambios)

import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int

numeroCambios _ 0 = 1

numeroCambios xs n = sum [numeroCambios (drop p xs) y | (x,p) <- zip xs [0..], let y = n-x, y >=0]

sucCambios :: [Int]

sucCambios = map (numeroCambios [1, 2, 5, 10]) [0..]

grafica_cambios :: Int -> IO()

grafica_cambios n = plotList [Title "Cambios con monedas de 1, 2, 5 y 10", XLabel "Objetivo", YLabel "Numero de cambios", Key Nothing] (take n sucCambios)

Responder

Una propuesta usando árboles,

import Data.Tree (Tree(Node),levels)
import Data.List (tails,foldl',sortBy)
import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int
numeroCambios [] _ = 0
numeroCambios _  0 = 1
numeroCambios xs n =
  foldl' (flip $ (+) . sum) 0
  . concatMap levels
  $ zipWith (toTree n) (tails sxs) sxs
  where sxs = sortBy (flip compare) xs

toTree :: Int -> [Int] -> Int -> Tree Int
toTree n xs x
  | x < n     = Node 0 $ zipWith (toTree (n - x)) (tails xs) xs
  | x == n    = Node 1 []
  | otherwise = Node 0 []

sucCambios :: [Int]
sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO ()
grafica_cambios x =
  plotList
  [Title "Cambios con monedas de 1, 2, 5 y 10"
  , XLabel "Objetivo"
  , YLabel "Numero de cambios"
  , Key Nothing]
  (take x sucCambios)

import Data.Tree (Tree(Node),levels)

import Data.List (tails,foldl',sortBy)

import Graphics.Gnuplot.Simple

numeroCambios :: [Int] -> Int -> Int

numeroCambios [] _ = 0

numeroCambios _ 0 = 1

numeroCambios xs n =

foldl' (flip $ (+) . sum) 0

. concatMap levels

$ zipWith (toTree n) (tails sxs) sxs

where sxs = sortBy (flip compare) xs

toTree :: Int -> [Int] -> Int -> Tree Int

toTree n xs x

| x < n = Node 0 $ zipWith (toTree (n - x)) (tails xs) xs

| x == n = Node 1 []

| otherwise = Node 0 []

sucCambios :: [Int]

sucCambios = map (numeroCambios [1,2,5,10]) [0..]

grafica_cambios :: Int -> IO ()

grafica_cambios x =

plotList

[Title "Cambios con monedas de 1, 2, 5 y 10"

, XLabel "Objetivo"

, YLabel "Numero de cambios"

, Key Nothing]

(take x sucCambios)

Responder

Otra propuesta de numeroCambios usando secuencias en lugar de árboles,

import Data.Foldable (asum,foldl')
import Data.Sequence (Seq,fromList)
import Data.List (tails,sortBy)

numeroCambios :: [Int] -> Int -> Int
numeroCambios [] _ = 0
numeroCambios _  0 = 1
numeroCambios xs n =
  foldl' (flip $ (+) . sum) 0
  $ zipWith (toSeq n) (tails sxs) sxs
  where sxs = sortBy (flip compare) xs

toSeq :: Int -> [Int] -> Int -> Seq Int
toSeq n xs x
  | x < n     = asum $ zipWith (toSeq (n - x)) (tails xs) xs
  | x == n    = fromList [1]
  | otherwise = fromList [0]

import Data.Foldable (asum,foldl')

import Data.Sequence (Seq,fromList)

import Data.List (tails,sortBy)

numeroCambios :: [Int] -> Int -> Int

numeroCambios [] _ = 0

numeroCambios _ 0 = 1

numeroCambios xs n =

foldl' (flip $ (+) . sum) 0

$ zipWith (toSeq n) (tails sxs) sxs

where sxs = sortBy (flip compare) xs

toSeq :: Int -> [Int] -> Int -> Seq Int

toSeq n xs x

| x < n = asum $ zipWith (toSeq (n - x)) (tails xs) xs

| x == n = fromList [1]

| otherwise = fromList [0]

Responder

carbremor dice:

4-enero-2018 a las 19:54

— Otra forma de obtener la sucesión sucCambios. Basada en la OEIS —

sucCambios2 1 = 1
sucCambios2 2 = 1
sucCambios2 3 = 2
sucCambios2 4 = 2
sucCambios2 5 = 3
sucCambios2 6 = 4
sucCambios2 7 = 5
sucCambios2 8 = 6
sucCambios2 9 = 7
sucCambios2 10 = 8
sucCambios2 11 = 11
sucCambios2 12 = 12
sucCambios2 13 = 15
sucCambios2 14 = 16
sucCambios2 15 = 19
sucCambios2 16 = 22
sucCambios2 17 = 25
sucCambios2 n = sucCambios2(n-2) + sucCambios2(n-5) – sucCambios2(n-7) + sucCambios2(n-10) – sucCambios2(n-12) – sucCambios2 (n-15) + sucCambios2(n-17) +1

lista_sucCambios2 = [sucCambios2 n | n <- [1..]]

Responder

Problema del cambio de monedas

Soluciones

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico