Exercitium

Refinamiento de montículos

PorJosé A. Alonso 28-mayo-201513-junio-2015

Definir la función

   refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a

1	refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a

tal que (refina m ps) es el montículo formado por los elementos del montículo m que cumplen todos los predicados de la lista ps. Por ejemplo,

   ghci> refina (foldr inserta vacio [1..22]) [(<7), even]
   M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio
   ghci> refina (foldr inserta vacio [1..22]) [(<1), even]
   Vacio

ghci> refina (foldr inserta vacio [1..22]) [(<7), even]

M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio

ghci> refina (foldr inserta vacio [1..22]) [(<1), even]

Vacio

Soluciones

refina :: Ord a => Monticulo a -> [a-> Bool] -> Monticulo a 
refina m ps | esVacio m   = vacio
            | cumple x ps = inserta x (refina r ps)
            | otherwise   = refina r ps
            where x = menor m
                  r = resto m

-- (cumple x ps) se verifica si x cumple todos los predicados de ps. Por
-- ejemplo,  
--    cumple 2 [(<7), even]  ==  True
--    cumple 3 [(<7), even]  ==  False
--    cumple 8 [(<7), even]  ==  False
cumple :: a -> [a -> Bool] -> Bool
cumple x ps = and [p x | p <- ps]

-- La función cumple se puede definir por recursión:
cumple2 x []     = True
cumple2 x (p:ps) = p x && cumple x ps

refina :: Ord a => Monticulo a -> [a-> Bool] -> Monticulo a

refina m ps | esVacio m = vacio

| cumple x ps = inserta x (refina r ps)

| otherwise = refina r ps

where x = menor m

r = resto m

-- (cumple x ps) se verifica si x cumple todos los predicados de ps. Por

-- ejemplo,

-- cumple 2 [(<7), even] == True

-- cumple 3 [(<7), even] == False

-- cumple 8 [(<7), even] == False

cumple :: a -> [a -> Bool] -> Bool

cumple x ps = and [p x | p <- ps]

-- La función cumple se puede definir por recursión:

cumple2 x [] = True

cumple2 x (p:ps) = p x && cumple x ps

Cálculo de aprobados

PorJosé A. Alonso 27-mayo-201513-junio-2015

La notas de un examen se pueden representar mediante un vector en el que los valores son los pares formados por los nombres de los alumnos y sus notas.

Definir la función

   aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]

1	aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]

tal que (aprobados p) es la lista de los nombres de los alumnos que han aprobado y Nothing si todos están suspensos. Por ejemplo,

   ghci> aprobados (listArray (1,3) [("Ana",5),("Pedro",3),("Lucia",6)])
   Just ["Ana","Lucia"]
   ghci> aprobados (listArray (1,3) [("Ana",4),("Pedro",3),("Lucia",4.9)])
   Nothing

ghci> aprobados (listArray (1,3) [("Ana",5),("Pedro",3),("Lucia",6)])

Just ["Ana","Lucia"]

ghci> aprobados (listArray (1,3) [("Ana",4),("Pedro",3),("Lucia",4.9)])

Nothing

Soluciones

import Data.Array

aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]
aprobados p | null xs   = Nothing
            | otherwise = Just xs
    where xs = [x | (x,n) <- elems p, n >= 5]

import Data.Array

aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]

aprobados p | null xs = Nothing

| otherwise = Just xs

where xs = [x | (x,n) <- elems p, n >= 5]

Reparto de escaños por la ley d’Hont

PorJosé A. Alonso 26-mayo-201525-abril-2021

El sistema D’Hondt es una fórmula electoral, creada por Victor d’Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

   reparto :: Int -> [Int] -> [(Int,Int)]

1	reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

   ghci> reparto 7 [340000,280000,160000,60000,15000]
   [(1,3),(2,3),(3,1)]
   ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
   [(1,9),(2,7),(3,4),(4,1)]

ghci> reparto 7 [340000,280000,160000,60000,15000]

[(1,3),(2,3),(3,1)]

ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]

