Diagonales principales de una matriz
Definir la función
diagonalesPrincipales :: Matriz a -> [[a]]
tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo, para la matriz
1 2 3 4 5 6 7 8 9 10 11 12
la lista de sus diagonales principales es
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
En Haskell,
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Segmentos de longitud dada
Definir la función
segmentos :: Int -> [a] -> [[a]]
tal que (segmentos n xs) es la lista de los segmentos de longitud n de la lista xs. Por ejemplo,
segmentos 3 [1..5] == [[1,2,3],[2,3,4],[3,4,5]]
Reconocimiento de potencias de 2
Definir la función
esPotenciaDeDos :: Integer -> Bool
tal que (esPotenciaDeDos n) se verifica si n es una potencia de dos (suponiendo que n es mayor que 0). Por ejemplo.
esPotenciaDeDos 1 == True esPotenciaDeDos 2 == True esPotenciaDeDos 6 == False esPotenciaDeDos 8 == True esPotenciaDeDos 1024 == True esPotenciaDeDos 1026 == False esPotenciaDeDos (2^100000) == True
Nota: Comprobar la definición para grandes potencias de 2.
Menor número triangular con más de n divisores
La sucesión de los números triangulares se obtiene sumando los números naturales.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 3 6 10 15
Así, el 7º número triangular es
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
Los primeros 10 números triangulares son
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Los divisores de los primeros 7 números triangulares son:
1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28
Como se puede observar, 28 es el menor número triangular con más de 5 divisores.
Definir la función
menorTriangularConAlMenosNDivisores :: Int -> Integer
tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,
menorTriangularConAlMenosNDivisores 5 == 28 menorTriangularConAlMenosNDivisores 50 == 25200 menorTriangularConAlMenosNDivisores 500 == 76576500
Dos cuadrados encajados
Definir la función
dosCuadrados :: Picture
que dibuje dos cuadrados encajados como se muestra en la siguiente figura
Nota: Escribir las soluciones usando la siguiente plantilla
import Graphics.Gloss main :: IO () main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados dosCuadrados :: Picture dosCuadrados = undefined
Particiones de enteros positivos
Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.
Definir la función
particiones :: Int -> [[Int]]
tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,
particiones 4 == [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] particiones 5 == [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] length (particiones 50) == 204226
Mínimo producto escalar
El producto escalar de los vectores [latex][a_1,a_2,\dots,a_n][/latex] y [latex][b_1,b_2,\dots,b_n][/latex] es [latex]a_1 \times b_1 + a_2 \times b_2 + \dots + a_n \times b_n[/latex].
Definir la función
menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a
tal que (menorProductoEscalar xs ys) es el mínimo de los productos escalares de las permutaciones de xs y de las permutaciones de ys. Por ejemplo,
menorProductoEscalar [3,2,5] [1,4,6] == 29 menorProductoEscalar [3,2,5] [1,4,-6] == -19 menorProductoEscalar [0..9] [0..9] == 120 menorProductoEscalar [0..99] [0..99] == 161700 menorProductoEscalar [0..999] [0..999] == 166167000
Mayor capicúa producto de dos números de n cifras
Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.
Definir la función
mayorCapicuaP :: Integer -> Integer
tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,
mayorCapicuaP 2 == 9009 mayorCapicuaP 3 == 906609 mayorCapicuaP 4 == 99000099 mayorCapicuaP 5 == 9966006699
Siguiente elemento en una lista
Definir la función
siguiente :: Eq a => a -> [a] -> Maybe a
tal que (siguiente x ys) es justo el elemento siguiente a la primera ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,
siguiente 5 [3,5,2,5,7] == Just 2 siguiente 9 [3,5,2,5,7] == Nothing siguiente 'd' "afdegdb" == Just 'e' siguiente "todo" ["En","todo","la","medida"] == Just "la" siguiente "nada" ["En","todo","la","medida"] == Nothing siguiente 999999 [1..1000000] == Just 1000000 siguiente 1000000 [1..1000000] == Nothing
Números polidivisibles
Un número natural es polidivisible si cumple las siguientes condiciones:
- El número formado por sus dos primeros dígitos es divisible por 2.
- El número formado por sus tres primeros dígitos es divisible por 3.
- El número formado por sus cuatros primeros dígitos es divisible por 4.
- etcétera.
Por ejemplo, el número 345654 es un número polidivisible ya que
- 34 es divisible por 2,
- 345 es divisible por 3,
- 3456 es divisible por 4,
- 34565 es divisible por 5 y
- 345654 es divisible por 6.
pero 123456 no lo es, porque 1234 no es divisible por 4.
Definir las funciones
polidivisibles :: [Integer] polidivisiblesN :: Integer -> [Integer]
tales que
- polidivisible es la sucesión cuyos elementos son los números polidivisibles. Por ejemplo,
λ> take 20 polidivisibles [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30] λ> take 10 (dropWhile (<100) polidivisibles) [102,105,108,120,123,126,129,141,144,147]
- (polidivisiblesN k) es la lista de los números polidivisibles con k dígitos. Por ejemplo,
λ> polidivisiblesN 2 [10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48, 50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88, 90,92,94,96,98]
Comprobar que, para n entre 1 y 5, la cantidad de números polidivisibles de n dígitos es 9*10^(n-1)/n!.
Posición del primer falso en un vector
Definir la función
posicion :: Array Int Bool -> Maybe Int
tal que (posicion v) es la menor posición del vector de booleanos v cuyo valor es falso y es Nothing si todos los valores son verdaderos. Por ejemplo,
posicion (listArray (0,4) [True,True,False,True,False]) == Just 2 posicion (listArray (0,4) [i <= 2 | i <- [0..4]]) == Just 3 posicion (listArray (0,4) [i <= 7 | i <- [0..4]]) == Nothing
División según una propiedad
Definir la función
divideSegun :: (a -> Bool) -> [a] -> [[a]]
tal que (divideSegun p xs) es la lista de los segmentos de xs cuyos elementos cumplen la propiedad p. Por ejemplo,
divideSegun even [3,5,2,7,6,8,9,1] == [[3,5],[7],[9,1]] divideSegun odd [3,5,2,7,6,8,9,1] == [[2],[6,8]]
Comprobar con QuickCheck que, para cualquier lista xs de números enteros, la concatenación de los elementos de (divideSegun even xs) es la lista de los elementos de xs que no son pares.
Particiones en listas de segmentos
Definir la función
particiones :: Int -> [a] -> [[[a]]]
tal que (particiones n xs) es la lista de lista de n elementos cuya concatenación es xs. Por ejemplo,
λ> particiones 2 "abc" [["","abc"],["a","bc"],["ab","c"],["abc",""]] λ> particiones 3 "abc" [["","","abc"],["","a","bc"],["","ab","c"],["","abc",""], ["a","","bc"],["a","b","c"],["a","bc",""],["ab","","c"], ["ab","c",""],["abc","",""]] λ> length (particiones 4 "abc") 20
Números naturales separados por ceros
Definir la sucesión
naturales0 :: [Int]
cuyos elementos son los números naturales separados por 0. Por ejemplo,
λ> take 25 naturales0 [0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12]
Comprobar con QuickCheck que el n-ésimo término de la sucesión es n*(1+(-1)^n)/4.
Nota. En la comprobación usar
quickCheckWith (stdArgs {maxSize=7}) prop_naturales0
Enumeración de los números enteros
Definir la sucesión
enteros :: [Int]
tal que sus elementos son los números enteros comenzando en el 0 e intercalando los positivos y los negativos. Por ejemplo,
λ> take 23 enteros [0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]
Comprobar con QuickCheck que el n-ésimo término de la sucesión es (1-(2n+1)(-1)^n)/4.
Nota. En la comprobación usar
quickCheckWith (stdArgs {maxSize=7}) prop_naturales0
Sustitución de listas
Definir la función
sustituye :: Eq a => [a] -> [a] -> [a] -> [a]
tal que (sustituye xs ys zs) es la lista obtenida sustituyendo las ocurrencias de xs en zs por ys. Por ejemplo,
sustituye "as" "_" "las casaderas" == "l_ c_ader_" sustituye "as" "es" "las casaderas" == "les cesaderes" sustituye "asa" "a" "las casaderas" == "las caderas" sustituye "asd" "a" "las casaderas" == "las casaderas"
Triparticiones de una lista
Definir la función
triparticiones :: [a] -> [([a],[a],[a])]
tal que (triparticiones xs) es la lista de las ternas (xs1,xs2,xs3) tales que su concatenación es xs. Por ejemplo,
λ> triparticiones "abc" [("","","abc"),("","a","bc"),("","ab","c"),("","abc",""), ("a","","bc"),("a","b","c"),("a","bc",""),("ab","","c"), ("ab","c",""),("abc","","")]
Comprobar con QuickCheck que, suponiendo que xs es una lista de elementos comparables por igualdad, entonces para cada terna de (triparticiones xs) se cumple que la concatenación de sus elementos es xs.
Listas con suma dada
Definir la función
conSuma :: (Eq a, Num a) => [a] -> [[a]] -> [[[a]]]
tal que (conSuma xs yss) es la lista de los vectores de xss cuya suma vectorial es xs. Por ejemplo,
λ> conSuma [9,10,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]] [[[4,7,3],[5,3,9]],[[4,7,3],[3,1,4],[2,2,5]]] λ> conSuma [9,11,12] [[4,7,3],[3,1,4],[5,3,9],[2,2,5]] []
Suma de una lista de vectores
Definir la función
sumaVec :: Num a => [[a]] -> [a]
tal que (sumaVec xss) es la suma de los vectores de xss. Por ejemplo,
sumaVec [[4,7,3],[3,1,4],[2,2,5]] == [9,10,12] sumaVec [[4,7],[3,3],[1,4],[2,5]] == [10,19]
Ordenación según una función
Definir la función
ordenaSegun :: Ord b => (a -> b) -> [a] -> [a]
tal que (ordenaSegun f xs) es la lista obtenida ordenando los elementos de xs según sus valores mediante la función f. Por ejemplo,
ordenaSegun abs [-3,2,5,-2] == [2,-2,-3,5] ordenaSegun abs [-3,-2,5,2] == [-2,2,-3,5] ordenaSegun length ["pq","x","mn"] == ["x","pq","mn"] [g 0 | g <- ordenaSegun (\f -> f 4) [(+5),(+2),(+3)]] == [2,3,5]
Comprobar con QuickCheck que (ordenaSegun id) es equivalente a sort.
Conjuntos de puntos enteros en regiones rectangulares
Los puntos de una cuadrícula se puede representar mediante pares de números enteros
type Punto = (Int,Int)
y las regiones rectangulares mediante el siguiente tipo de dato
data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show)
donde
- (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
- (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
- (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.
Definir la función
puntos :: Region -> [Punto]
tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por
r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2)
se tiene
λ> puntos r0021 [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)] λ> puntos r3051 [(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)] λ> puntos r4162 [(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)] λ> puntos (Union r0021 r3051) [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)] λ> puntos (Diferencia r3051 r4162) [(3,0),(3,1),(4,0),(5,0)] λ> puntos (Union (Diferencia r3051 r4162) r4162) [(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]
Comprobar con QuickCheck, usando la función enRegion definida en el ejercicio "Puntos en regiones rectangulares" que (enRegion p r) es equivalente a (p elem puntos r).
Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones
import Test.QuickCheck import Control.Monad type Punto = (Int,Int) data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show) r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2) puntos :: Region -> [Punto] puntos = undefined -- La propiedad es prop_puntos :: Punto -> Region -> Bool prop_puntos p r = undefined -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_puntos -- +++ OK, passed 100 tests. enRegion :: Punto -> Region -> Bool enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) = x1 <= x && x <= x2 && y1 <= y && y <= y2 enRegion p (Union r1 r2) = enRegion p r1 || enRegion p r2 enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2) -- Generador de regiones: instance Arbitrary Region where arbitrary = sized arb where arb 0 = liftM2 Rectangulo arbitrary arbitrary arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary, liftM2 Union sub sub, liftM2 Diferencia sub sub] where sub = arb (n `div` 2)
Máxima suma de los segmentos
Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la máxima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vacía.
Definir la función
mss :: [Integer] -> Integer
tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,
mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6] == 7 mss [-1,-2,-3] == 0 mss [1..500] == 125250 mss [1..1000] == 500500 mss [-500..3] == 6 mss [-1000..3] == 6
Listas disjuntas
Definir la función
disjuntas :: Ord a => [a] -> [a] -> Bool
tal que (disjuntas xs ys) se verifica si las listas ordenadas crecientemente xs e ys son disjuntas. Por ejemplo,
disjuntas [2,5] [1,4,7] == True disjuntas [2,5,7] [1,4,7] == False disjuntas [1..1000000] [3000000..4000000] == True
Triángulos de Herón
Un triángulo de Herón es un triángulo tal que sus lados y su área son números enteros. Su nombre se debe al matemático griego Herón de Alejandría que descubrió la fórmula para calcular el área de un triángulo a partir de sus lados.
La fórmula de Herón dice que el área de un triángulo cuyos lados miden a, b y c es \[\sqrt{s(s-a)(s-b)(s-c)}\] donde s es el semiperímetro del triángulo; es decir, \[s=\frac{a+b+c}{2}\]
Un ejemplo de triángulo de Herón es el triángulo de lados 3, 4 y 5 cuya área es 6. Se puede observar que cualquier triángulo cuyos lados sean múltiplos de 3, 4 y 5 también es de Herón; por ejemplo, el de lados 6, 8 y 10 también lo es.
Se dice que un triángulo de Herón es primitivo si el máximo común divisor de sus lados es 1. Por ejemplo, el de lados 3, 4 y 5 es primitivo; pero el de lados 6, 8 y 10 no lo es.
Definir la sucesión
triangulosHeronPrimitivos :: [(Int,Int,Int)]
tal que sus elementos son los triángulos de Herón primitivos ordenados por su perímetro. Por ejemplo,
λ> take 7 triangulosHeronPrimitivos [(3,4,5),(5,5,6),(5,5,8),(5,12,13),(4,13,15),(10,13,13),(9,10,17)]
2015 y los números pitagóricos
Un número pitagórico es un número natural cuyo cuadrado se puede escribir como la suma de los cuadrados de dos números naturales no nulos; es decir, el número natural a es pitagórico si existen dos números naturales b y c distintos de cero tales que a² = b²+c². Por ejemplo, 5 es un número pitagórico ya que 5² = 3²+4² y también lo es 2015 ya que 2015² = 1612²+1209².
Definir la sucesión
pitagoricos :: [Integer]
cuyos elementos son los números pitagóricos. Por ejemplo,
λ> take 20 pitagoricos [5,10,13,15,17,20,25,26,29,30,34,35,37,39,40,41,45,50,51,52]
Calcular la posición de 2015 en la sucesión.
Varios cuadrados encajados rotando
Definir la función
cuadrados :: Int -> Float -> Picture
de forma que (cuadrados n) sea la animación obtenida rotando n cuadrados encajados como se muestra a continuación.
Nota: Escribir las soluciones usando la siguiente plantilla
import Graphics.Gloss import System.IO main :: IO () main = do hSetBuffering stdout NoBuffering putStr "Introduce el numero de cuadrados [1..10]: " n <- readLn animate (InWindow (show n ++ " cuadrados encajados rotando" ) (600,600) (20,20)) white (cuadrados n) cuadrados :: Int -> Float -> Picture cuadrados n t = undefined
Varios cuadrados encajados
Definir la función
cuadrados :: Int -> Picture
tal que (cuadrados n) dibuje n cuadrados encajados como se muestra en las siguientes figuras:
- para n=2
- para n=4
- para n=10
Nota: Escribir las soluciones usando la siguiente plantilla
import Graphics.Gloss import System.IO main :: IO () main = do hSetBuffering stdout NoBuffering putStr "Introduce el numero de cuadrados [1..10]: " n <- readLn display (InWindow (show n ++ " cuadrados encajados" ) (600,600) (20,20)) white (cuadrados n) cuadrados :: Int -> Picture cuadrados n = undefined
Simplificación de expresiones proposicionales
El siguiente tipo de dato algebraico representa las fórmulas proposicionales construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):
data Form = X | V | F | Neg Form | Dis Form Form deriving (Eq, Ord, Show)
Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).
Definir las funciones
valor :: Form -> Bool -> Bool simplifica :: Form -> Form
tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,
valor (Neg X) True == False valor (Neg F) True == True valor (Dis X (Neg X)) True == True valor (Dis X (Neg X)) False == True
y (simplifica p) es una forma obtenida aplicándole a p las siguientes reglas de simplificación:
Neg V = F Neg F = V Neg (Neg q) = q Dis V q = V Dis F q = q Dis q V = V Dis q F = F Dis q q = q
Por ejemplo,
simplifica (Dis X (Neg (Neg X))) == X simplifica (Neg (Dis (Neg (Neg X)) F)) == Neg X simplifica (Dis (Neg F) F) == V simplifica (Dis (Neg V) (Neg (Dis (Neg X) F))) == X simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F))) == Neg X
Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).
Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de fórmulas proposicionales
import Test.QuickCheck import Control.Monad data Form = X | V | F | Neg Form | Dis Form Form deriving (Eq, Ord, Show) valor :: Form -> Bool -> Bool valor = undefined simplifica :: Form -> Form simplifica = undefined -- La propiedad es prop_simplifica :: Form -> Bool -> Bool prop_simplifica p i = undefined -- La comprobación es -- Generador de fórmulas instance Arbitrary Form where arbitrary = sized form where form n | n <= 0 = atom | otherwise = oneof [ atom , liftM Neg subform , liftM2 Dis subform subform ] where atom = oneof [elements [X,V,F]] subform = form (n `div` 2)
2015 y los números con factorización capicúa
Un número tiene factorización capicúa si puede escribir como un producto de números primos tal que la concatenación de sus dígitos forma un número capicúa. Por ejemplo, el 2015 tiene factorización capicúa ya que 2015 = 13531, los factores son primos y su concatenación es 13531 que es capicúa.
Definir la sucesión
conFactorizacionesCapicuas :: [Int]
formada por los números que tienen factorización capicúa. Por ejemplo,
λ> take 20 conFactorizacionesCapicuas [1,2,3,4,5,7,8,9,11,12,16,18,20,25,27,28,32,36,39,44]
Usando conFactorizacionesCapicuas escribir expresiones cuyos valores sean las respuestas a las siguientes preguntas y calcularlas
- ¿Qué lugar ocupa el 2015 en la sucesión?
- ¿Cuál fue el anterior año con factorización capicúa?
- ¿Cuál será el siguiente año con factorización capicúa?
Soluciones
import Data.List (permutations) conFactorizacionesCapicuas :: [Int] conFactorizacionesCapicuas = [n | n <- [1..], not (null (factorizacionesCapicua n))] -- (factorizacionesCapicua n) es la lista de las factorizaciones -- capicúas de n. Por ejemplo, -- factorizacionesCapicua 2015 == [[13,5,31],[31,5,13]] factorizacionesCapicua :: Int -> [[Int]] factorizacionesCapicua n = [xs | xs <- permutations (factorizacion n), esCapicuaConcatenacion xs] -- (factorizacion n) es la lista de todos los factores primos de n; es -- decir, es una lista de números primos cuyo producto es n. Por ejemplo, -- factorizacion 300 == [2,2,3,5,5] factorizacion :: Int -> [Int] factorizacion n | n == 1 = [] | otherwise = x : factorizacion (div n x) where x = menorFactor n -- (menorFactor n) es el menor factor primo de n. Por ejemplo, -- menorFactor 15 == 3 -- menorFactor 16 == 2 -- menorFactor 17 == 17 menorFactor :: Int -> Int menorFactor n = head [x | x <- [2..], rem n x == 0] -- (esCapicuaConcatenacion xs) se verifica si la concatenación de los -- números de xs es capicúa. Por ejemplo, -- esCapicuaConcatenacion [13,5,31] == True -- esCapicuaConcatenacion [135,31] == True -- esCapicuaConcatenacion [135,21] == False esCapicuaConcatenacion :: [Int] -> Bool esCapicuaConcatenacion xs = ys == reverse ys where ys = concat (map show xs) -- El cálculo de la 1ª respuesta es -- λ> length (takeWhile (<= 2015) conFactorizacionesCapicuas) -- 265 -- El cálculo de la 2ª respuesta es -- λ> last (takeWhile (<2015) conFactorizacionesCapicuas) -- 2001 -- El cálculo de la 3ª respuesta es -- λ> head (dropWhile (<=2015) conFactorizacionesCapicuas) -- 2023
Período de una lista
El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período "abababab" es "ab" ya que "abababab" se obtiene repitiendo tres veces la lista "ab".
Definir la función
periodo :: Eq a => [a] -> [a]
tal que (periodo xs) es el período de xs. Por ejemplo,
periodo "ababab" == "ab" periodo "buenobueno" == "bueno" periodo "oooooo" == "o" periodo "sevilla" == "sevilla"
La función suelo
La función suelo asigna a cada número real el número entero más próximo por defecto; es decir, el mayor número entero igual o menor que ese número real. Por ejemplo, al -2.4 le asigna el -3 y al 1.7 el 1.
Haskell tiene una implementación de la función suelo llamada floor. El objetivo de este ejercicio es redefinir dicha función; es decir, definir la función
suelo :: Float -> Integer
tal que (suelo x) es el suelo de x. Por ejemplo,
suelo (-2.7) == -3 suelo (-2.4) == -3 suelo (-2) == -2 suelo 0 == 0 suelo 2 == 2 suelo 2.4 == 2 suelo 2.7 == 2
Comprobar con QuickCheck que las funciones suelo y floor son equivalentes.
Enumeración de los pares de números naturales
Los pares de los números naturales se pueden ordenar por la suma de sus componentes y entres los pares con la misma suma elegir antes al que tiene mayos su primera componente.
Definir la función
pares :: [(Int,Int)]
tal que pares es la lista de los pares de números naturales con el orden anterior. por ejemplo,
λ> take 10 pares [(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]
Usando la definición de pares, definir la función
posicion :: (Int,Int) -> Int
tal que (posicion p) es la posición del par p en la lista pares. Por ejemplo,
posicion (0,0) == 0 posicion (2,0) == 3
Finalmente, comprobar con QuickCheck que para cualquier par (x,y) de números naturales, la (posicion (x,y)) es igual a (y + (x+y+1)*(x+y) div 2).
Nota. En la comprobación usar
quickCheckWith (stdArgs {maxSize=7}) prop_posicion
Elementos más frecuentes
Definir la función
masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]
tal que (masFrecuentes n xs) es la lista de los pares formados por los elementos de xs que aparecen más veces junto con el número de veces que aparecen. Por ejemplo,
λ> masFrecuentes 2 "trianera" [(2,'r'),(2,'a')] λ> masFrecuentes 2 "interdisciplinariedad" [(5,'i'),(3,'d')] λ> masFrecuentes 3 (show (product [1..10000])) [(5803,'0'),(3416,'2'),(3341,'4')]
Puntos en regiones rectangulares
Los puntos se puede representar mediante pares de números
type Punto = (Float,Float)
y las regiones rectangulares mediante el siguiente tipo de dato
data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show)
donde
- (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
- (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
- (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.
Definir la función
enRegion :: Punto -> Region -> Bool
tal que (enRegion p r) se verifica si el punto p pertenece a la región r. Por ejemplo, usando las regiones definidas por
r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2)
se tiene
enRegion (1.6,0.7) r0021 == True enRegion (3.6,0.7) r0021 == False enRegion (1,1) (Union r0021 r3051) == True enRegion (4,0) (Union r0021 r3051) == True enRegion (4,2) (Union r0021 r3051) == False enRegion (3,1) (Diferencia r3051 r4162) == True enRegion (4,1) (Diferencia r3051 r4162) == False enRegion (4,2) (Diferencia r3051 r4162) == False enRegion (4,2) (Union (Diferencia r3051 r4162) r4162) == True
Comprobar con QuickCheck que si el punto p está en la región r1, entonces, para cualquier región r2, p está en (Union r1 r2) y en (Union r2 r1), pero no está en (Diferencia r2 r1).
Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones
import Test.QuickCheck import Control.Monad type Punto = (Float,Float) data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show) r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2) enRegion :: Punto -> Region -> Bool enRegion = undefined -- La propiedad es prop_enRegion p r1 r2 = undefined -- La comprobación es -- λ> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion -- +++ OK, passed 100 tests. -- Generador de regiones: instance Arbitrary Region where arbitrary = sized arb where arb 0 = liftM2 Rectangulo arbitrary arbitrary arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary, liftM2 Union sub sub, liftM2 Diferencia sub sub] where sub = arb (n `div` 2)
Desemparejamiento de listas
Definir la función
desemparejada :: [(a,b)] -> ([a],[b])
tal que (desemparejada ps) es el par de lista (xs,ys) tal que al emparejar (con zip) xs e ys devuelve ps. Por ejemplo,
λ> desemparejada [(3,'l'),(2,'u'),(5,'i'),(9,'s')] ([3,2,5,9],"luis")
Comprobar con QuickCheck que
- desemparejada es equivalente a la función predefinida unzip.
- si el valor de (desemparejada ps) es (xs,ys), entonces (zip xs ys) es igual a ps.
2015 y los números tales que la suma de sus dígitos es igual al número de sus divisores
Una propiedad del 2015 es que la suma de sus dígitos coincide con el número de sus divisores; en efecto, la suma de sus dígitos es 2+0+1+5=8 y tiene 8 divisores (1, 5, 13, 31, 65, 155, 403 y 2015).
Definir la sucesión
especiales :: [Int]
formada por los números n tales que la suma de los dígitos de n coincide con el número de divisores de n. Por ejemplo,
take 12 especiales == [1,2,11,22,36,84,101,152,156,170,202,208]
Usar la sucesión para responder las siguientes cuestiones
- ¿Cuántos años hasta el 2015 inclusive han cumplido la propiedad?
- ¿Cuál fue el anterior al 2015 que cumplió la propiedad?
- ¿Cuál será el siguiente al 2015 que cumplirá la propiedad?
Nota: La sucesión especiales es la misma que la A057531 de la OEIS (On-Line Encyclopedia of Integer Sequences).
2015 como raíz cuadrada de la suma de tres cubos
Todos los años, en las proximidades del final de año suelen aparecer cuestiones con propiedades del número del nuevo año. Una sobre el 2015 es la publicada el martes en la entrada 2015 como raíz de la suma de tres cubos del blog Números y algo más en la que se pide calcular tres números tales que 2015 sea igual a la raíz cuadrada de la suma de dichos tres números.
A partir de dicha entrada, se propone el siguiente problema: Definir la sucesión
raicesCuadradasDeSumasDe3Cubos :: [Integer]
cuyos elementos son los números que se pueden escribir como raíces cuadradas de sumas de tres cubos. Por ejemplo,
take 9 raicesCuadradasDeSumasDe3Cubos = [6,9,15,27,48,72,53,59,78]
El 6 está en la sucesión porque 1³+2³+3³ = 36 y la raíz cuadrada de36 es 6 y el 9 está porque 3³+3³+3³ = 81 y la raíz cuadrada de 81 es 9. Algunos números tienen varias descomposiones como raíz cuadrada de suma de tres cubos; por ejemplo, el 71 se puede escribir como la raíz cuadrada de la suma de los cubos de 6, 9 y 16 y también como la de 4, 4, y 17.
A partir de la sucesión se plantean las siguientes cuestiones:
- ¿Qué lugar ocupa el 2015 en la sucesión?
- ¿Cuál será el próximo año que se podrá escribir como la raíz cuadrada de suma de tres cubos?
- ¿Cuáles son las descomposiciones de 2015 como raíz cuadrada de suma de tres cubos?
- ¿Cuáles son los años hasta el 2015 que se pueden escribir como raíz cuadrada de suma de tres cubos de más formas distintas?
Fractal de la curva del dragón
La curva del dragón es un fractal que se construye siguiendo los siguientes pasos:
- A partir de un segmento, se construye el triángulo rectángulo e isósceles, como lo muestra las dos primeras figuras. Luego se borra el segmento inicial.
- Se repite varias veces el proceso de remplazar un segmento por otros dos para cada línea de la curva, alternando siempre la orientación de los triángulos.
La siguiente figura muestra los trece primeros pasos:
El ejercicio consiste en definir (en CodeWorld) la función
dragon :: Number -> Picture
tal que (dragon n) es el dibujo correspondiente al paso n de la construcción de la curva del dragón. Por ejemplo, el dibujo de dragon(20) es
Nota: La descripción de la curva dragón es la que se encuentra en el artículo de la Wikipedia.
Elementos adicionales
Definir la función
adicionales :: Ord a => Int -> [a] -> [a] -> [a]
tal que (adicionales n xs ys) es la lista de los n elementos de que no pertenecen a ys (se supone que las listas xs e ys están ordenadas y que pueden ser infinitas). Por ejemplo,
adicionales 0 [1,3] [1,3] == [] adicionales 1 [1,3] [1] == [3] adicionales 2 [1,3,5] [1] == [3,5] adicionales 2 [1,3,5,7,9] [1,5,7] == [3,9] adicionales 2 ([1,3,5]++[7..]) ([1]++[7..]) == [3,5]
Representaciones de matrices
Las matrices se pueden representar de distintas formas. Por ejemplo, la matriz
|7 5 6| |1 9 4|
se puede representar como la terna
([7,5,6,1,9,4],2,3)
(donde la primera componente es la lista de los elementos de matriz, la segunda es su número de filas y la tercera es su número de columnas) y también se puede representar como una lista de listas
[[[7,5,6],[1,9,4]]
(donde cada elemento es una de las filas de la matriz).
Definir las funciones
ternaAlistas :: ([a],Int,Int) -> [[a]] listasAterna :: [[a]] -> ([a],Int,Int)
tales que ternaAlistas pase de la primera representación a la segunda y listasAterna pase de la segunda a la primera. Por ejemplo,
ternaAlistas ([7,5,6,1,9,4],2,3) == [[7,5,6],[1,9,4]] listasAterna [[7,5,6],[1,9,4]] == ([7,5,6,1,9,4],2,3) ternaAlistas ([7,5,6,1,9,4],3,2) == [[7,5],[6,1],[9,4]] listasAterna [[7,5],[6,1],[9,4]] == ([7,5,6,1,9,4],3,2)
Permutación de elementos consecutivos
Definir la función
permutaConsecutivos :: [a] -> [a]
tal que (permutaConsecutivos xs) es la lista obtenida permutando los elementos consecutivos de xs. Por ejemplo,
permutaConsecutivos [1..8] == [2,1,4,3,6,5,8,7] permutaConsecutivos [1..9] == [2,1,4,3,6,5,8,7,9] permutaConsecutivos "simplemente" == "ispmelemtne"
Juego de bloques con letras
Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.
Definir la función
soluciones :: [String] -> String -> [[String]]
tal que (soluciones bs cs) es la lista de las soluciones del juego de los bloque usando los bloques bs (cada bloque es una cadena de dos letras mayúsculas) para formar la palabra cs. Por ejemplo,
λ> soluciones ["AB","NO","OA"] "ANA" [["AB","NO","OA"],["OA","NO","AB"]] λ> soluciones ["AB","NE","OA"] "Bea" [["AB","NE","OA"]] λ> soluciones ["AB","NE","OA"] "EvA" [] λ> soluciones ["AB","NO","OA","NC"] "ANA" [["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]] λ> soluciones ["AB","NO","OA","NC"] "Anca" [["AB","NO","NC","OA"],["OA","NO","NC","AB"]] λ> soluciones (["AB","NO","OA"] ++ replicate (10^6) "PQ") "ANA" [["AB","NO","OA"],["OA","NO","AB"]]
Números que sumados a su siguiente primo dan primos
La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.
La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.
Definir la sucesión
a249624 :: [Integer]
tal que sus elementos son los números x tales que la suma de x y el primo que le sigue es un número primo. Por ejemplo,
λ> take 20 a249624 [0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]
El número 8 está en la sucesión porque su siguiente primo es 11 y 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente primo es 13 y 12+13=25 no es primo.
Normalización de expresiones aritméticas
El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos
data Expr = Var String | S Expr Expr | P Expr Expre deriving (Eq, Show)
Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))
Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.
Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.
Definir la función
esTermino :: Expr -> Bool esTermino :: Expr -> Bool normal :: Expr -> Expr
tales que
- (esTermino a) se verifica si a es un término. Por ejemplo,
esTermino (V "x") == True esTermino (P (V "x") (P (V "y") (V "z"))) == True esTermino (P (V "x") (S (V "y") (V "z"))) == False esTermino (S (V "x") (P (V "y") (V "z"))) == False
- (esNormal a) se verifica si a está en forma normal. Por ejemplo,
esNormal (V "x") == True esNormal (P (V "x") (P (V "y") (V "z"))) == True esNormal (S (V "x") (P (V "y") (V "z"))) == True esNormal (P (V "x") (S (V "y") (V "z"))) == False esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True
- (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:
(a+b)*c = a*c+b*c c*(a+b) = c*a+c*b
Por ejemplo,
λ> normal (P (S (V "x") (V "y")) (V "z")) S (P (V "x") (V "z")) (P (V "y") (V "z")) λ> normal (P (V "z") (S (V "x") (V "y"))) S (P (V "z") (V "x")) (P (V "z") (V "y")) λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v"))) S (S (P (V "x") (V "u")) (P (V "x") (V "v"))) (S (P (V "y") (V "u")) (P (V "y") (V "v"))) λ> normal (S (P (V "x") (V "y")) (V "z")) S (P (V "x") (V "y")) (V "z") λ> normal (V "x") V "x"
Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).
Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas
import Test.QuickCheck import Control.Monad instance Arbitrary Expr where arbitrary = sized arb where arb 0 = liftM V arbitrary arb n | n > 0 = oneof [liftM V arbitrary, liftM2 S sub sub, liftM2 P sub sub] where sub = arb (n `div` 2)
Sin consecutivos repetidos
Definir la función
sinConsecutivosRepetidos :: Eq a => [a] -> [a]
tal que (sinConsecutivosRepetidos xs) es la lista obtenida a partir de xs de forma que si hay dos o más elementos idénticos consecutivos, borra las repeticiones y deja sólo el primer elemento. Por ejemplo,
λ> sinConsecutivosRepetidos "eesssooo essss toodddooo" "eso es todo"
Búsqueda en lista de listas de pares
Definir la función
busca :: Eq a => a -> [[(a,b)]] -> [b]
tal que (busca x pss) es la lista de los segundos componentes de los pares de la lista de listas de pares pss cuya primera componentes es x. Por ejemplo,
busca 3 [[(3,4)],[(5,4),(3,2),(3,5)],[(4,1),(7,3)]] == [4,2,5]
Problema de las puertas
Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:
- Inicialmente todas las puertas están cerradas.
- El primer camarero cambia de estado las puertas de todas las habitaciones.
- El segundo cambia de estado de las puertas de las habitaciones pares.
- El tercero cambia de estado todas las puertas que son múltiplos de 3.
- El cuarto cambia de estado todas las puertas que son múltiplos de 4
- Así, hasta que ha pasado el último camarero.
Por ejemplo, para n = 5
Pase | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5 Inicial | Cerrada | Cerrada | Cerrada | Cerrada | Cerrada Pase 1 | Abierta | Abierta | Abierta | Abierta | Abierta Pase 2 | Abierta | Cerrada | Abierta | Cerrada | Abierta Pase 3 | Abierta | Cerrada | Cerrada | Cerrada | Abierta Pase 4 | Abierta | Cerrada | Cerrada | Abierta | Abierta Pase 5 | Abierta | Cerrada | Cerrada | Abierta | Cerrada
Los estados de las puertas se representan por el siguiente tipo de datos
data Estado = Abierta | Cerrada deriving (Eq, Show)
Definir la función
final :: Int -> [Estado]
tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,
λ> final 5 [Abierta,Cerrada,Cerrada,Abierta,Cerrada] λ> final 7 [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]
Llanuras de longitud dada
Expresiones aritmética normalizadas
El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos
data Expr = Var String | S Expr Expr | P Expr Expre
Por ejemplo, x.(y+z) se representa por (P (V "x") (S (V "y") (V "z")))
Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.
Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.
Definir las funciones
esTermino, esNormal :: Expr -> Bool
tales que
- (esTermino a) se verifica si a es un término. Por ejemplo,
esTermino (V "x") == True esTermino (P (V "x") (P (V "y") (V "z"))) == True esTermino (P (V "x") (S (V "y") (V "z"))) == False esTermino (S (V "x") (P (V "y") (V "z"))) == False
- (esNormal a) se verifica si a está en forma normal. Por ejemplo,
esNormal (V "x") == True esNormal (P (V "x") (P (V "y") (V "z"))) == True esNormal (S (V "x") (P (V "y") (V "z"))) == True esNormal (P (V "x") (S (V "y") (V "z"))) == False esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
Acrónimos
A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,
- "ofimática" es un acrónimo de "oficina" e "informática"
- "informática" es un acrónimo de "información" y "automática"
- "teleñeco" es un acrónimo de "televisión" y "muñeco"
Definir la función
esAcronimo :: String -> String -> String -> Bool
tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys y zs. Por ejemplo,
esAcronimo "ofimatica" "oficina" "informatica" == True esAcronimo "informatica" "informacion" "automatica" == True
Particiones de longitud fija
Definir la función
particionesFijas :: Int -> Int -> [[Int]]
tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,
λ> particionesFijas 8 2 [[4,4],[5,3],[6,2],[7,1]] λ> particionesFijas 8 3 [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]] λ> particionesFijas 9 3 [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]] λ> length (particionesFijas 67 5) 8056
Evaluación de árboles de expresiones aritméticas
Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión "9-2*4" se puede representar por el árbol
-
/ \
9 *
/ \
2 4
Definiendo el tipo de dato Arbol por
data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol
la representación del árbol anterior es
N (-) (H 9) (N (*) (H 2) (H 4))
Definir la función
valor :: Arbol -> Int
tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,
valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1 valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17 valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11 valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13
Aplicaciones alternativas
Definir la función
alternativa :: (a -> b) -> (a -> b) -> [a] -> [b]
tal que (alternativa f g xs) es la lista obtenida aplicando alternativamente las funciones f y g a los elementos de xs. Por ejemplo,
alternativa (+1) (+10) [1,2,3,4] == [2,12,4,14] alternativa (+10) (*10) [1,2,3,4,5] == [11,20,13,40,15]
Repetición cíclica
Definir la función
ciclica :: [a] -> [a]
tal que (ciclica xs) es la lista obtenida repitiendo cíclicamente los elementos de xs. Por ejemplo,
take 10 (ciclica [3,5]) == [3,5,3,5,3,5,3,5,3,5] take 10 (ciclica [3,5,7]) == [3,5,7,3,5,7,3,5,7,3] take 10 (ciclica [3,5..]) == [3,5,7,9,11,13,15,17,19,1] ciclica [] == []
Comprobar con QuickCheck que la función ciclica es equivalente a la predefinida cycle; es decir, para cualquier número entero n y cualquier lista no vacía xs, se verifica que
take n (ciclica xs) == take n (cycle xs)
Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
λ> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica +++ OK, passed 100 tests.
Elemento común en la menor posición
Definir la función
elemento :: Eq a => [a] -> [a] -> [a]
tal que (elemento xs ys) es la lista formada por el elemento común a xs e ys con la menor posición. Por ejemplo.
elemento [3,7,6,9,8,0] [5,4,2,7,8,6,9] == [7] elemento [3,7,6,9] [9,5,6] == [9] elemento [5,3,6] [7,6,3] == [3] elemento [3,7,6,3,8,0] [5,4,9,1,4,2,1] == []
Nota: Como se observa en el 3ª ejemplo, en el caso de que un elemento x de xs pertenezca a ys y el elemento de ys en la misma posición que x pertenezca a xs, se elige como el de menor posición el de xs.
Cuantificadores sobre listas
Definir la función
verificaP :: (a -> Bool) -> [[a]] -> Bool
tal que (verificaP p xs) se verifica si cada elemento de la lista xss contiene algún elemento que cumple el predicado p. Por ejemplo,
verificaP odd [[1,3,4,2], [4,5], [9]] == True verificaP odd [[1,3,4,2], [4,8], [9]] == False
Nota: Se puede definir por comprensión, recursión y plegado.
Inversa a trozos
Definir la función
inversa :: Int -> [a] -> [a]
tal que (inversa k xs) es la lista obtenida invirtiendo elementos de xs, k elementos cada vez. Si el número de elementos de xs no es un múltiplo de k, entonces los finales elementos de xs se dejen sin invertir. Por ejemplo,
inversa 3 [1..11] == [3,2,1,6,5,4,9,8,7,10,11] inversa 4 [1..11] == [4,3,2,1,8,7,6,5,9,10,11]
Comprobar con QuickCheck que la función inversa es involutiva; es decir, para todo número k>0 y toda lista xs, se tiene que (inversa k (inversa k xs)) es igual a xs
Mínimos locales
Un mínimo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un mínimo local de [3,2,1,3,7,7,1,0,2] ya que es menor que 2 (su predecesor) y que 3 (su sucesor).
Definir la función
minimosLocales :: Ord a => [a] -> [a]
tal que (minimosLocales xs) es la lista de los mínimos locales de la lista xs. Por ejemplo,
minimosLocales [3,2,1,3,7,7,9,6,8] == [1,6] minimosLocales [1..100] == [] minimosLocales "mqexvzat" == "eva"
Pequeño test de inteligencia
Recientemente se publicó en la Red un pequeño test de inteligencia cuyo objetivo consistía en descubrir una función a partir de una colección de ejemplos. Los ejemplos eran los siguientes
f 6 4 == 210 f 9 2 == 711 f 8 5 == 313 f 5 2 == 37 f 7 6 == 113 f 9 8 == 117 f 10 6 == 416 f 15 3 == 1218
Definir la función
f :: Int -> Int -> Int
tal que f cubra los ejemplos anteriores y la definición de f sea lo más corta posible (en número de palabras).
Mayores elementos de una matriz
Las matrices se pueden representar mediante listas de listas. Por ejemplo, la matriz
|3 2 5| |4 9 7|
se puede representar por [[3,2,5],[4,9,7]].
Definir la función
mayores :: Ord a => Int -> [[a]] -> [(a,Int)]
tal que (mayores n xss) es la lista de los n mayores elementos de matriz xss junto con sus correspondientes número de fila. Por ejemplo,
λ> mayores 4 [[4,26,9],[2,37,53],[41,1,8]] [(53,2),(41,3),(37,2),(26,1)]
Comprobar con QuickCheck que todos los elementos de (mayores n xss) son mayores o iguales que los restantes elementos de xss.
Nota: Se pueden usar las funciones sort y (\) de la librería Data.List.
Último dígito no nulo del factorial
El factorial de 7 es
7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040
por tanto, el último dígito no nulo del factorial de 7 es 4.
Definir la función
ultimoNoNuloFactorial :: Integer -> Integer
tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,
ultimoNoNuloFactorial 7 == 4 ultimoNoNuloFactorial 10 == 8 ultimoNoNuloFactorial 12 == 6 ultimoNoNuloFactorial 97 == 2 ultimoNoNuloFactorial 0 == 1
Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.
Repetición de elementos
Definir la función
repiteElementos :: Int -> [a] -> [a]
tal que (repiteElementos k xs) es la lista obtenida repitiendo cada elemento de xs k veces. Por ejemplo,
repiteElementos 3 [5,2,7,4] == [5,5,5,2,2,2,7,7,7,4,4,4]
Comprobar con QuickCheck que, para todo número natural k y toda lista xs, el número de elementos de (repiteElementos k xs) es k veces el número de elementos de xs.
Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
λ> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos +++ OK, passed 100 tests.
Conjunto de primos relativos
Dos números enteros son primos relativos si no tienen ningún factor primo en común, o, dicho de otra manera, si no tienen otro divisor común más que 1 y -1. Equivalentemente son primos entre sí, si y sólo si, su máximo común divisor es igual a 1.
Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3
Definir la función
primosRelativos :: [Int] -> Bool
tal que (primosRelativos xs) se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,
primosRelativos [6,35] == True primosRelativos [6,27] == False primosRelativos [2,3,4] == False primosRelativos [6,35,11] == True primosRelativos [6,35,11,221] == True primosRelativos [6,35,11,231] == False
Precio total
Una función de precio determina el precio de cada elemento; por ejemplo,
precioCI :: String -> Int precioCI "leche" = 10 precioCI "mantequilla" = 18 precioCI "patatas" = 22 precioCI "chocolate" = 16
Definir la función
precioTotal :: (String -> Int) -> [String] -> Int
tal que (precioTotal f xs) es el precio total de los elementos de xs respecto de la función de precio f. Por ejemplo,
precioTotal precioCI ["leche", "leche", "mantequilla"] == 38 precioTotal precioCI ["chocolate", "mantequilla"] == 34
Extensión de un fichero
La extensión de un fichero es la palabra a continuación del último punto en el nombre del fichero. Por ejemplo, la extensión de "documento.txt" es "txt"
Definir la función
extension :: String -> String
tal que (extension cs) es la extensión del fichero cs. Por ejemplo,
extension "ejercicio.hs" == "hs" extension "documento.txt" == "txt" extension "documento.txt.pdf" == "pdf" extension "resumen" == ""
Distancia de Hamming
La distancia de Hamming entre dos listas es el número de en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).
Definir la función
distancia :: Eq a => [a] -> [a] -> Int
tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,
distancia "romano" "comino" == 2 distancia "romano" "camino" == 3 distancia "roma" "comino" == 2 distancia "roma" "camino" == 3 distancia "romano" "ron" == 1 distancia "romano" "cama" == 2 distancia "romano" "rama" == 1
Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad
distancia(xs,ys) = 0 si, y sólo si, xs = ys
y, en el caso de que no se verifique, modificar ligeramente propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.
Rompecabeza matemático
Definir una función
f :: Int -> Int
tal que para todo n, f(f(n)) = -n y comprobar con QuickCheck que se cumple la propiedad
prop_f :: Int -> Bool prop_f n = f (f n) == -n
es decir,
λ> quickCheck prop_f +++ OK, passed 100 tests.
Suma de todos los anteriores
Definir la función
sumaAnteriores :: [Integer] -> Bool
tal que (sumaAnteriores xs) se verifica si cada elemento de la lista xs (excepto el primero) es la suma de sus anteriores elementos en la lista. Por ejemplo,
sumaAnteriores [3,3,6,12] == True sumaAnteriores [3,3,7,10] == False sumaAnteriores [3] == True sumaAnteriores [] == True
Máximo de una función
Se considera la siguiente función
g :: Integer -> Integer g n = if n < 10 then n*n else n
Definir la función
max_g :: Integer -> Integer
tal que (max_g n) es el punto i del intervalo [0,n] donde g alcanza el máximo de sus valores, si n es positivo y 0 en caso contrario. Por ejemplo,
max_g (-7) == 0 max_g 7 == 7 max_g 14 == 9 max_g 84 == 84
Comprobar con QuickCheck que la función max_g es equivalente a la función f definida por
f :: Integer -> Integer f n | n < 0 = 0 | n >= 10 && n < 81 = 9 | otherwise = n
Nota: Se piden dos definiciones de max_g, una por comprensión y otra por recursión.
Mayúscula inicial
Definir la función
mayusculaInicial :: String -> String
tal que (mayusculaInicial xs) es la palabra xs con la letra inicial en mayúscula y las restantes en minúsculas. Por ejemplo,
mayusculaInicial "sEviLLa" == "Sevilla"
Parte impar de un número
Todo número entero \(n\) se puede escribir como \(m \times 2^k\), con \(m\) impar. Se dice que \(m\) es la parte impar de \(n\). Por ejemplo, la parte impar de 40 es 5 porque 40 = \(5 \times 2^3\).
Definir la función
parteImpar :: Int -> Int
tal que (parteImpar n) es la parte impar de n. Por ejemplo,
parteImpar 40 == 5
Elementos no repetidos
Definir la función
noRepetidos :: Eq a => [a] -> [a]
tal que (noRepetidos xs) es la lista de los elementos no repetidos de la lista xs. Por ejemplo,
noRepetidos [3,2,5,2,4,7,3] == [5,4,7] noRepetidos "noRepetidos" == "nRptids" noRepetidos "Roma" == "Roma"
Listas equidigitales
Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.
Definir la función
equidigital :: [Int] -> Bool
tal que (equidigital xs) se verifica si xs es una lista equidigital. Por ejemplo,
equidigital [343,225,777,943] == True equidigital [343,225,777,94,3] == False
Divisibles por el primero
Definir la función
divisiblesPorPrimero :: [Int] -> Bool
tal que (divisibles xs) se verifica si todos los elementos positivos de xs son divisibles por el primero. Por ejemplo,
divisiblesPorPrimero [2,6,-3,0,18,-17,10] == True divisiblesPorPrimero [-13] == True divisiblesPorPrimero [-3,6,1,-3,9,18] == False divisiblesPorPrimero [5,-2,-6,3] == False divisiblesPorPrimero [] == True divisiblesPorPrimero [0,2,4] == False divisiblesPorPrimero [0,-2,-4] == True
Laberinto numérico
El problema del laberinto numérico consiste en, dados un par de números, encontrar la longitud del camino más corto entre ellos usando sólo las siguientes operaciones:
- multiplicar por 2,
- dividir por 2 (sólo para los pares) y
- sumar 2.
Por ejemplo, un camino mínimo
- de 3 a 12 es [3,6,12],
- de 12 a 3 es [12,6,3],
- de 9 a 2 es [9,18,20,10,12,6,8,4,2] y
- de 2 a 9 es [2,4,8,16,18,9].
Definir la función
longitudCaminoMinimo :: Int -> Int -> Int
tal que (longitudCaminoMinimo x y) es la longitud del camino mínimo desde x hasta y en el laberinto numérico.
longitudCaminoMinimo 3 12 == 2 longitudCaminoMinimo 12 3 == 2 longitudCaminoMinimo 9 2 == 8 longitudCaminoMinimo 2 9 == 5
Sustitución en una expresión aritmética
La expresiones aritméticas se pueden representar mediante el siguiente tipo
data Expr = C Int | V Char | S Expr Expr | P Expr Expr deriving (Eq, Show)
por ejemplo, la expresión "z*(3+x)" se representa por (P (V 'z') (S (C 3) (V 'x'))).
Definir la función
sustitucion :: Expr -> [(Char, Int)] -> Expr
tal que (sustitucion e s) es la expresión obtenida sustituyendo las variables de la expresión e según se indica en la sustitución s. Por ejemplo,
λ> sustitucion (P (V 'z') (S (C 3) (V 'x'))) [('x',7),('z',9)] P (C 9) (S (C 3) (C 7)) λ> sustitucion (P (V 'z') (S (C 3) (V 'y'))) [('x',7),('z',9)] P (C 9) (S (C 3) (V 'y'))
Clausura de un conjunto respecto de una función
Un conjunto A está cerrado respecto de una función f si para todo elemento x de A se tiene que f(x) pertenece a A. La clausura de un conjunto B respecto de una función f es el menor conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo, la clausura de {0,1,2} respecto del opuesto es {0,1,2,-1,-2}.
Definir la función
clausura :: Eq a => (a -> a) -> [a] -> [a]
tal que (clausura f xs) es la clausura de xs respecto de f. Por ejemplo,
clausura (\x -> -x) [0,1,2] == [0,1,2,-1,-2] clausura (\x -> (x+1) `mod` 5) [0] == [0,1,2,3,4]
Cadenas de ceros y unos
Definir la constante
cadenasCerosUnos :: [String]
tal que cadenasCerosUnos es la lista de cadenas de ceros y unos,
ordenada lexicográficamente. Por ejemplo,
λ> take 15 cadenasCerosUnos1 ["","0","1","00","01","10","11","000","001","010","011","100", "101","110","111"]
Números con todos sus dígitos primos
Definir la lista
numerosConDigitosPrimos :: [Integer]
cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,
λ> take 22 numerosConDigitosPrimos [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223] λ> numerosConDigitosPrimos !! (10^7) 322732232572
Matriz permutación
Una matriz permutación es una matriz cuadrada con todos sus elementos iguales a 0, excepto uno cualquiera por cada fila y columna, el cual debe ser igual a 1.
En este ejercicio se usará el tipo de las matrices definido por
type Matriz a = Array (Int,Int) a
y los siguientes ejemplos de matrices
q1, q2, q3 :: Matriz Int q1 = array ((1,1),(2,2)) [((1,1),1),((1,2),0),((2,1),0),((2,2),1)] q2 = array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),0),((2,2),1)] q3 = array ((1,1),(2,2)) [((1,1),3),((1,2),0),((2,1),0),((2,2),1)]
Definir la función
esMatrizPermutacion :: Num a => Matriz a -> Bool
tal que (esMatrizPermutacion p) se verifica si p es una matriz permutación. Por ejemplo.
esMatrizPermutacion q1 == True esMatrizPermutacion q2 == False esMatrizPermutacion q3 == False
Inserción en árboles binarios de búsqueda
Un árbol binario de búsqueda (ABB) es un árbol binario tal que el cada nodo es mayor que los valores de su subárbol izquierdo y menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el siguiente ABB:
3
/ \
/ \
2 6
/ \
4 8
Los ABB se pueden representar como tipo de dato algebraico:
data ABB = V | N Int ABB ABB deriving (Eq, Show)
Por ejemplo, la definición del ABB anteriore es
ej :: ABB ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))
Definir la función
inserta :: Int -> ABB -> ABB
tal que (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si no es uno de sus valores. Por ejemplo,
λ> inserta 5 ej N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V)) λ> inserta 1 ej N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V)) λ> inserta 2 ej N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))
Comprobar con QuickCheck que al insertar un valor en un ABB se obtiene otro ABB.
Producto de matrices como listas de listas
Las matrices pueden representarse mediante una lista de listas donde cada una de las lista representa una fila de la matriz. Por ejemplo, la matriz
|1 0 -2| |0 3 -1|
puede representarse por [[1,0,-2],[0,3,-1]].
Definir la función
producto :: Num a => [[a]] -> [[a]] -> [[a]]
tal que (producto p q) es el producto de las matrices p y q. Por ejemplo,
λ> producto [[1,0,-2],[0,3,-1]] [[0,3],[-2,-1],[0,4]] [[0,-5],[-6,-7]]
Sucesiones pucelanas
En la Olimpiada de Matemática del 2010 se planteó el siguiente problema:
Una sucesión pucelana es una sucesión creciente de 16 números impares positivos consecutivos, cuya suma es un cubo perfecto. ¿Cuántas sucesiones pucelanas tienen solamente números de tres cifras?
Para resolverlo se propone el siguiente ejercicio.
Definir la función
pucelanasConNcifras :: Int -> [[Int]]
tal que (pucelanasConNcifras n) es la lista de las sucesiones pucelanas que tienen solamente números de n cifras. Por ejemplo,
λ> pucelanasConNcifras 2 [[17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47]]
Calcular cuántas sucesiones pucelanas tienen solamente números de tres cifras.
Todas tienen par
Definir la función
todasTienenPar :: [[Int]] -> Bool
tal que tal que todasTienenPar xss se verifica si cada elemento de la lista de listas xss contiene algún número par. Por ejemplo,
todasTienenPar [[1,2],[3,4,5],[8]] == True todasTienenPar [[1,2],[3,5]] == False
Producto cartesiano de una familia de conjuntos
Definir la función
producto :: [[a]] -> [[a]]
tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,
λ> producto [[2,5],[6,4]] [[2,6],[2,4],[5,6],[5,4]] λ> producto [[1,3],[2,5],[6,4]] [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] λ> producto [[1,3,5],[2,4]] [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]] λ> producto [] [[]]
Comprobar con QuickCheck que para toda lista de listas de enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.
Código Morse
El código Morse es un sistema de representación de letras y números mediante señales emitidas de forma intermitente.
A los signos (letras mayúsculas o dígitos) se le asigna un código como se muestra a continuación
+---+-------+---+-------+---+-------+---+-------+ | A | .- | J | .--- | S | ... | 1 | ..--- | | B | -... | K | -.- | T | - | 2 | ...-- | | C | -.-. | L | .-.. | U | ..- | 3 | ....- | | D | -.. | M | -- | V | ...- | 4 | ..... | | E | . | N | -. | W | .-- | 5 | -.... | | F | ..-. | O | --- | X | -..- | 6 | --... | | G | --. | P | .--. | Y | -.-- | 7 | ---.. | | H | .... | Q | --.- | Z | --.. | 8 | ----. | | I | .. | R | .-. | 0 | .---- | 9 | ----- | +---+-------+---+-------+---+-------+---+-------+
El código Morse de las palabras se obtiene a partir del de sus caracteres insertando un espacio entre cada uno. Por ejemplo, el código de "todo" es "- --- -.. ---"
El código Morse de las frase se obtiene a partir del de sus palabras insertando un espacio entre cada uno. Por ejemplo, el código de "todo o nada" es "- --- -.. --- --- -. .- -.. .-"
Definir las funciones
fraseAmorse :: String -> String morseAfrase :: String -> String
tales que
- (fraseAmorse cs) es la traducción de la frase cs a Morse. Por ejemplo,
λ> fraseAmorse "En todo la medida" ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-"
- (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por ejemplo,
λ> morseAfrase ". -. - --- -.. --- .-.. .- -- . -.. .. -.. .-" "EN TODO LA MEDIDA"
Nota: La lista de los códigos Morse de A, B, ..., Z, 0, 1, ..., 9 es
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---", "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-", "..-","...-",".--","-..-","-.--","--..",".----","..---","...--", "....-",".....","-....","--...","---..","----.","-----"]
Elemento más cercano que cumple una propiedad
Definir la función
cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
tal que (cercano p n xs) es el elemento de xs cuya posición es la cercana a la posición n que verifica la propiedad p. La búsqueda comienza en n y los elementos se analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo,
cercano (`elem` "aeiou") 6 "Sevilla" == Just 'a' cercano (`elem` "aeiou") 1 "Sevilla" == Just 'e' cercano (`elem` "aeiou") 2 "Sevilla" == Just 'i' cercano (`elem` "aeiou") 5 "Sevilla" == Just 'a' cercano (`elem` "aeiou") 9 "Sevilla" == Just 'a' cercano (`elem` "aeiou") (-3) "Sevilla" == Just 'e' cercano (>100) 4 [200,1,150,2,4] == Just 150 cercano even 5 [1,3..99] == Nothing
Representación de Zeckendorf
Los primeros números de Fibonacci son
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.
El teorema de Zeckendorf establece que todo entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es
100 = 89 + 8 + 3
Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,
100 = 89 + 8 + 2 + 1 100 = 55 + 34 + 8 + 3
pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.
Definir la función
zeckendorf :: Integer -> [Integer]
tal que (zeckendorf n) es la representación de Zeckendorf de n. Por ejemplo,
zeckendorf 100 == [89,8,3] zeckendorf 2014 == [1597,377,34,5,1] zeckendorf 28656 == [17711,6765,2584,987,377,144,55,21,8,3,1] zeckendorf 14930396 == [14930352,34,8,2]
Ventana deslizante
Definir la función
ventanas :: Int -> Int -> [a] -> [[a]]
tal que (ventanas x y zs) es la lista de ventanas de zs de tamaño x y deslizamiento y; es decir, listas de x elementos consecutivos de zs (salvo, posiblemente, la última que puede ser menor) tales que la diferencia de posiciones entre los primeros elementos de ventanas consecutivas es y. Por ejemplo,
ventanas 3 2 [5,1,9,2] == [[5,1,9],[9,2]] ventanas 3 3 [5,1,9,2] == [[5,1,9],[2]] ventanas 3 4 [5,1,9,2] == [[5,1,9]] ventanas 4 1 [1..7] == [[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]] ventanas 4 2 [1..7] == [[1,2,3,4],[3,4,5,6],[5,6,7]] ventanas 4 3 [1..7] == [[1,2,3,4],[4,5,6,7]] ventanas 4 4 [1..7] == [[1,2,3,4],[5,6,7]] ventanas 4 5 [1..7] == [[1,2,3,4],[6,7]] ventanas 4 6 [1..7] == [[1,2,3,4],[7]] ventanas 4 7 [1..7] == [[1,2,3,4]] ventanas 4 8 [1..7] == [[1,2,3,4]] ventanas 3 2 "abcdef" == ["abc","cde","ef"] ventanas 3 3 "abcdef" == ["abc","def"] ventanas 3 4 "abcdef" == ["abc","ef"] ventanas 3 5 "abcdef" == ["abc","f"] ventanas 3 6 "abcdef" == ["abc"] ventanas 3 7 "abcdef" == ["abc"] ventanas 1 5 "abcdef" == ["a","f"]
Divide si todos son múltiplos
Definir la función
divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]
tal que (divideSiTodosMultiplos x ys) es justo la lista de los cocientes de los elementos de ys entre x si todos son múltiplos de de número no nulo x y Nothing en caso contrario. Por ejemplo,
divideSiTodosMultiplos 2 [6,10,4] == Just [3,5,2] divideSiTodosMultiplos 2 [6,10,5] == Nothing
Renombramiento de un árbol
Los árboles binarios se pueden representar mediante el tipo Arbol definido por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq, Foldable, Functor)
Por ejemplo, el árbol
"C"
/ \
/ \
/ \
"B" "A"
/ \ / \
"A" "B" "B" "C"
se puede definir por
ej1 :: Arbol String ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))
Definir la función
renombraArbol :: Arbol t -> Arbol Int
tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor de los nodos y hojas de a por números tales que tengan el mismo valor si y sólo si coincide su contenido. Por ejemplo,
λ> renombraArbol ej1 N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))
Gráficamente,
2
/ \
/ \
/ \
1 0
/ \ / \
0 1 1 2
Empiezan con mayúscula
Definir la función
conMayuscula :: String -> Int
tal que (conMayuscula cs) es el número de palabras de cs que empiezan con mayúscula. Por ejemplo.
conMayuscula "Juan vive en Sevilla o en Huelva" == 3
Límite de sucesiones
Definir la función
limite :: (Double -> Double) -> Double -> Double
tal que (limite f a) es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,
limite (\n -> (2*n+1)/(n+5)) 0.001 == 1.9900110987791344 limite (\n -> (1+1/n)**n) 0.001 == 2.714072874546881
Eliminación de n elementos
Definir la función
elimina :: Int -> [a] -> [[a]]
tal que (elimina n xs) es la lista de las listas obtenidas eliminando n elementos de xs. Por ejemplo,
elimina 0 "abcd" == ["abcd"] elimina 1 "abcd" == ["bcd","acd","abd","abc"] elimina 2 "abcd" == ["cd","bd","bc","ad","ac","ab"] elimina 3 "abcd" == ["d","c","b","a"] elimina 4 "abcd" == [""] elimina 5 "abcd" == [] elimina 6 "abcd" == []
Intercalación de n copias
Definir la función
intercala :: Int -> a -> [a] -> [[a]]
tal que (intercala n x ys) es la lista de la listas obtenidas intercalando n copias de x en ys. Por ejemplo,
intercala 2 'a' "bc" == ["bcaa","baca","baac","abca","abac","aabc"] intercala 2 'a' "c" == ["caa","aca","aac"] intercala 1 'a' "c" == ["ca","ac"] intercala 0 'a' "c" == ["c"]
Sopa de letras
Las matrices se puede representar mediante tablas cuyos índices son pares de números naturales:
type Matriz a = Array (Int,Int) a
Definir la función
enLaSopa :: Eq a => [a] -> Matriz a -> Bool
tal que (enLaSopa c p) se verifica si c está en la matriz p en horizontal o en vertical. Por ejemplo, si ej1 es la matriz siguiente:
ej1 :: Matriz Char ej1 = listaMatriz ["mjtholueq", "juhoolauh", "dariouhyj", "rngkploaa"]
donde la función listaMatriz está definida por
listaMatriz :: [[a]] -> Matriz a listaMatriz xss = listArray ((1,1),(m,n)) (concat xss) where m = length xss n = length (head xss)
entonces,
enLaSopa "dar" p == True -- En horizontal a la derecha en la 3ª fila enLaSopa "oir" p == True -- En horizontal a la izquierda en la 3ª fila enLaSopa "juan" p == True -- En vertical descendente en la 2ª columna enLaSopa "kio" p == True -- En vertical ascendente en la 3ª columna enLaSopa "Juan" p == False enLaSopa "hola" p == False
N gramas
Un n-grama de una sucesión es una subsucesión contigua de n elementos.
Definir la función
nGramas :: Int -> [a] -> [[a]]
tal que (nGramas k xs) es la lista de los n-gramas de xs de longitud k. Por ejemplo,
nGramas 0 "abcd" == [] nGramas 1 "abcd" == ["a","b","c","d"] nGramas 2 "abcd" == ["ab", "bc", "cd"] nGramas 3 "abcd" == ["abc", "bcd"] nGramas 4 "abcd" == ["abcd"] nGramas 5 "abcd" == []
Entero positivo de la cadena
Definir la función
enteroPositivo :: String -> Maybe Int
tal que (enteroPositivo cs) es justo el contenido de la cadena cs, si dicho contenido es un entero positivo, y Nothing en caso contrario. Por ejemplo,
enteroPositivo "235" == Just 235 enteroPositivo "-235" == Nothing enteroPositivo "23.5" == Nothing enteroPositivo "235 " == Nothing enteroPositivo "cinco" == Nothing enteroPositivo "" == Nothing
Filtro booleano
Definir la función
filtroBooleano :: [Bool] -> [a] -> [Maybe a]
tal que (filtroBooleano xs ys) es la lista de los elementos de ys tales que el elemento de xs en la misma posición es verdadero. Por ejemplo,
λ> filtroBooleano [True,False,True] "Sevilla" [Just 'S',Nothing,Just 'v'] λ> filtroBooleano (repeat True) "abc" [Just 'a',Just 'b',Just 'c'] λ> take 3 (filtroBooleano (repeat True) [1..]) [Just 1,Just 2,Just 3] λ> take 3 (filtroBooleano (repeat False) [1..]) [Nothing,Nothing,Nothing] λ> take 3 (filtroBooleano (cycle [True,False]) [1..]) [Just 1,Nothing,Just 3]