mayo 2015 – Exercitium

Matrices latinas

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

Una matriz latina de orden n es una matriz cuadrada de orden n tal que todos sus elementos son cero salvo los de su fila y columna central, si n es impar; o los de sus dos filas y columnas centrales, si n es par.

Definir la función

   latina :: Int -> Array (Int,Int) Int

1	latina :: Int -> Array (Int,Int) Int

tal que (latina n) es la siguiente matriz latina de orden n:

Para n impar:

     | 0  0... 0 1   0 ... 0   0|
     | 0  0... 0 2   0 ... 0   0|
     | 0  0... 0 3   0 ... 0   0|
     | .........................|
     | 1  2..............n-1   n|
     | .........................|
     | 0  0... 0 n-2 0 ... 0   0|
     | 0  0... 0 n-1 0 ... 0   0|
     | 0  0... 0 n   0 ... 0   0|

| 0 0... 0 1 0 ... 0 0|

| 0 0... 0 2 0 ... 0 0|

| 0 0... 0 3 0 ... 0 0|

| .........................|

| 1 2..............n-1 n|

| .........................|

| 0 0... 0 n-2 0 ... 0 0|

| 0 0... 0 n-1 0 ... 0 0|

| 0 0... 0 n 0 ... 0 0|

Para n par:

     | 0  0... 0 1   n    0 ...   0   0|
     | 0  0... 0 2   n-1  0 ...   0   0|
     | 0  0... 0 3   n-2  0 ...   0   0|
     | ................................|
     | 1  2.....................n-1   n|
     | n n-1 .................... 2   1|
     | ................................|
     | 0  0... 0 n-2  3   0 ...   0   0|
     | 0  0... 0 n-1  2   0 ...   0   0|
     | 0  0... 0 n    1   0 ...   0   0|

| 0 0... 0 1 n 0 ... 0 0|

| 0 0... 0 2 n-1 0 ... 0 0|

| 0 0... 0 3 n-2 0 ... 0 0|

| ................................|

| 1 2.....................n-1 n|

| n n-1 .................... 2 1|

| ................................|

| 0 0... 0 n-2 3 0 ... 0 0|

| 0 0... 0 n-1 2 0 ... 0 0|

| 0 0... 0 n 1 0 ... 0 0|

Por ejemplo,

   ghci> elems (latina 5)
   [0,0,1,0,0,
    0,0,2,0,0,
    1,2,3,4,5,
    0,0,4,0,0,
    0,0,5,0,0]
   ghci> elems (latina 6)
   [0,0,1,6,0,0,
    0,0,2,5,0,0,
    1,2,3,4,5,6,
    6,5,4,3,2,1,
    0,0,5,2,0,0,
    0,0,6,1,0,0]

ghci> elems (latina 5)

[0,0,1,0,0,

0,0,2,0,0,

1,2,3,4,5,

0,0,4,0,0,

0,0,5,0,0]

ghci> elems (latina 6)

[0,0,1,6,0,0,

0,0,2,5,0,0,

1,2,3,4,5,6,

6,5,4,3,2,1,

0,0,5,2,0,0,

0,0,6,1,0,0]

Soluciones

latina :: Int -> Array (Int,Int) Int
latina n | even n    = latinaPar n
         | otherwise = latinaImpar n

-- (latinaImpar n) es la matriz latina de orden n, siendo n un número
-- impar. Por ejemplo,
--    ghci> elems (latinaImpar 5)
--    [0,0,1,0,0,
--     0,0,2,0,0,
--     1,2,3,4,5,
--     0,0,4,0,0,
--     0,0,5,0,0]
latinaImpar :: Int -> Array (Int,Int) Int
latinaImpar n = 
    array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
    where c = 1 + (n `div` 2)
          f i j | i == c    = j
                | j == c    = i 
                | otherwise = 0 

-- (latinaPar n) es la matriz latina de orden n, siendo n un número
-- par. Por ejemplo,
--    ghci> elems (latinaPar 6)
--    [0,0,1,6,0,0,
--     0,0,2,5,0,0,
--     1,2,3,4,5,6,
--     6,5,4,3,2,1,
--     0,0,5,2,0,0,
--     0,0,6,1,0,0]
latinaPar :: Int -> Array (Int,Int) Int
latinaPar n = 
    array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
    where c = n `div` 2
          f i j | i == c    = j
                | i == c+1  = n-j+1
                | j == c    = i
                | j == c+1  = n-i+1
                | otherwise = 0

latina :: Int -> Array (Int,Int) Int

latina n | even n = latinaPar n

| otherwise = latinaImpar n

-- (latinaImpar n) es la matriz latina de orden n, siendo n un número

-- impar. Por ejemplo,

-- ghci> elems (latinaImpar 5)

-- [0,0,1,0,0,

-- 0,0,2,0,0,

-- 1,2,3,4,5,

-- 0,0,4,0,0,

-- 0,0,5,0,0]

latinaImpar :: Int -> Array (Int,Int) Int

latinaImpar n =

array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]

where c = 1 + (n `div` 2)

f i j | i == c = j

| j == c = i

| otherwise = 0

-- (latinaPar n) es la matriz latina de orden n, siendo n un número

-- par. Por ejemplo,

-- ghci> elems (latinaPar 6)

-- [0,0,1,6,0,0,

-- 0,0,2,5,0,0,

-- 1,2,3,4,5,6,

-- 6,5,4,3,2,1,

-- 0,0,5,2,0,0,

-- 0,0,6,1,0,0]

latinaPar :: Int -> Array (Int,Int) Int

latinaPar n =

array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]

where c = n `div` 2

f i j | i == c = j

| i == c+1 = n-j+1

| j == c = i

| j == c+1 = n-i+1

| otherwise = 0

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

Matrices marco y transiciones

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

Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.

Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.

Definir las funciones

   marco      :: Int -> Int -> Integer -> Matrix Integer
   paso       :: Matrix Integer -> Matrix Integer
   itPasos    :: Int -> Matrix Integer -> Matrix Integer
   pasosHasta :: Integer -> Int

marco :: Int -> Int -> Integer -> Matrix Integer

paso :: Matrix Integer -> Matrix Integer

itPasos :: Int -> Matrix Integer -> Matrix Integer

pasosHasta :: Integer -> Int

tales que

(marco m n z) genera la matriz de dimensión mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones interiores. Por ejemplo,

     ghci> marco 5 5 1
     ( 1 1 1 1 1 )
     ( 1 0 0 0 1 )
     ( 1 0 0 0 1 )
     ( 1 0 0 0 1 )
     ( 1 1 1 1 1 )