[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Soluciones

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de
-- votos entre 5 partidos.
ejVotos :: [Int]
ejVotos = [340000,280000,160000,60000,15000]

ejVotos2 :: [Int]
ejVotos2 = [391000,311000,184000,73000,27000,12000,2000]

-- ghci> reparto 21 ejVotos2
-- [(1,9),(2,7),(3,4),(4,1)]

ejVotos3 :: [Int]
ejVotos3 = [221,195,40,6,4]

-- (votosPartidos vs) es la lista con los pares formados por los votos y
-- el número de cada partido. Por ejemplo, 
--    ghci> votosPartidos ejVotos
--    [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]
votosPartidos :: [Int] -> [(Int,Int)]
votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.
-- Por ejemplo, 
--    ghci> restos 5 (340000,1)
--    [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]
restos :: Int -> (Int,Int) -> [(Int,Int)]
restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- (reparto1 n vs) es la lista formada por los n restos mayores
-- correspondientes a la lista de votos vs. Por ejemplo,
--    ghci> reparto1 7 ejVotos
--    [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),
--     (93333,2)]
reparto1 :: Int -> [Int] -> [(Int,Int)]
reparto1 n vs = 
    take n $ reverse $ sort (concatMap (restos n) (votosPartidos vs))

-- (reparto2 n vs) es el número de los partidos, cuyos votos son vs, que
-- obtienen los n escaños. Por ejemplo,
--    ghci> reparto2 7 ejVotos
--    [1,2,1,3,2,1,2]
reparto2 :: Int -> [Int] -> [Int]
reparto2 n vs = map snd (reparto1 n vs)

-- (reparto n vs) es la lista de los pares formados por los números de
-- los partidos y el número de escaño que les corresponden al repartir n
-- escaños en función de la lista de sus votos. Por ejemplo, 
--    ghci> reparto 7 ejVotos
--    [(1,3),(2,3),(3,1)]
reparto :: Int -> [Int] -> [(Int,Int)]
reparto n vs = 
    [(x,1 + length xs) | (x:xs) <- group (sort (reparto2 n vs))]

import Data.List (sort, group)

-- Para los ejemplos que siguen, se usará la siguiente ditribución de

-- votos entre 5 partidos.

ejVotos :: [Int]

ejVotos = [340000,280000,160000,60000,15000]

ejVotos2 :: [Int]

ejVotos2 = [391000,311000,184000,73000,27000,12000,2000]

-- ghci> reparto 21 ejVotos2

-- [(1,9),(2,7),(3,4),(4,1)]

ejVotos3 :: [Int]

ejVotos3 = [221,195,40,6,4]

-- (votosPartidos vs) es la lista con los pares formados por los votos y

-- el número de cada partido. Por ejemplo,

-- ghci> votosPartidos ejVotos

-- [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]

votosPartidos :: [Int] -> [(Int,Int)]

votosPartidos vs = zip vs [1..]

-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.

-- Por ejemplo,

-- ghci> restos 5 (340000,1)

-- [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]

restos :: Int -> (Int,Int) -> [(Int,Int)]

restos n (x,i) = [(x `div` k,i) | k <- [1..n]]

-- (reparto1 n vs) es la lista formada por los n restos mayores

-- correspondientes a la lista de votos vs. Por ejemplo,

-- ghci> reparto1 7 ejVotos

-- [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),

-- (93333,2)]

reparto1 :: Int -> [Int] -> [(Int,Int)]

reparto1 n vs =

take n $ reverse $ sort (concatMap (restos n) (votosPartidos vs))

-- (reparto2 n vs) es el número de los partidos, cuyos votos son vs, que

-- obtienen los n escaños. Por ejemplo,

-- ghci> reparto2 7 ejVotos

-- [1,2,1,3,2,1,2]

reparto2 :: Int -> [Int] -> [Int]

reparto2 n vs = map snd (reparto1 n vs)

-- (reparto n vs) es la lista de los pares formados por los números de

-- los partidos y el número de escaño que les corresponden al repartir n

-- escaños en función de la lista de sus votos. Por ejemplo,

-- ghci> reparto 7 ejVotos

-- [(1,3),(2,3),(3,1)]

reparto :: Int -> [Int] -> [(Int,Int)]

