Definir la función

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

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1
λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> longitudMayorSublistaCreciente2 xs
61
λ> longitudMayorSublistaCreciente3 xs
61

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Leer más…

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

sylvester        :: Integer -> Integer
graficaSylvester :: Integer -> Integer -> IO ()

tales que

• (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

λ> [sylvester n | n <- [0..7]]
[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
λ> length (show (sylvester 25))
6830085

• (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
• (graficaSylvester 3 30) dibuja
• (graficaSylvester 4 30) dibuja
• (graficaSylvester 5 30) dibuja

Leer más…

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

take 5 (emparejables 2   10)  ==  [[3,7]]
take 5 (emparejables 3   10)  ==  []
take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
take 5 (emparejables 4  100)  ==  []
take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

Leer más…

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la constante

pandigitalesPrimos :: [Int]

tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,

take 3 pandigitalesPrimos       ==  [7652413,7642513,7641253]
2143 `elem` pandigitalesPrimos  ==  True
length pandigitalesPrimos       ==  538

Leer más…

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

Leer más…

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"

Leer más…

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
mayorCapicuaP 6  ==  999000000999
mayorCapicuaP 7  ==  99956644665999

Leer más…

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (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 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]

Leer más…

El sistema D'Hondt es una fórmula 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)]

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,

λ> reparto 7 [340000,280000,160000,60000,15000]
[(1,3),(2,3),(3,1)]
λ> 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.

Leer más…

La conjetura de las familias estables por uniones fue planteada por Péter Frankl en 1979 y aún sigue abierta.

Una familia de conjuntos es estable por uniones si la unión de dos conjuntos cualesquiera de la familia pertenece a la familia. Por ejemplo, {∅, {1}, {2}, {1,2}, {1,3}, {1,2,3}} es estable por uniones; pero {{1}, {2}, {1,3}, {1,2,3}} no lo es.

La conjetura afirma que toda familia no vacía estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de la familia.

Definir las funciones

esEstable :: Ord a => Set (Set a) -> Bool
familiasEstables :: Ord a => Set a -> Set (Set (Set a))
mayoritarios :: Ord a => Set (Set a) -> [a]
conjeturaFrankl :: Int -> Bool

tales que

• (esEstable f) se verifica si la familia f es estable por uniones. Por ejemplo,

λ> esEstable (fromList [empty, fromList [1,2], fromList [1..5]])
True
λ> esEstable (fromList [empty, fromList [1,7], fromList [1..5]])
False
λ> esEstable (fromList [fromList [1,2], singleton 3, fromList [1..3]])
True

• (familiasEstables c) es el conjunto de las familias estables por uniones formadas por elementos del conjunto c. Por ejemplo,

λ> familiasEstables (fromList [1..2])
fromList
  [ fromList []
  , fromList [fromList []]
  , fromList [fromList [],fromList [1]]
  , fromList [fromList [],fromList [1],fromList [1,2]],
    fromList [fromList [],fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [1,2]]
  , fromList [fromList [],fromList [1,2],fromList [2]]
  , fromList [fromList [],fromList [2]]
  , fromList [fromList [1]]
  , fromList [fromList [1],fromList [1,2]]
  , fromList [fromList [1],fromList [1,2],fromList [2]]
  , fromList [fromList [1,2]]
  , fromList [fromList [1,2],fromList [2]]
  , fromList [fromList [2]]]
λ> size (familiasEstables (fromList [1,2]))
14
λ> size (familiasEstables (fromList [1..3]))
122
λ> size (familiasEstables (fromList [1..4]))
4960

• (mayoritarios f) es la lista de elementos que pertenecen al menos a la mitad de los conjuntos de la familia f. Por ejemplo,

mayoritarios (fromList [empty, fromList [1,3], fromList [3,5]]) == [3]
mayoritarios (fromList [empty, fromList [1,3], fromList [4,5]]) == []

• (conjeturaFrankl n) se verifica si para toda familia f formada por elementos del conjunto {1,2,...,n} no vacía, estable por uniones y distinta de {∅} posee algún elemento que pertenece al menos a la mitad de los conjuntos de f. Por ejemplo.

conjeturaFrankl 2  ==  True
conjeturaFrankl 3  ==  True
conjeturaFrankl 4  ==  True

Leer más…