ghci> marco 5 5 1

( 1 1 1 1 1 )

( 1 0 0 0 1 )

( 1 1 1 1 1 )

(paso t) calcula la matriz generada tras aplicar un paso de transición a la matriz t. Por ejemplo,

     ghci> paso (marco 5 5 1)
     ( 1 1 1 1 1 )
     ( 1 5 3 5 1 )
     ( 1 3 0 3 1 )
     ( 1 5 3 5 1 )
     ( 1 1 1 1 1 )

ghci> paso (marco 5 5 1)

( 1 1 1 1 1 )

( 1 5 3 5 1 )

( 1 3 0 3 1 )

( 1 5 3 5 1 )

( 1 1 1 1 1 )

(itPasos k t) es la matriz obtenida tras aplicar k pasos de transición a partir de la matriz t. Por ejemplo,

     ghci> itPasos 10 (marco 5 5 1)
     (       1       1       1       1       1 )
     (       1 4156075 5878783 4156075       1 )
     (       1 5878783 8315560 5878783       1 )
     (       1 4156075 5878783 4156075       1 )
     (       1       1       1       1       1 )

ghci> itPasos 10 (marco 5 5 1)

( 1 1 1 1 1 )

( 1 4156075 5878783 4156075 1 )

( 1 5878783 8315560 5878783 1 )

( 1 4156075 5878783 4156075 1 )

( 1 1 1 1 1 )

(pasosHasta k) es el número de pasos de transición a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo,

     pasosHasta 4         ==  1
     pasosHasta 6         ==  2
     pasosHasta (2^2015)  ==  887

pasosHasta 4 == 1

pasosHasta 6 == 2

pasosHasta (2^2015) == 887

Soluciones

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z  = matrix m n f
    where f (i,j) | frontera m n (i,j) = z
                  | otherwise          = 0 

-- (frontera m n (i,j)) se verifica si (i,j) es una posición de la
-- frontera de las matrices de dimensión mxn.
frontera :: Int -> Int -> (Int,Int) -> Bool
frontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]

paso :: Matrix Integer -> Matrix Integer
paso p = matrix m n f where
    m = nrows p
    n = ncols p
    f (i,j) 
        | frontera m n (i,j) = p!(i,j)
        | otherwise          = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]
    
-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del
-- punto interior (i,j) en las matrices de dimensión mxn.
vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]
vecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]
                           , b <- [j-1..j+1]
                           , (a,b) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer 
itPasos k t = (iterate paso t) !! k 

pasosHasta :: Integer -> Int
pasosHasta k =
    length (takeWhile (\t -> menores t k) (iterate paso (marco 5 5 1)))

-- (menores p k) se verifica si los elementos de p son menores o
-- iguales que k. Por ejemplo, 
--    menores (itPasos 1 (marco 5 5 1)) 6  ==  True
--    menores (itPasos 1 (marco 5 5 1)) 4  ==  False
menores :: Matrix Integer -> Integer -> Bool
menores p k = all (<=k) (toList p)

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer

marco m n z = matrix m n f

where f (i,j) | frontera m n (i,j) = z

| otherwise = 0

-- (frontera m n (i,j)) se verifica si (i,j) es una posición de la

-- frontera de las matrices de dimensión mxn.

frontera :: Int -> Int -> (Int,Int) -> Bool

frontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]

paso :: Matrix Integer -> Matrix Integer

paso p = matrix m n f where

m = nrows p

n = ncols p

f (i,j)

| frontera m n (i,j) = p!(i,j)

| otherwise = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]

-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del

-- punto interior (i,j) en las matrices de dimensión mxn.

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

vecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]

, b <- [j-1..j+1]

, (a,b) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer

itPasos k t = (iterate paso t) !! k

pasosHasta :: Integer -> Int

pasosHasta k =

length (takeWhile (\t -> menores t k) (iterate paso (marco 5 5 1)))

-- (menores p k) se verifica si los elementos de p son menores o

-- iguales que k. Por ejemplo,

-- menores (itPasos 1 (marco 5 5 1)) 6 == True

-- menores (itPasos 1 (marco 5 5 1)) 4 == False

menores :: Matrix Integer -> Integer -> Bool

menores p k = all (<=k) (toList p)

Parte par de un polinomio

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

La parte par de un polinomio de coeficientes enteros es el polinomio formado por sus monomios cuyos coeficientes son números pares. Por ejemplo, la parte par de 4x^3+x^2-7x+6 es 4x^3+6.

Definir la función

   partePar :: Integral a => Polinomio a -> Polinomio a

1	partePar :: Integral a => Polinomio a -> Polinomio a

tal que (partePar p) es la parte par de p. Por ejemplo,

   ghci> partePar (consPol 3 4 (consPol 2 1 (consPol 0 6 polCero)))
   4*x^3 + 6

1 2	ghci> partePar (consPol 3 4 (consPol 2 1 (consPol 0 6 polCero))) 4*x^3 + 6

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

partePar :: Integral a => Polinomio a -> Polinomio a
partePar p
    | esPolCero p = polCero
    | even b      = consPol n b (partePar r)
    | otherwise   = partePar r
    where n = grado p
          b = coefLider p
          r = restoPol p

partePar :: Integral a => Polinomio a -> Polinomio a

partePar p

| esPolCero p = polCero

| even b = consPol n b (partePar r)

| otherwise = partePar r

where n = grado p

b = coefLider p

r = restoPol p

Aplicación de funciones a nodos y hojas

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

Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato

   data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

1	data Arbol a = H a \| N a (Arbol a) (Arbol a) deriving Show

Definir la función

   aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a

1	aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a

tal que (aplica f g a) devuelve el árbol obtenido al aplicar la función f a las hojas del árbol a y la función g a los nodos interiores. Por ejemplo,

   ghci> aplica (+1)(*2) (N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2)))
   N 10 (N 4 (H 2) (H 3)) (N 6 (H 5) (H 3))

1 2	ghci> aplica (+1)(*2) (N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))) N 10 (N 4 (H 2) (H 3)) (N 6 (H 5) (H 3))

Soluciones

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a
aplica f g (H x)     = H (f x)
aplica f g (N x i d) = N (g x) (aplica f g i) (aplica f g d)

data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show

aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a

aplica f g (H x) = H (f x)

aplica f g (N x i d) = N (g x) (aplica f g i) (aplica f g d)

Ciclos de un grafo

PorJosé A. Alonso 18-mayo-201526-marzo-2022

Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),…,v(n)] de nodos de G tal que:

