Menu Close

Categoría: Avanzado

Representaciones de un número como potencia

El número 512 se puede escribir de tres maneras como potencias:

   512 = 2⁹ = 8³ = 512¹

Definir las funciones

   potencias       :: Integer -> [(Integer,Integer)]
   numeroPotencias :: Integer -> Int

tales que

  • (potencias x) es la lista de las representaciones de x como potencias de números enteros positivos. Por ejemplo,
     potencias 7      ==  [(7,1)]
     potencias 8      ==  [(2,3),(8,1)]
     potencias 512    ==  [(2,9),(8,3),(512,1)]
     potencias 16384  ==  [(2,14),(4,7),(128,2),(16384,1)]
     potencias 65536  ==  [(2,16),(4,8),(16,4),(256,2),(65536,1)]
  • (numeroPotencias x) de las representaciones de x como potencias de números enteros positivos. Por ejemplo,
     numeroPotencias 7          ==  1
     numeroPotencias 8          ==  2
     numeroPotencias 512        ==  3
     numeroPotencias 16384      ==  4
     numeroPotencias 65536      ==  5
     numeroPotencias (2^(10^5)) ==  36

Soluciones

import Data.List (group,genericLength)
import Data.Numbers.Primes (primeFactors)
 
potencias :: Integer -> [(Integer,Integer)]
potencias x = [(a^d,b `div` d) | d <- divisores b]
  where ps = factorizacionPrima x
        b   = mcd (map snd ps)
        a   = product [c^(e `div` b) | (c,e) <- ps]
 
-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 120  ==  [1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]
divisores :: Integer -> [Integer]
divisores x =
  [y | y <- [1..x], x `mod` y == 0]
 
-- (factorizacionPrima x) es la factorización prima de x. Por ejemplo,
--    factorizacionPrima 1200  ==  [(2,4),(3,1),(5,2)]
factorizacionPrima :: Integer -> [(Integer,Integer)]
factorizacionPrima x =
  [(head xs, genericLength xs) | xs <- group (primeFactors x)]
 
-- (mcd xs) es el máximo común divisor de xs. Por ejemplo,
--    mcd [12,30,42]  ==  6
mcd :: Integral a => [a] -> a
mcd xs = foldr1 gcd xs
 
-- 1ª definición de numeroPotencias
-- ================================
 
--    numeroPotencias 7          ==  1
--    numeroPotencias 8          ==  2
--    numeroPotencias 512        ==  3
--    numeroPotencias 16384      ==  4
--    numeroPotencias 65536      ==  5
--    numeroPotencias (2^(10^5)) ==  36
numeroPotencias :: Integer -> Int
numeroPotencias = length . potencias
 
-- 2ª definición de numeroPotencias
-- ================================
 
numeroPotencias2 :: Integer -> Int
numeroPotencias2 n =
  numeroDivisores (mcd (map length (group (primeFactors n))))
 
-- (numeroDivisores n) es el número de divisores de n. Por ejemplo,
--    numeroDivisores 12  ==  6
--    numeroDivisores 14  ==  4
numeroDivisores :: Int -> Int
numeroDivisores =
  product . map ((+1) . length) . group . primeFactors
 
-- Comparación de eficiencia de numeroPotencias
-- ============================================
 