reparto n vs =

[(x,1 + length xs) | (x:xs) <- group (sort (reparto2 n vs))]

Inversiones de un número

PorJosé A. Alonso 25-mayo-201530-noviembre-2015

Un número tiene una inversión cuando existe un dígito x a la derecha de otro dígito de forma que x es menor que y. Por ejemplo, en el número 1745 hay dos inversiones ya que 4 es menor que 7 y 5 es menor que 7 y están a la derecha de 7.

Definir la función

   nInversiones :: Integer -> Int

1	nInversiones :: Integer -> Int

tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,

   nInversiones 1745  ==  2

1	nInversiones 1745 == 2

Soluciones

import Data.List (tails)

-- 1ª definición
-- =============

nInversiones1 :: Integer -> Int
nInversiones1 = length . inversiones . show

-- (inversiones xs) es la lista de las inversiones de xs. Por ejemplo, 
--    inversiones "1745"   ==  [('7','4'),('7','5')]
--    inversiones "cbafd"  ==  [('c','b'),('c','a'),('b','a'),('f','d')]
inversiones :: Ord a => [a] -> [(a,a)]
inversiones []     = []
inversiones (x:xs) = [(x,y) | y <- xs, y < x] ++ inversiones xs

-- 2ª definición
-- =============

nInversiones2 :: Integer -> Int
nInversiones2 = aux . show
    where aux [] = 0
          aux (y:ys) | null xs   = aux ys
                     | otherwise = length xs + aux ys
                     where xs = [x | x <- ys, x < y]  

-- 3ª solución
-- ===========

nInversiones3 :: Integer -> Int
nInversiones3 x = sum $ map f xss
    where xss = init $ tails (show x)
          f (x:xs) = length $ filter (<x) xs

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    ghci> let f1000 = product [1..1000] 
--    ghci> nInversiones1 f1000
--    1751225
--    (2.81 secs, 452526504 bytes)
--    ghci> nInversiones2 f1000
--    1751225
--    (2.45 secs, 312752672 bytes)
--    ghci> nInversiones3 f1000
--    1751225
--    (0.71 secs, 100315896 bytes)

import Data.List (tails)

-- 1ª definición

-- =============

nInversiones1 :: Integer -> Int

nInversiones1 = length . inversiones . show

-- (inversiones xs) es la lista de las inversiones de xs. Por ejemplo,

-- inversiones "1745" == [('7','4'),('7','5')]

-- inversiones "cbafd" == [('c','b'),('c','a'),('b','a'),('f','d')]

inversiones :: Ord a => [a] -> [(a,a)]

inversiones [] = []

inversiones (x:xs) = [(x,y) | y <- xs, y < x] ++ inversiones xs

-- 2ª definición

-- =============

nInversiones2 :: Integer -> Int

nInversiones2 = aux . show

where aux [] = 0

aux (y:ys) | null xs = aux ys

| otherwise = length xs + aux ys

where xs = [x | x <- ys, x < y]

-- 3ª solución

-- ===========

nInversiones3 :: Integer -> Int

nInversiones3 x = sum $ map f xss

where xss = init $ tails (show x)

f (x:xs) = length $ filter (<x) xs

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- ghci> let f1000 = product [1..1000]

-- ghci> nInversiones1 f1000

-- 1751225

-- (2.81 secs, 452526504 bytes)

-- ghci> nInversiones2 f1000

-- 1751225

-- (2.45 secs, 312752672 bytes)

-- ghci> nInversiones3 f1000

-- 1751225

-- (0.71 secs, 100315896 bytes)

Números comenzando con un dígito dado

PorJosé A. Alonso 22-mayo-201513-junio-2015

Definir la función

   comienzanCon :: [Int] -> Int -> [Int]

1	comienzanCon :: [Int] -> Int -> [Int]

tal que (comienzanCon xs d) es la lista de los elementos de xs que empiezan por el dígito d. Por ejemplo,

   comienzanCon [123,51,11,711,52] 1 == [123,11]
   comienzanCon [123,51,11,711,52] 5 == [51,52]
   comienzanCon [123,51,11,711,52] 6 == []