(v(1),v(2)), (v(2),v(3)), (v(3),v(4)), …, (v(n-1),v(n)) son aristas de G,
v(1) = v(n), y
salvo v(1) = v(n), todos los v(i) son distintos entre sí.

Definir la función

   ciclos :: Grafo Int Int -> [[Int]]

1	ciclos :: Grafo Int Int -> [[Int]]

tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por

   g1, g2 :: Grafo Int Int
   g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]
   g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]

g1, g2 :: Grafo Int Int

g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]

g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]

entonces

   ciclos g1  ==  [[1,2,4,1],[2,4,1,2],[4,1,2,4]]
   ciclos g2  ==  [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]

1 2	ciclos g1 == [[1,2,4,1],[2,4,1,2],[4,1,2,4]] ciclos g2 == [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

import Data.List (nub, subsequences, permutations, sort)
import I1M.Grafo

-- 1ª definición (por fuerza bruta)
-- ================================

ciclos1 :: Grafo Int Int -> [[Int]]
ciclos1 g = 
    sort [ys | (x:xs) <- concatMap permutations (subsequences (nodos g)) 
             , let ys = (x:xs) ++ [x]
             , esCiclo ys g]

-- (esCiclo vs g) se verifica si vs es un ciclo en el grafo g. Por
-- ejemplo, 
esCiclo :: [Int] -> Grafo Int Int -> Bool
esCiclo vs g = 
    all (aristaEn g) (zip vs (tail vs)) &&
    head vs == last vs &&
    length (nub vs) == length vs - 1    

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

ciclos2 :: Grafo Int Int -> [[Int]]
ciclos2 g = sort [ys | (x:xs) <- caminos g
                     , let ys = (x:xs) ++ [x]
                     , esCiclo ys g]

-- (caminos g) es la lista de los caminos en el grafo g. Por ejemplo,
--    caminos g1  ==  [[1,2,3],[1,2,4],[2,3],[2,4,1],[3],[4,1,2,3]]
caminos :: Grafo Int Int -> [[Int]]
caminos g = concatMap (caminosDesde g) (nodos g)

-- (caminosDesde g v) es la lista de los caminos en el grafo g a partir
-- del vértice v. Por ejemplo,
--    caminosDesde g1 1  ==  [[1],[1,2],[1,2,3],[1,2,4]]
--    caminosDesde g1 2  ==  [[2],[2,3],[2,4],[2,4,1]]
--    caminosDesde g1 3  ==  [[3]]
--    caminosDesde g1 4  ==  [[4],[4,1],[4,1,2],[4,1,2,3]]
caminosDesde :: Grafo Int Int -> Int -> [[Int]]
caminosDesde g v = 
    map (reverse . fst) $
    concat $ 
    takeWhile (not.null) (iterate (concatMap sucesores) [([v],[v])])
    where sucesores (x:xs,ys) = [(z:x:xs,z:ys) | z <- adyacentes g x
                                               , z `notElem` ys]

-- 3ª solución (Pedro Martín)
-- ==========================

ciclos3 :: Grafo Int Int -> [[Int]]
ciclos3 g = concat [aux [n] (adyacentes g n) | n <- nodos g] where 
    aux _ [] = []
    aux xs (y:ys)
        | notElem y xs = aux (xs ++ [y]) (adyacentes g y) ++ aux xs ys
        | y == head xs = (xs ++ [y]) : aux xs ys
        | otherwise    = aux xs ys

-- 4ª solución (Chema Cortés)
-- ==========================

ciclos4 :: Grafo Int Int -> [[Int]]
ciclos4 g = concat [ caminos a a [] | a <- nodos g ] where
    -- caminos posibles de b hasta a, sin pasar dos veces por un mismo nodo
    caminos a b vs
        | a == b && (not.null) vs = [[b]]
        | otherwise = [ b:xs | c <- adyacentes g b
                             , c `notElem` vs
                             , xs <- caminos a c (c:vs)]

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

-- ghci> let ejemplo n = creaGrafo D (1,n) ((n,1,0) : [(i,i+1,0) | i <- [1..n-1]])
-- 
-- ghci> length (ciclos1 (ejemplo 9))
-- 9
-- (4.92 secs, 1371229152 bytes)
--
-- ghci> length (ciclos2 (ejemplo 9))
-- 9
-- (0.01 secs, 2577736 bytes)
-- 
-- ghci> length (ciclos3 (ejemplo 9))
-- 9
-- (0.01 secs, 1038932 bytes)
-- 
-- ghci> length (ciclos4 (ejemplo 9))
-- 9
-- (0.01 secs, 2589288 bytes)
-- 
-- ghci> length (ciclos2 (ejemplo 400))
-- 400
-- (11.74 secs, 5148997000 bytes)
-- 
-- ghci> length (ciclos3 (ejemplo 400))
-- 400
-- (4.99 secs, 936520100 bytes)
-- 
-- ghci> length (ciclos4 (ejemplo 400))
-- 400
-- (1.56 secs, 66701772 bytes)

100

101

102

import Data.List (nub, subsequences, permutations, sort)

import I1M.Grafo

-- 1ª definición (por fuerza bruta)

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

ciclos1 :: Grafo Int Int -> [[Int]]

ciclos1 g =

sort [ys | (x:xs) <- concatMap permutations (subsequences (nodos g))

, let ys = (x:xs) ++ [x]

, esCiclo ys g]

-- (esCiclo vs g) se verifica si vs es un ciclo en el grafo g. Por

-- ejemplo,

esCiclo :: [Int] -> Grafo Int Int -> Bool

esCiclo vs g =

all (aristaEn g) (zip vs (tail vs)) &&

head vs == last vs &&

length (nub vs) == length vs - 1

-- 2ª definición

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

ciclos2 :: Grafo Int Int -> [[Int]]

ciclos2 g = sort [ys | (x:xs) <- caminos g

, let ys = (x:xs) ++ [x]

, esCiclo ys g]

-- (caminos g) es la lista de los caminos en el grafo g. Por ejemplo,

-- caminos g1 == [[1,2,3],[1,2,4],[2,3],[2,4,1],[3],[4,1,2,3]]

caminos :: Grafo Int Int -> [[Int]]

caminos g = concatMap (caminosDesde g) (nodos g)

-- (caminosDesde g v) es la lista de los caminos en el grafo g a partir

-- del vértice v. Por ejemplo,

-- caminosDesde g1 1 == [[1],[1,2],[1,2,3],[1,2,4]]

-- caminosDesde g1 2 == [[2],[2,3],[2,4],[2,4,1]]

-- caminosDesde g1 3 == [[3]]

-- caminosDesde g1 4 == [[4],[4,1],[4,1,2],[4,1,2,3]]

caminosDesde :: Grafo Int Int -> Int -> [[Int]]

caminosDesde g v =

map (reverse . fst) $

concat $

takeWhile (not.null) (iterate (concatMap sucesores) [([v],[v])])

where sucesores (x:xs,ys) = [(z:x:xs,z:ys) | z <- adyacentes g x

, z `notElem` ys]

-- 3ª solución (Pedro Martín)

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

ciclos3 :: Grafo Int Int -> [[Int]]

ciclos3 g = concat [aux [n] (adyacentes g n) | n <- nodos g] where

aux _ [] = []

aux xs (y:ys)

| notElem y xs = aux (xs ++ [y]) (adyacentes g y) ++ aux xs ys

| y == head xs = (xs ++ [y]) : aux xs ys

| otherwise = aux xs ys

-- 4ª solución (Chema Cortés)

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

ciclos4 :: Grafo Int Int -> [[Int]]

ciclos4 g = concat [ caminos a a [] | a <- nodos g ] where

-- caminos posibles de b hasta a, sin pasar dos veces por un mismo nodo

caminos a b vs

| a == b && (not.null) vs = [[b]]

| otherwise = [ b:xs | c <- adyacentes g b

, c `notElem` vs

, xs <- caminos a c (c:vs)]

-- Comparación de eficiencia

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

-- ghci> let ejemplo n = creaGrafo D (1,n) ((n,1,0) : [(i,i+1,0) | i <- [1..n-1]])

-- ghci> length (ciclos1 (ejemplo 9))

-- 9

-- (4.92 secs, 1371229152 bytes)

-- ghci> length (ciclos2 (ejemplo 9))

-- 9

-- (0.01 secs, 2577736 bytes)

-- ghci> length (ciclos3 (ejemplo 9))

-- 9

-- (0.01 secs, 1038932 bytes)

-- ghci> length (ciclos4 (ejemplo 9))

-- 9

-- (0.01 secs, 2589288 bytes)

-- ghci> length (ciclos2 (ejemplo 400))

-- 400

-- (11.74 secs, 5148997000 bytes)

-- ghci> length (ciclos3 (ejemplo 400))

-- 400

-- (4.99 secs, 936520100 bytes)

-- ghci> length (ciclos4 (ejemplo 400))

-- 400

-- (1.56 secs, 66701772 bytes)

Números alternados

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

Decimos que un número es alternado si no tiene dos cifras consecutivas iguales ni tres cifras consecutivas en orden creciente no estricto o decreciente no estricto. Por ejemplo, los números 132425 y 92745 son alternados, pero los números 12325 y 29778 no. Las tres primeras cifras de 12325 están en orden creciente y 29778 tiene dos cifras iguales consecutivas.

Definir la constante

   alternados :: [Integer]

1	alternados :: [Integer]

cuyo valor es la lista infinita de los números alternados. Por ejemplo,

   take 10 alternados                      ==  [0,1,2,3,4,5,6,7,8,9]
   length (takeWhile (< 1000) alternados)  ==  616
   alternados !! 1234567                   ==  19390804

take 10 alternados == [0,1,2,3,4,5,6,7,8,9]

length (takeWhile (< 1000) alternados) == 616

alternados !! 1234567 == 19390804

Soluciones

import Data.Char (digitToInt)

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

-- (cifras n) es la lista de las cifras de n. Por ejemplo.
--    cifras 325  ==  [3,2,5]
cifras :: Integer -> [Int]
cifras n = map digitToInt (show n)

-- (cifrasAlternadas xs) se verifica si las lista de cifras xs es
-- alternada. Por ejemplo,
--    cifrasAlternadas [1,3,2,4,2,5]  ==  True
--    cifrasAlternadas [9,2,7,4,5]    ==  True
--    cifrasAlternadas [1,2,3,2,5]    ==  False
--    cifrasAlternadas [2,9,7,7,8]    ==  False
cifrasAlternadas :: [Int] -> Bool
cifrasAlternadas [x1,x2] = x1 /= x2
cifrasAlternadas (x1:x2:x3:xs) =
    not (((x1 <= x2) && (x2 <= x3)) || ((x1 >= x2) && (x2 >= x3))) &&
    cifrasAlternadas (x2:x3:xs)
cifrasAlternadas _ = True

-- (alternado n) se verifica si n es un número alternado. Por ejemplo,
--    alternado 132425  ==  True
--    alternado 92745   ==  True
--    alternado 12325   ==  False
--    alternado 29778   ==  False
alternado :: Integer -> Bool
alternado n = cifrasAlternadas (cifras n)

alternados1 :: [Integer]
alternados1 = filter alternado [0..]

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

-- (extiendeAlternado n) es la lista de números alternados que se pueden
-- obtener añadiendo una cifra al final del número alternado n. Por
-- ejemplo,
--    extiendeAlternado 7   ==  [70,71,72,73,74,75,76,78,79]
--    extiendeAlternado 24  ==  [240,241,242,243]
--    extiendeAlternado 42  ==  [423,424,425,426,427,428,429]
extiendeAlternado :: Integer -> [Integer]
extiendeAlternado n 
    | n < 10    = [n*10+h | h <- [0..n-1]++[n+1..9]]
    | d < c     = [n*10+h | h <- [0..c-1]]
    | otherwise = [n*10+h | h <- [c+1..9]]
    where c = n `mod` 10
          d = (n `mod` 100) `div` 10

alternados2 :: [Integer]
alternados2 = concat (iterate (concatMap extiendeAlternado) [0])

import Data.Char (digitToInt)

-- 1ª definición

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

-- (cifras n) es la lista de las cifras de n. Por ejemplo.

-- cifras 325 == [3,2,5]

cifras :: Integer -> [Int]

cifras n = map digitToInt (show n)

-- (cifrasAlternadas xs) se verifica si las lista de cifras xs es

-- alternada. Por ejemplo,

-- cifrasAlternadas [1,3,2,4,2,5] == True

-- cifrasAlternadas [9,2,7,4,5] == True

-- cifrasAlternadas [1,2,3,2,5] == False

-- cifrasAlternadas [2,9,7,7,8] == False

cifrasAlternadas :: [Int] -> Bool

cifrasAlternadas [x1,x2] = x1 /= x2

cifrasAlternadas (x1:x2:x3:xs) =

not (((x1 <= x2) && (x2 <= x3)) || ((x1 >= x2) && (x2 >= x3))) &&

cifrasAlternadas (x2:x3:xs)

cifrasAlternadas _ = True

-- (alternado n) se verifica si n es un número alternado. Por ejemplo,

-- alternado 132425 == True

-- alternado 92745 == True

-- alternado 12325 == False

-- alternado 29778 == False

alternado :: Integer -> Bool

alternado n = cifrasAlternadas (cifras n)

alternados1 :: [Integer]

alternados1 = filter alternado [0..]

-- 2ª definición

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

-- (extiendeAlternado n) es la lista de números alternados que se pueden

-- obtener añadiendo una cifra al final del número alternado n. Por

-- ejemplo,

-- extiendeAlternado 7 == [70,71,72,73,74,75,76,78,79]

-- extiendeAlternado 24 == [240,241,242,243]

-- extiendeAlternado 42 == [423,424,425,426,427,428,429]

extiendeAlternado :: Integer -> [Integer]

extiendeAlternado n

| n < 10 = [n*10+h | h <- [0..n-1]++[n+1..9]]

| d < c = [n*10+h | h <- [0..c-1]]

| otherwise = [n*10+h | h <- [c+1..9]]

where c = n `mod` 10

d = (n `mod` 100) `div` 10

alternados2 :: [Integer]

alternados2 = concat (iterate (concatMap extiendeAlternado) [0])

Visibilidad de listas y matrices

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

La visibilidad de una lista es el número de elementos que son estrictamente mayores que todos los anteriores. Por ejemplo, la visibilidad de la lista [1,2,5,2,3,6] es 4.

La visibilidad de una matriz P es el par formado por las visibilidades de las filas de P y las visibilidades de las columnas de P. Por ejemplo, dada la matriz

       ( 4 2 1 )
   Q = ( 3 2 5 )
       ( 6 1 8 )

( 4 2 1 )

Q = ( 3 2 5 )

( 6 1 8 )

la visibilidad de Q es ([1,2,2],[2,1,3]).

Definir las funciones

   visibilidadLista  :: [Int] -> Int
   visibilidadMatriz :: Matrix Int -> ([Int],[Int])

1 2	visibilidadLista :: [Int] -> Int visibilidadMatriz :: Matrix Int -> ([Int],[Int])

tales que

(visibilidadLista xs) es la visibilidad de la lista xs. Por ejemplo,

     visibilidadLista [1,2,5,2,3,6]   ==  4
     visibilidadLista [0,-2,5,1,6,6]  ==  3

1 2	visibilidadLista [1,2,5,2,3,6] == 4 visibilidadLista [0,-2,5,1,6,6] == 3

(visibilidadMatriz p) es la visibilidad de la matriz p. Por ejemplo,

     ghci> visibilidadMatriz (fromLists [[4,2,1],[3,2,5],[6,1,8]])
     ([1,2,2],[2,1,3])
     ghci> visibilidadMatriz (fromLists [[0,2,1],[0,2,5],[6,1,8]])
     ([2,3,2],[2,1,3])

ghci> visibilidadMatriz (fromLists [[4,2,1],[3,2,5],[6,1,8]])

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

ghci> visibilidadMatriz (fromLists [[0,2,1],[0,2,5],[6,1,8]])

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

Soluciones

import Data.List (inits)
import Data.Matrix (Matrix, (!), nrows, ncols, fromLists)

visibilidadLista :: [Int] -> Int
visibilidadLista xs =
    length [x | (ys,x) <- zip (inits xs) xs, all (<x) ys]

visibilidadMatriz :: Matrix Int -> ([Int],[Int])
visibilidadMatriz p =
    ([visibilidadLista [p ! (i,j) | j <- [1..n]] | i <- [1..m]],
     [visibilidadLista [p ! (i,j) | i <- [1..m]] | j <- [1..n]])
     where m = nrows p
           n = ncols p

import Data.List (inits)

import Data.Matrix (Matrix, (!), nrows, ncols, fromLists)

visibilidadLista :: [Int] -> Int

visibilidadLista xs =

length [x | (ys,x) <- zip (inits xs) xs, all (<x) ys]

visibilidadMatriz :: Matrix Int -> ([Int],[Int])

visibilidadMatriz p =

([visibilidadLista [p ! (i,j) | j <- [1..n]] | i <- [1..m]],

[visibilidadLista [p ! (i,j) | i <- [1..m]] | j <- [1..n]])

where m = nrows p

n = ncols p

Reconocimiento de camino en un grafo

PorJosé A. Alonso 13-mayo-201526-marzo-2022

Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),…,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos

   g1, g2 :: Grafo Int Int
   g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)]
   g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]