-- La comparación es
--    λ> numeroPotencias (2^(10^5))
--    36
--    (0.40 secs, 707,287,312 bytes)
--    λ> numeroPotencias2 (2^(10^5))
--    36
--    (0.35 secs, 675,954,872 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Espirales

Definir la función

   espiral :: Int -> [[Int]]

tal que (espiral n) es la espiral de orden n (es decir, con n filas y n columnas). Por ejemplo,

   λ> mapM_ print (espiral 5)
   [1,1,1,1,1]
   [0,0,0,0,1]
   [1,1,1,0,1]
   [1,0,0,0,1]
   [1,1,1,1,1]
   λ> mapM_ print (espiral 6)
   [1,1,1,1,1,1]
   [0,0,0,0,0,1]
   [1,1,1,1,0,1]
   [1,0,0,1,0,1]
   [1,0,0,0,0,1]
   [1,1,1,1,1,1]
   λ> mapM_ print (espiral 7)
   [1,1,1,1,1,1,1]
   [0,0,0,0,0,0,1]
   [1,1,1,1,1,0,1]
   [1,0,0,0,1,0,1]
   [1,0,1,1,1,0,1]
   [1,0,0,0,0,0,1]
   [1,1,1,1,1,1,1]
   λ> mapM_ print (espiral 8)
   [1,1,1,1,1,1,1,1]
   [0,0,0,0,0,0,0,1]
   [1,1,1,1,1,1,0,1]
   [1,0,0,0,0,1,0,1]
   [1,0,1,0,0,1,0,1]
   [1,0,1,1,1,1,0,1]
   [1,0,0,0,0,0,0,1]
   [1,1,1,1,1,1,1,1]

Nota: La serpiente (formada por los 1) nunca se puede tocar a ella misma.

Soluciones

import Data.List (transpose)
 
espiral :: Int -> [[Int]]
espiral n = espiralAux n n
 
espiralAux :: Int -> Int -> [[Int]]
espiralAux 0 _ = []
espiralAux 1 1 = [[1]]
espiralAux n m = primeraFila n : segundaFila n : filasDesdeTercera n m
 
-- (primeraFila n) es la primera fila de la espiral de orden n. Por
-- ejemplo,
--    λ> primeraFila 5
--    [1,1,1,1,1]
primeraFila :: Int -> [Int]
primeraFila n = replicate n 1
 
-- (segundaFila n) es la segunda de la espiral de orden n. Por
-- ejemplo,
--    λ> segundaFila 5
--    [0,0,0,0,1]
segundaFila :: Int -> [Int]
segundaFila n = replicate (n-1) 0 ++ [1]
 
-- (filasDesdeTercera n m), cuando n = m, es la lista de las filas de la
-- espiral de orden n a partir de la tercera. Por ejemplo,
--    λ> mapM_ print (filasDesdeTercera 5 5)
--    [1,1,1,0,1]
--    [1,0,0,0,1]
--    [1,1,1,1,1]
filasDesdeTercera :: Int -> Int -> [[Int]]
filasDesdeTercera n m = map reverse (transpose (espiralAux (m-2) n))

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Menor número con una cantidad dada de divisores

El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

Definir la función

   menor :: Integer -> Integer

tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,

   menor 1  ==  2
   menor 2  ==  6
   menor 3  ==  24
   menor 4  ==  120
   length (show (menor (4*10^4)))  ==  207945

Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.

Soluciones

import Data.List (genericLength, genericTake, group)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
menor1 :: Integer -> Integer
menor1 n = head [x | x <- [1..], numeroDivisores x == 2^n]
 
numeroDivisores :: Integer -> Integer
numeroDivisores =
  genericLength . divisores
 
-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 12  ==  [1,3,2,6,4,12]
--    divisores 25  ==  [1,5,25]
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n], n `rem` x == 0]
 
-- 2ª solución
-- ===========
 
menor2 :: Integer -> Integer
menor2 n = head [x | x <- [1..], numeroDivisores2 x == 2^n]
 
-- (numeroDivisores2 x) es el número de divisores de x. Por ejemplo,
--    numeroDivisores2 120  ==  16
numeroDivisores2 :: Integer -> Integer
numeroDivisores2 =
  product . map ((+1) . genericLength) . group . primeFactors
 
-- 3ª solución
-- ===========
 
menor3 :: Integer -> Integer
menor3 n = product (genericTake n potencias)
 
-- potencias es la sucesión de las potencias de la forma p^(2^k),
-- donde p es un número primo y k es un número natural, ordenadas de
-- menor a mayor. Por ejemplo,
--    take 14 potencias    ==  [2,3,4,5,7,9,11,13,16,17,19,23,25,29]
potencias :: [Integer]
potencias = 2 : mezcla (tail primes) (map (^2) potencias)
 
