Ir al contenido principal

Número de inversiones

Misceláneas

Se dice que en una sucesión de números x(1), x(2), ..., x(n) hay una inversión cuando existe un par de números x(i) > x(j), siendo i < j. Por ejemplo, en la permutación 2, 1, 4, 3 hay dos inversiones (2 antes que 1 y 4 antes que 3) y en la permutación 4, 3, 1, 2 hay cinco inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).

Definir la función

numeroInversiones :: Ord a => [a] -> Int

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

numeroInversiones [2,1,4,3]  ==  2
numeroInversiones [4,3,1,2]  ==  5

Leer más…

Descomposiciones triangulares

Teoría de números

Los números triangulares se forman como sigue

*     *      *
     * *    * *
           * * *
1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Definir la función

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

tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,

λ> descomposicionesTriangulares3 4
[]
λ> descomposicionesTriangulares3 5
[(1,1,3)]
λ> descomposicionesTriangulares3 12
[(1,1,10),(3,3,6)]
λ> descomposicionesTriangulares3 30
[(1,1,28),(3,6,21),(10,10,10)]
λ> descomposicionesTriangulares3 61
[(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
λ> descomposicionesTriangulares3 52
[(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
λ> descomposicionesTriangulares3 82
[(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
λ> length (descomposicionesTriangulares3 (5*10^5))
124

Leer más…

Índices de valores verdaderos

Misceláneas

Definir la función

indicesVerdaderos :: [Int] -> [Bool]

tal que (indicesVerdaderos xs) es la lista infinita de booleanos tal que sólo son verdaderos los elementos cuyos índices pertenecen a la lista estrictamente creciente xs. Por ejemplo,

λ> take 6 (indicesVerdaderos [1,4])
[False,True,False,False,True,False]
λ> take 6 (indicesVerdaderos [0,2..])
[True,False,True,False,True,False]
λ> take 3 (indicesVerdaderos [])
[False,False,False]
λ> take 6 (indicesVerdaderos [1..])
[False,True,True,True,True,True]
λ> last (take (8*10^7) (indicesVerdaderos [0,5..]))
False

Leer más…

Código de las alergias

Misceláneas

Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:

Huevos ........   1
Cacahuetes ....   2
Mariscos ......   4
Fresas ........   8
Tomates .......  16
Chocolate .....  32
Polen .........  64
Gatos ......... 128

Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).

Los alérgenos se representan mediante el siguiente tipo de dato

data Alergeno = Huevos
              | Cacahuetes
              | Mariscos
              | Fresas
              | Tomates
              | Chocolate
              | Polen
              | Gatos
  deriving (Enum, Eq, Show, Bounded)

Definir la función

alergias :: Int -> [Alergeno]

tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,

λ> alergias 1
[Huevos]
λ> alergias 2
[Cacahuetes]
λ> alergias 3
[Huevos,Cacahuetes]
λ> alergias 5
[Huevos,Mariscos]
λ> alergias 255
[Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]

Leer más…

Lista cuadrada

Misceláneas

Definir la función

listaCuadrada :: Int -> a -> [a] -> [[a]]

tal que (listaCuadrada n x xs) es una lista de n listas de longitud n formadas con los elementos de xs completada con x, si no xs no tiene suficientes elementos. Por ejemplo,

listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Máximos locales

Misceláneas

Un máximo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

maximosLocales :: Ord a => [a] -> [a]

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
maximosLocales [1..100]             ==  []
maximosLocales "adbpmqexyz"         ==  "dpq"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Matrices de Toepliz

Misceláneas

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Primos equidistantes

Misceláneas

Definir la función

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

tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,

take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]
primosEquidistantes 4 !! (10^5) ==  (18467047,18467051)

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Anagramas

Misceláneas

Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, "mora" y "roma" son anagramas de "amor".

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Diagonales principales

Misceláneas

La lista de las diagonales principales de la matriz

1  2  3  4
5  6  7  8
9 10 11 12

es

[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Definir la función

diagonalesPrincipales :: Array (Int,Int) a -> [[a]]

tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo,

λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…