g1, g2 :: Grafo Int Int

g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)]

g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]

la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.

Definir la función

   camino :: Grafo Int Int -> [Int] -> Bool

1	camino :: Grafo Int Int -> [Int] -> Bool

tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,

   camino g1 [1,2,3]  ==  True
   camino g2 [1,2,3]  ==  False

1 2	camino g1 [1,2,3] == True camino g2 [1,2,3] == False

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

import I1M.Grafo 
camino :: Grafo Int Int -> [Int] -> Bool
camino g vs = all (aristaEn g) (zip vs (tail vs))

import I1M.Grafo

camino :: Grafo Int Int -> [Int] -> Bool

camino g vs = all (aristaEn g) (zip vs (tail vs))

El teorema de Midy

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

El ejercicio de hoy, propuesto por Antonio García Blázquez, tiene como objetivo comprobar la veracidad del Teorema de Midy, este teorema dice:

Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.

Por ejemplo, 2/7 = 0’285714285714… El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.

Definir la función

   teoremaMidy :: Integer -> Bool

1	teoremaMidy :: Integer -> Bool

tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural a menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,

   teoremaMidy 200  ==  True

1	teoremaMidy 200 == True

Además, comprobar el teorema de Midy usando QuickCheck.

Soluciones

import Data.List (genericTake)
import Data.Numbers.Primes (primes, isPrime)
import Test.QuickCheck