-- (mezcla xs ys) es la lista obtenida mezclando las dos listas xs e ys,
-- que se suponen ordenadas y disjuntas. Por ejemplo,
--    ghci> take 15 (mezcla [2^n | n <- [1..]] [3^n | n <- [1..]])
--    [2,3,4,8,9,16,27,32,64,81,128,243,256,512,729]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)
                     | x > y = y : mezcla (x:xs) ys
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--   λ> menor 8
--   1081080
--   (47.69 secs, 94,764,856,352 bytes)
--   λ> menor2 8
--   1081080
--   (36.17 secs, 94,764,856,368 bytes)
--   λ> menor3 8
--   1081080
--   (0.00 secs, 116,960 bytes)
 
-- Definición de menor
-- ===================
 
-- En lo que sigue, usaremos menor3 como menor.
menor :: Integer -> Integer
menor = menor3
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_menor :: Integer -> Property
prop_menor k =
  k >= 0 ==>
  menor (k+1) `mod` menor k == 0
 
-- La comprobación es
--    λ> quickCheck prop_menor
--    +++ OK, passed 100 tests.

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Mayor número borrando k dígitos

Definir la función

   mayorBorrando :: Int -> Integer -> Integer

tal que (mayorBorrando k n) es el mayor número obtenido borrando k dígitos de n (se supone que n tiene más de k dígitos). Por ejemplo,

   mayorBorrando 1 6782334  ==  782334
   mayorBorrando 3 6782334  ==  8334
   mayorBorrando 3 10020    ==  20
   mayorBorrando 1000000 (4256 + 10^1000004) == 14256

Soluciones

import Data.List (subsequences)
 
-- 1ª definición
-- =============
 
mayorBorrando :: Int -> Integer -> Integer
mayorBorrando k n = read (mayorBorrandoLista1 k (show n))
 