comienzanCon [123,51,11,711,52] 1 == [123,11]

comienzanCon [123,51,11,711,52] 5 == [51,52]

comienzanCon [123,51,11,711,52] 6 == []

Soluciones

import Data.Char (intToDigit)

-- 1ª definición (por comprensión)
comienzanCon :: [Int]-> Int -> [Int]
comienzanCon xs d = [x | x <- xs, head (show x) == d']
    where d' = head (show d)

-- 2ª definición (por recursión)
comienzanCon2 :: [Int]-> Int -> [Int]
comienzanCon2 xs d = aux xs
    where aux [] = []
          aux (x:xs) | head (show x) == d' = x : aux xs
                     | otherwise           = aux xs
          d' = head (show d)

-- 3ª definición (por filtrado)
comienzanCon3 :: [Int]-> Int -> [Int]
comienzanCon3 xs d = filter (\x -> head (show x) == d') xs
    where d' = head (show d)

-- 4ª definición (por plegado)
comienzanCon4 :: [Int]-> Int -> [Int]
comienzanCon4 xs d = foldr f [] xs
    where f x ys | head (show x) == d' = x : ys
                 | otherwise           = ys
          d' = head (show d)

-- En las definiciones anteriores se puede usa intToDigit en lugar de
-- read. 

comienzanCon' :: [Int]-> Int -> [Int]
comienzanCon' xs d = [x | x <- xs, head (show x) == intToDigit d]

comienzanCon2' :: [Int]-> Int -> [Int]
comienzanCon2' xs d = aux xs
    where aux [] = []
          aux (x:xs) | head (show x) == intToDigit d = x : aux xs
                     | otherwise                     = aux xs

comienzanCon3' :: [Int]-> Int -> [Int]
comienzanCon3' xs d = filter ((==intToDigit d) . head . show) xs

comienzanCon4' :: [Int]-> Int -> [Int]
comienzanCon4' xs d = foldr f [] xs
    where f x ys | head (show x) == intToDigit d = x : ys
                 | otherwise                     = ys

import Data.Char (intToDigit)

-- 1ª definición (por comprensión)

comienzanCon :: [Int]-> Int -> [Int]

comienzanCon xs d = [x | x <- xs, head (show x) == d']

where d' = head (show d)

-- 2ª definición (por recursión)

comienzanCon2 :: [Int]-> Int -> [Int]

comienzanCon2 xs d = aux xs

where aux [] = []

aux (x:xs) | head (show x) == d' = x : aux xs

| otherwise = aux xs

d' = head (show d)

-- 3ª definición (por filtrado)

comienzanCon3 :: [Int]-> Int -> [Int]

comienzanCon3 xs d = filter (\x -> head (show x) == d') xs

where d' = head (show d)

-- 4ª definición (por plegado)

comienzanCon4 :: [Int]-> Int -> [Int]

comienzanCon4 xs d = foldr f [] xs

where f x ys | head (show x) == d' = x : ys

| otherwise = ys

d' = head (show d)

-- En las definiciones anteriores se puede usa intToDigit en lugar de

-- read.

comienzanCon' :: [Int]-> Int -> [Int]

comienzanCon' xs d = [x | x <- xs, head (show x) == intToDigit d]

comienzanCon2' :: [Int]-> Int -> [Int]

comienzanCon2' xs d = aux xs

where aux [] = []

aux (x:xs) | head (show x) == intToDigit d = x : aux xs

| otherwise = aux xs

comienzanCon3' :: [Int]-> Int -> [Int]

comienzanCon3' xs d = filter ((==intToDigit d) . head . show) xs

comienzanCon4' :: [Int]-> Int -> [Int]

comienzanCon4' xs d = foldr f [] xs

where f x ys | head (show x) == intToDigit d = x : ys

| otherwise = ys

Refinamiento de montículos

Soluciones

Cálculo de aprobados

Soluciones

Reparto de escaños por la ley d’Hont

Soluciones

Inversiones de un número

Soluciones

Números comenzando con un dígito dado

Soluciones

Entradas recientes

Buscar

Correo electrónico