teoremaMidy :: Integer -> Bool
teoremaMidy n = 
    all conclusionMidy [(a,p) | p <- takeWhile (<n) (drop 3 primes),
                                a <- [1..p-1],
                                tienePeriodoDeLongitudPar (a,p)]

-- (tienePeriodoDeLongitudPar (a,p)) se verifica si el período de a/p
-- (con p un primo mayor que 5 y que a) es de longitud par. Por ejemplo,  
--    tienePeriodoDeLongitudPar (1,7)   ==  True
--    tienePeriodoDeLongitudPar (1,37)  ==  False
tienePeriodoDeLongitudPar :: (Integer,Integer) -> Bool
tienePeriodoDeLongitudPar (a,p) =
    even (longitudPeriodo p)

-- (expansionDec (a,p)) es la expansión decimal de a/p. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: (Integer,Integer) -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (longitudPeriodo p) es la longitud del período de 1/p (y de
-- cualquier fracción irreducible de denominador p), donde p es un
-- número primo mayor que 5. Por ejemplo, 
--    longitudPeriodo 7   ==  6
--    longitudPeriodo 37  ==  3
--    longitudPeriodo 83  ==  41
longitudPeriodo :: Integer -> Integer
longitudPeriodo p = head [k | k <- [1..], 10^k `mod` p == 1]