-- (mayorBorrandoLista1 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista1 1 "6782334"  ==  "782334"
--    mayorBorrandoLista1 3 "6782334"  ==  "8334"
mayorBorrandoLista1 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista1 k xs = maximum (borra1 k xs)
 
-- (borra1 k xs) es la lista de las listas obtenidas borrando k elementos
-- de xs. Por ejemplo,
--    borra1 1 "abcd"  ==  ["abc","abd","acd","bcd"]
--    borra1 2 "abcd"  ==  ["ab","ac","bc","ad","bd","cd"]
--    borra1 3 "abcd"  ==  ["a","b","c","d"]
borra1 n xs = [ys | ys <- subsequences xs, length ys == k]
  where k = length xs - n
 
-- 2ª definición
-- =============
 
mayorBorrando2 :: Int -> Integer -> Integer
mayorBorrando2 k n = read (mayorBorrandoLista2 k (show n))
 
-- (mayorBorrandoLista2 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista2 1 "6782334"  ==  "782334"
--    mayorBorrandoLista2 3 "6782334"  ==  "8334"
mayorBorrandoLista2 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista2 k xs = maximum (borra2 k xs)
 
-- (borra2 k xs) es la lista de las listas obtenidas borrando k elementos
-- de xs. Por ejemplo,
--    borra2 1 "abcd"  ==  ["abc","abd","acd","bcd"]
--    borra2 2 "abcd"  ==  ["ab","ac","ad","bc","bd","cd"]
--    borra2 3 "abcd"  ==  ["a","b","c","d"]
borra2 :: Eq a => Int -> [a] -> [[a]]
borra2 0 xs     = [xs]
borra2 n []     = []
borra2 n (x:xs) = [x:ys | ys <- borra2 n xs] ++ borra2 (n-1) xs
 
-- 3ª definición
-- =============
 
mayorBorrando3 :: Int -> Integer -> Integer
mayorBorrando3 k n = read (mayorBorrandoLista3 k (show n))
 
-- (mayorBorrandoLista3 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista3 1 "6782334"  ==  "782334"
--    mayorBorrandoLista3 3 "6782334"  ==  "8334"
mayorBorrandoLista3 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista3 k xs = maximum (itera k borraUnoListas [xs])
 
-- (borraUnoListas xss) es la lista obtenida borrando un elemento (de
-- todas las formas posibles de la lista de listas no vacías xss. Por
-- ejemplo,
--    borraUnoListas ["abc","def"]  ==  ["bc","ac","ab","ef","df","de"]
borraUnoListas :: [[a]] -> [[a]]
borraUnoListas = concatMap borraUno
 
-- (borraUno xs) es la lista de listas obtenidas borrando un elemento de la
-- lista no vacía xs de todas las formas posibles. Por ejemplo,
--    borraUno "abcde"  ==  ["bcde","acde","abde","abce","abcd"]
borraUno :: [a] -> [[a]]
borraUno [x] = [[]]
borraUno (x:xs) = xs : map (x:) (borraUno xs)
 
-- (itera k f x) es el resultado de aplicar k veces la función f al
-- elemento x. Por ejmplo,
--    itera 3 (*2) 1   ==  8
--    itera 4 (+2) 10  ==  18
itera :: Eq a => Int -> (a -> a) -> a -> a
itera 0 _ x = x
itera n f x = itera (n-1) f (f x)
 
-- 4ª definición
-- =============
 
mayorBorrando4 :: Int -> Integer -> Integer
mayorBorrando4 k n = read (mayorBorrandoLista4 k (show n))
 
-- (mayorBorrandoLista4 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista4 1 "6782334"  ==  "782334"
--    mayorBorrandoLista4 3 "6782334"  ==  "8334"
mayorBorrandoLista4 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista4 k = itera k mayorBorraUno
 
-- (mayorBorraUno xs) es la mayor lista obtenida eliminando un elemento de
-- xs. Por ejemplo,
--    mayorBorraUno "6782334"  ==  "782334"
--    mayorBorraUno "782334"   ==  "82334"
--    mayorBorraUno "82334"    ==  "8334"
mayorBorraUno :: Ord a => [a] -> [a]
mayorBorraUno = maximum . borraUno
 
-- 5ª definición
-- =============
 
mayorBorrando5 :: Int -> Integer -> Integer
mayorBorrando5 k n = read (mayorBorrandoLista5 k (show n))
 
-- (mayorBorrandoLista5 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista5 1 "6782334"  ==  "782334"
--    mayorBorrandoLista5 3 "6782334"  ==  "8334"
mayorBorrandoLista5 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista5 k = itera k mayorBorraUno2
 
-- (mayorBorraUno2 xs) es la mayor lista obtenida eliminando un elemento de
-- xs. Por ejemplo,
--    mayorBorraUno2 "6782334"  ==  "782334"
--    mayorBorraUno2 "782334"   ==  "82334"
--    mayorBorraUno2 "82334"    ==  "8334"
mayorBorraUno2 :: Ord a => [a] -> [a]
mayorBorraUno2 [x]      = []
mayorBorraUno2 (x:y:xs) | x < y     = y:xs
                        | otherwise = x : mayorBorraUno2 (y:xs)
 
-- 6ª definición
-- =============
 
mayorBorrando6 :: Int -> Integer -> Integer
mayorBorrando6 k n = read (mayorBorrandoLista6 k (show n))
 
-- (mayorBorrandoLista6 k xs) es la mayor lista obtenida borrando k elementos de
-- xs (se supone que xs tiene más de k elementos). Por ejemplo,
--    mayorBorrandoLista6 1 "6782334"  ==  "782334"
--    mayorBorrandoLista6 3 "6782334"  ==  "8334"
mayorBorrandoLista6 :: Ord a => Int -> [a] -> [a]
mayorBorrandoLista6 k xs = aux k [] xs
 
aux 0 ys     xs     = reverse ys ++ xs
aux k ys     []     = reverse (drop k ys)
aux k []     (x:xs) = aux k [x] xs
aux k (y:ys) (x:xs) | y >= x    = aux k     (x:y:ys) xs
                    | otherwise = aux (k-1) ys       (x:xs)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> mayorBorrando 6 (product [1..18])
--    7705728000
--    (0.06 secs, 15,165,496 bytes)
--    λ> mayorBorrando2 6 (product [1..18])
--    7705728000
--    (0.04 secs, 19,662,816 bytes)
--    λ> mayorBorrando3 6 (product [1..18])
--    7705728000
--    (6.93 secs, 5,143,807,064 bytes)
--    λ> mayorBorrando4 6 (product [1..18])
--    7705728000
--    (0.01 secs, 183,728 bytes)
--    λ> mayorBorrando5 6 (product [1..18])
--    7705728000
--    (0.01 secs, 118,984 bytes)
--    λ> mayorBorrando6 6 (product [1..18])
--    7705728000
--
--    λ> mayorBorrando 17 (product [1..25])
--    998400000
--    (19.09 secs, 14,516,359,464 bytes)
--    λ> mayorBorrando2 17 (product [1..25])
--    998400000
--    (47.39 secs, 30,066,413,608 bytes)
--    λ> mayorBorrando4 17 (product [1..25])
--    998400000
--    (0.01 secs, 458,320 bytes)
--    λ> mayorBorrando5 17 (product [1..25])
--    998400000
--    (0.01 secs, 134,424 bytes)
--    λ> mayorBorrando6 17 (product [1..25])
--    984000000
--    (0.01 secs, 124,600 bytes)
--
--    λ> mayorBorrando4 600 (product [1..300])
--    999999999999999
--    (3.29 secs, 4,421,841,944 bytes)
--    λ> mayorBorrando5 600 (product [1..300])
--    999999999999999
--    (0.03 secs, 6,690,440 bytes)
--    λ> mayorBorrando6 600 (product [1..300])
--    960000000000000
--    (0.01 secs, 593,864 bytes)
--
--    λ> mayorBorrando5 10000 (4256 + 10^10004)
--    14256
--    (16.04 secs, 18,221,784,872 bytes)
--    λ> mayorBorrando6 10000 (4256 + 10^10004)
--    14256
--    (0.02 secs, 6,669,592 bytes)
--
--    λ> mayorBorrando6 1000000 (4256 + 10^1000004)
--    14256
--    (1.04 secs, 655,561,656 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Cambio con el menor número de monedas

El problema del cambio con el menor número 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 menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

   1, 1, 1, 1, 1, 1
   1, 1, 1, 3
   1, 1, 4
   3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

   monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

   monedas [1,3,4]  6                    ==  Just 2
   monedas [2,5,10] 3                    ==  Nothing
   monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

Soluciones

import Data.Array ((!), array)
 
-- 1ª solución
-- ===========
 
monedas :: [Int] -> Int -> Maybe Int
monedas ms x
  | null cs   = Nothing
  | otherwise = Just (minimum (map length cs))
  where cs = cambios ms x
 
-- (cambios ms x) es la lista de las foemas de obtener x sumando monedas
-- de ms. Por ejemplo,
--   λ> cambios [1,5,10] 12
--   [[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]]
--   λ> cambios [2,5,10] 3
--   []
--   λ> cambios [1,3,4] 6
--   [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]]
cambios :: [Int] -> Int -> [[Int]]
cambios _      0 = [[]]
cambios []     _ = []
cambios (k:ks) m
  | m < k     = []
  | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++
                cambios ks m
 
-- 2ª solución
-- ===========
 
monedas2 :: [Int] -> Int -> Maybe Int
monedas2 ms n
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = aux n
    aux 0 = 0
    aux k = siguiente (minimo [aux (k - x) | x <- ms,  k >= x])
 
infinito :: Int
infinito = 10^30
 
minimo :: [Int] -> Int
minimo [] = infinito
minimo xs = minimum xs
 
siguiente :: Int -> Int
siguiente x | x == infinito = infinito
            | otherwise     = 1 + x
 
-- 3ª solución
-- ===========
 
monedas3 :: [Int] -> Int -> Maybe Int
monedas3 ms n  
  | sol == infinito = Nothing
  | otherwise       = Just sol
  where
    sol = v ! n
    v   = array (0,n) [(i,f i) | i <- [0..n]]
    f 0 = 0
    f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x])
 
-- Comparación de eficiencia
-- =========================
 
--    λ> monedas [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.02 secs, 871,144 bytes)
--    λ> monedas2 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (15.44 secs, 1,866,519,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 27
--    Just 3
--    (0.01 secs, 157,232 bytes)
--    
--    λ> monedas [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (14.20 secs, 1,845,293,080 bytes)
--    λ> monedas3 [1,2,5,10,20,50,100,200] 188
--    Just 7
--    (0.01 secs, 623,376 bytes)