-- (periodo (a,p)) es el período de a/b (para a < p y p > 5 es primo). 
-- Por ejemplo, 
--    periodo (1,7)   ==  [1,4,2,8,5,7]
--    periodo (2,7)   ==  [2,8,5,7,1,4]
--    periodo (6,7)   ==  [8,5,7,1,4,2]
--    periodo (1,73)  ==  [0,1,3,6,9,8,6,3]
periodo :: (Integer,Integer) -> [Integer]
periodo (a,p) = genericTake t xs
    where (_:xs) = expansionDec (a,p)
          t      = longitudPeriodo p

-- (conclusionMidy (a,p)) se verifica si a/p verifica la conclusión del
-- teorema de Midy; es decir, podemos partir el período de a/p en dos
-- mitades, cuya suma es un número formado únicamente por nueves. Por
-- ejemplo,  
--    conclusionMidy (1,7)   ==  True
--    conclusionMidy (1,37)  ==  False
conclusionMidy :: (Integer,Integer) -> Bool
conclusionMidy (a,p) = 
    all (==9) (zipWith (+) ys zs)
    where xs      = periodo (a,p)
          (ys,zs) = splitAt (length xs `div` 2) xs

-- ---------------------------------------------------------------------
-- § Comprobación con QuickCheck                                      --
-- ---------------------------------------------------------------------

-- (condicionMidy (a,p)) se verifica si a/p cumple las condiciones del
-- teorema de Midy. Por ejemplo,
--    condicionMidy (1,7)   ==  True
--    condicionMidy (1,37)  ==  False
condicionMidy :: (Integer,Integer) -> Bool
condicionMidy (a,p) = 
    a > 0 && 
    a < p && 
    isPrime p && 
    p > 5 && 
    tienePeriodoDeLongitudPar (a,p)

-- La propiedad es 
prop_teoremaMidy :: (Integer,Integer) -> Property
prop_teoremaMidy (a,p) = 
    condicionMidy (a,p) ==> conclusionMidy (a,p)

-- La comprobación es 
--    ghci> quickCheck prop_teoremaMidy
--    *** Gave up! Passed only 24 tests.

-- En la comprobación se observa que la mayoría de los ejemplos
-- generados no cumplen la condición del teorema de Midy y sólo 24 de
-- ellos la cumplen y también la conclusión. 

-- Para aumentar el número de casos en lo que se cumpla la condición, se
-- puede aumentar el valor de maxSuccess; por ejemplo,   
--    ghci> quickCheckWith (stdArgs {maxSuccess=700}) prop_teoremaMidy
--    *** Gave up! Passed only 137 tests.

-- Otra forma de conseguirlo es definir un generador de números de Midy
-- (es decir, de pares (a,p) que cumplan la condición del teorema de
-- Midy). Por ejemplo, 
--    ghci> sample numeroMidy
--    (15,19)
--    (5,7)
--    (1,23)
--    (7,11)
numeroMidy :: Gen (Integer,Integer)
numeroMidy = suchThat arbitrary condicionMidy

-- La propiedad es
prop_teoremaMidy2 :: Property
prop_teoremaMidy2 = forAll numeroMidy conclusionMidy

-- La comprobación es
--    ghci> quickCheck prop_teoremaMidy2
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

import Data.List (genericTake)

import Data.Numbers.Primes (primes, isPrime)

import Test.QuickCheck

teoremaMidy :: Integer -> Bool

teoremaMidy n =

all conclusionMidy [(a,p) | p <- takeWhile (<n) (drop 3 primes),

a <- [1..p-1],

tienePeriodoDeLongitudPar (a,p)]

-- (tienePeriodoDeLongitudPar (a,p)) se verifica si el período de a/p

-- (con p un primo mayor que 5 y que a) es de longitud par. Por ejemplo,

-- tienePeriodoDeLongitudPar (1,7) == True

-- tienePeriodoDeLongitudPar (1,37) == False

tienePeriodoDeLongitudPar :: (Integer,Integer) -> Bool

tienePeriodoDeLongitudPar (a,p) =

even (longitudPeriodo p)

-- (expansionDec (a,p)) es la expansión decimal de a/p. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: (Integer,Integer) -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (longitudPeriodo p) es la longitud del período de 1/p (y de

-- cualquier fracción irreducible de denominador p), donde p es un

-- número primo mayor que 5. Por ejemplo,

-- longitudPeriodo 7 == 6

-- longitudPeriodo 37 == 3

-- longitudPeriodo 83 == 41

longitudPeriodo :: Integer -> Integer

longitudPeriodo p = head [k | k <- [1..], 10^k `mod` p == 1]

-- (periodo (a,p)) es el período de a/b (para a < p y p > 5 es primo).

-- Por ejemplo,

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (2,7) == [2,8,5,7,1,4]

-- periodo (6,7) == [8,5,7,1,4,2]

-- periodo (1,73) == [0,1,3,6,9,8,6,3]

periodo :: (Integer,Integer) -> [Integer]

periodo (a,p) = genericTake t xs

where (_:xs) = expansionDec (a,p)

t = longitudPeriodo p

-- (conclusionMidy (a,p)) se verifica si a/p verifica la conclusión del

-- teorema de Midy; es decir, podemos partir el período de a/p en dos

-- mitades, cuya suma es un número formado únicamente por nueves. Por

-- ejemplo,

-- conclusionMidy (1,7) == True

-- conclusionMidy (1,37) == False

conclusionMidy :: (Integer,Integer) -> Bool

conclusionMidy (a,p) =

all (==9) (zipWith (+) ys zs)

where xs = periodo (a,p)

(ys,zs) = splitAt (length xs `div` 2) xs

-- ---------------------------------------------------------------------

-- § Comprobación con QuickCheck --

-- ---------------------------------------------------------------------

-- (condicionMidy (a,p)) se verifica si a/p cumple las condiciones del

-- teorema de Midy. Por ejemplo,

-- condicionMidy (1,7) == True

-- condicionMidy (1,37) == False

condicionMidy :: (Integer,Integer) -> Bool

condicionMidy (a,p) =

a > 0 &&

a < p &&

isPrime p &&

p > 5 &&

tienePeriodoDeLongitudPar (a,p)

-- La propiedad es

prop_teoremaMidy :: (Integer,Integer) -> Property

prop_teoremaMidy (a,p) =

condicionMidy (a,p) ==> conclusionMidy (a,p)

-- La comprobación es

-- ghci> quickCheck prop_teoremaMidy

-- *** Gave up! Passed only 24 tests.

-- En la comprobación se observa que la mayoría de los ejemplos

-- generados no cumplen la condición del teorema de Midy y sólo 24 de

-- ellos la cumplen y también la conclusión.

-- Para aumentar el número de casos en lo que se cumpla la condición, se

-- puede aumentar el valor de maxSuccess; por ejemplo,

-- ghci> quickCheckWith (stdArgs {maxSuccess=700}) prop_teoremaMidy

-- *** Gave up! Passed only 137 tests.

-- Otra forma de conseguirlo es definir un generador de números de Midy

-- (es decir, de pares (a,p) que cumplan la condición del teorema de

-- Midy). Por ejemplo,

-- ghci> sample numeroMidy

-- (15,19)

-- (5,7)

-- (1,23)

-- (7,11)

numeroMidy :: Gen (Integer,Integer)

numeroMidy = suchThat arbitrary condicionMidy

-- La propiedad es

prop_teoremaMidy2 :: Property

prop_teoremaMidy2 = forAll numeroMidy conclusionMidy

-- La comprobación es

-- ghci> quickCheck prop_teoremaMidy2

-- +++ OK, passed 100 tests.

Representación decimal de números racionales

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

Continuando con los ejercicios propuestos por los alumnos, Antonio García Blázquez ha propuesto un ejercicio que usa el período de los números decimales. El ejercicio de hoy, basado en su propuesta, trata de la representación decimal de los números racionales.

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

6/2 = 3 se representa por (3,[],[])

1/2 = 0.5 se representa por (0,[5],[])

1/3 = 0.333333... se representa por (0,[],[3])

23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

1	type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

1	type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

1 2	decimal :: Racional -> Decimal racional :: Decimal -> Racional

tales que

(decimal r) es la representación decimal del número racional r. Por ejemplo,

        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

decimal (1,4) == (0,[2,5],[])

decimal (1,3) == (0,[],[3])

decimal (23,14) == (1,[6],[4,2,8,5,7,1])

(racional d) es el número racional cuya representación decimal es d. Por ejemplo,

        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

racional (0,[2,5],[]) == (1,4)

racional (0,[],[3]) == (1,3)

racional (1,[6],[4,2,8,5,7,1]) == (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

ghci> let (_,_,p) = decimal (23,14) in concatMap show p

"428571"

ghci> let (_,_,p) = decimal (1,47) in concatMap show p

"0212765957446808510638297872340425531914893617"

ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)

540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b. Por ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)

-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------

-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es 
--    ghci> quickCheck prop_RacionalDecimal
--    +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))

-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es
--   ghci> quickCheck prop_RacionalDecimal2
--   +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es
--   ghci> quickCheck prop_DecimalRacional
--   +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.List

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- § Tipos --

-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el

-- primer elemento es el numerador y el segundo el denominador.

type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte

-- entera, el segundo es el anteperíodo y el tercero es el período.

type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------

-- § De racional a decimal --

-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,

-- mayorExponente 2 40 == 3

-- mayorExponente 5 40 == 1

-- mayorExponente 5 41 == 0

mayorExponente :: Integer -> Integer -> Integer

mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudAnteperiodo 2 == 1

-- longitudAnteperiodo 3 == 0

-- longitudAnteperiodo 14 == 1

longitudAnteperiodo :: Integer -> Integer

longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudPeriodo 2 == 0

-- longitudPeriodo 3 == 1

-- longitudPeriodo 7 == 6

longitudPeriodo :: Integer -> Integer

longitudPeriodo n

| m == 1 = 0

| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]

where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: Racional -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,

-- parteEntera (125,3) == 41

parteEntera :: Racional -> Integer

parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de

-- cifras que se encuentran entre la parte entera y el primer período de

-- a/b. Por ejemplo,

-- antePeriodo (23,14) == [6]

-- antePeriodo (1,5) == [2]

antePeriodo :: Racional -> [Integer]

antePeriodo (a,b) = genericTake s (tail xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b. Por ejemplo,

-- periodo (1,3) == [3]

-- periodo (1,5) == []

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (23,14) == [4,2,8,5,7,1]

-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"

periodo :: Racional -> [Integer]

periodo (a,b) = genericTake t (genericDrop (1+s) xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

t = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por

-- ejemplo,

-- reducido (40,80) == (1,2)

reducido :: Racional -> Racional

reducido (a,b) = (a `div` m, b `div` m)

where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna

-- formada por la parte entera, la parte decimal pura y la parte decimal

-- periódica. Por ejemplo,

-- decimal (1,4) == (0,[2,5],[])

-- decimal (1,3) == (0,[],[3])

-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])

decimal :: Racional -> Decimal

decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)

where r = reducido (a,b)

-- ---------------------------------------------------------------------

-- § De decimal a racional --

-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de

-- dígitos xs. Por ejemplo,

-- digitosAnumero [3,2,5] == 325

digitosAnumero :: [Integer] -> Integer

digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]

where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación

-- decimal es (x,ys,zs). Por ejemplo,

-- racional (0,[2,5],[]) == (1,4)

-- racional (0,[],[3]) == (1,3)

-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)

racional :: Decimal -> Racional

racional (x,ys,[]) = reducido (a,b) where

a = digitosAnumero (x:ys)

b = 10^(length ys)

racional (x,ys,zs) = reducido (a,b) where

a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)

b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------

-- § Propiedades --

-- ---------------------------------------------------------------------

-- La 1ª propiedad es

prop_RacionalDecimal :: Racional -> Property

prop_RacionalDecimal (a,b) =

a >= 0 && b > 0 ==>

racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal

-- +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales

numeroRacional :: Gen Racional

numeroRacional = do a <- arbitrary

b <- arbitrary

return (reducido (abs a, 1+ abs b))

-- La propiedad es

prop_RacionalDecimal2 :: Property

prop_RacionalDecimal2 =

forAll numeroRacional

(\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal2

-- +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales

numeroDecimal :: Gen Decimal

numeroDecimal = do a <- arbitrary

b <- arbitrary

return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es

prop_DecimalRacional :: Property

prop_DecimalRacional =

forAll numeroDecimal

(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es

-- ghci> quickCheck prop_DecimalRacional

-- +++ OK, passed 100 tests.

Potencias de primos con exponentes potencias de dos

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

Se llaman potencias de Fermi-Dirac a los números de la forma p^(2^k), donde p es un número primo y k es un número natural.

Definir la sucesión

   potencias :: [Integer]

1	potencias :: [Integer]

cuyos términos sean las potencias de Fermi-Dirac 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 !! 60      ==  241
   potencias !! (10^6)  ==  15476303

take 14 potencias == [2,3,4,5,7,9,11,13,16,17,19,23,25,29]

potencias !! 60 == 241

potencias !! (10^6) == 15476303

Soluciones

import Data.Numbers.Primes (primes)

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

import Data.Numbers.Primes (primes)

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

Múltiplos especiales

PorJosé A. Alonso 7-mayo-201515-mayo-2015

Dado dos números n y m, decimos que m es un múltiplo especial de n si m es un múltiplo de n y m no tiene ningún factor primo que sea congruente con 1 módulo 3.

Definir la función

   multiplosEspecialesCota :: Int -> Int -> [Int]

1	multiplosEspecialesCota :: Int -> Int -> [Int]

tal que (multiplosEspecialesCota n k) es la lista ordenada de todos los múltiplos especiales de n que son menores o iguales que k. Por ejemplo,

   multiplosEspecialesCota 5 50  ==  [5,10,15,20,25,30,40,45,50]
   multiplosEspecialesCota 7 50  ==  []

1 2	multiplosEspecialesCota 5 50 == [5,10,15,20,25,30,40,45,50] multiplosEspecialesCota 7 50 == []

Soluciones

import Data.Numbers.Primes (primeFactors)

multiplosEspecialesCota :: Int -> Int -> [Int]
multiplosEspecialesCota n k =
    [m | m <- [n,2*n..k], 
         all (\p -> p `mod` 3 /= 1) (primeFactors m)]

import Data.Numbers.Primes (primeFactors)

multiplosEspecialesCota :: Int -> Int -> [Int]

multiplosEspecialesCota n k =

[m | m <- [n,2*n..k],

all (\p -> p `mod` 3 /= 1) (primeFactors m)]

Mínimo y máximo de un montículo

PorJosé A. Alonso 6-mayo-201515-mayo-2015

Definir la función

   minMax :: Ord a => Monticulo a -> Maybe (a,a)

1	minMax :: Ord a => Monticulo a -> Maybe (a,a)

tal que (minMax m) es justamente el par formado por el menor y el mayor elemento de m, si el montículo m es no vacío. Por ejemplo,

   minMax (foldr inserta vacio [4,8,2,1,5])  ==  Just (1,8)
   minMax (foldr inserta vacio [4])          ==  Just (4,4)
   minMax vacio                              ==  Nothing

minMax (foldr inserta vacio [4,8,2,1,5]) == Just (1,8)

minMax (foldr inserta vacio [4]) == Just (4,4)

minMax vacio == Nothing

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de montículo (I1M.Monticulo) que se describe aquí y se encuentra aquí.

Soluciones

import I1M.Monticulo   -- http://bit.ly/1AKmUQB

minMax :: Ord a => Monticulo a -> Maybe (a, a)
minMax m | esVacio m = Nothing
         | otherwise = Just (menor m,mayor m)

-- (mayor m) es el mayor elemento del montículo m. Por ejemplo,
--     mayor (foldr inserta vacio [1,8,2,4,5])  ==  8
mayor :: Ord a => Monticulo a -> a
mayor m | esVacio r = menor m
        | otherwise = mayor r
        where r = resto m

-- 2ª definición de mayor 
mayor2 :: Ord a => Monticulo a -> a
mayor2 m = last (monticulo2Lista m)

monticulo2Lista :: Ord a => Monticulo a -> [a]
monticulo2Lista m | esVacio m = []
                  | otherwise = menor m : monticulo2Lista (resto m)

import I1M.Monticulo -- http://bit.ly/1AKmUQB

minMax :: Ord a => Monticulo a -> Maybe (a, a)

minMax m | esVacio m = Nothing

| otherwise = Just (menor m,mayor m)

-- (mayor m) es el mayor elemento del montículo m. Por ejemplo,

-- mayor (foldr inserta vacio [1,8,2,4,5]) == 8

mayor :: Ord a => Monticulo a -> a

mayor m | esVacio r = menor m

| otherwise = mayor r

where r = resto m

-- 2ª definición de mayor

mayor2 :: Ord a => Monticulo a -> a

mayor2 m = last (monticulo2Lista m)

monticulo2Lista :: Ord a => Monticulo a -> [a]

monticulo2Lista m | esVacio m = []

| otherwise = menor m : monticulo2Lista (resto m)

Números cuyas cifras coinciden con las de sus factores primos

PorJosé A. Alonso 4-mayo-201525-marzo-2022

Un número n es especial si al unir las cifras de sus factores primos, se obtienen exactamente las cifras de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

   esEspecial :: Integer -> Bool

1	esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

   esEspecial 1255 == True
   esEspecial 125  == False

1 2	esEspecial 1255 == True esEspecial 125 == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Soluciones

import Data.List (nub, sort)
import Data.Numbers.Primes (isPrime, primeFactors)
import Test.QuickCheck

esEspecial :: Integer -> Bool
esEspecial n = 
    sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es
prop_primos:: Integer -> Property
prop_primos n = 
    isPrime (abs n) ==> esEspecial (abs n)

-- La comprobación es
--    ghci> quickCheck prop_primos
--    +++ OK, passed 100 tests.

-- El cálculo es
--    ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]
--    [735,1255,3792,7236,11913]

import Data.List (nub, sort)

import Data.Numbers.Primes (isPrime, primeFactors)

import Test.QuickCheck

esEspecial :: Integer -> Bool

esEspecial n =

sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es

prop_primos:: Integer -> Property

prop_primos n =

isPrime (abs n) ==> esEspecial (abs n)

-- La comprobación es

-- ghci> quickCheck prop_primos

-- +++ OK, passed 100 tests.

-- El cálculo es

-- ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]

-- [735,1255,3792,7236,11913]

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico