Ir al contenido principal

Expresiones equilibradas

Misceláneas

Una cadena de paréntesis abiertos y cerrados está equilibrada si a cada paréntesis abierto le corresponde uno cerrado y los restantes están equilibrados. Por ejemplo, "(()())" está equilibrada, pero "())(()" no lo está.

Definir la función

equilibrada :: String -> Bool

tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,

equilibrada "(()())"          ==  True
equilibrada "())(()"          ==  False
equilibrada "()"              ==  True
equilibrada ")(()))"          ==  False
equilibrada "("               ==  False
equilibrada "(())((()())())"  == True

Leer más…

Reconocimiento de relaciones funcionales entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.

Definir la función

esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

tal que (esFuncional r) r se verifica si la relación r es funcional. Por ejemplo,

esFuncional [(2,4),(1,5),(3,4)]        ==  True
esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False

Leer más…

Menor x tal que los x múltiplos de n contienen todos los dígitos

Misceláneas

Definir la función

menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, ... y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

92                                    contiene  [2,9]
92 y 92×2                             contienen [1,2,4,8,9]
92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

menorX 92          ==  6
menorX 2967        ==  3
menorX 266         ==  4
menorX 18          ==  5
menorX 2           ==  45
menorX 125         ==  72
menorX 1234567890  ==  1
maximum [menorX n | n <- [1..3000]]  ==  72
minimum [menorX n | n <- [1..3000]]  ==  3

Leer más…

Conjunto de relaciones binarias entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Definir las funciones

relaciones  :: [a] -> [b] -> [[(a,b)]]
nRelaciones :: [a] -> [b] -> Integer

tales que

  • (relaciones xs ys) es el conjunto de las relaciones del conjunto xs en el conjunto ys. Por ejemplo,
λ> relaciones [1] [2]
[[],[(1,2)]]
λ> relaciones [1] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)]]
λ> relaciones [1,3] [2]
[[],[(1,2)],[(3,2)],[(1,2),(3,2)]]
λ> relaciones [1,3] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
 [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
 [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
 [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
 [(1,2),(1,4),(3,2),(3,4)]]
λ> relaciones [] []
[[]]
λ> relaciones [] [2]
[[]]
λ> relaciones [1] []
[[]]
  • (nRelaciones xs ys) es el número de relaciones del conjunto xs en el conjunto ys. Por ejemplo,
nRelaciones [1,2] [4,5]    ==  16
nRelaciones [1,2] [4,5,6]  ==  64
nRelaciones [0..9] [0..9]  ==  1267650600228229401496703205376

Leer más…

Sumas de dos cuadrados

Misceláneas

Definir la función

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

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]
sumasDe2Cuadrados 32                ==  [(4,4)]
sumasDe2Cuadrados 55                ==  []
sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]
length (sumasDe2Cuadrados (10^12))  ==  7

Leer más…

Mayor producto de las ramas de un árbol

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
               deriving Show

Por ejemplo, los árboles

   1              3
 /  \            /|\
2   3           / | \
    |          5  4  7
    4          |     /\
               6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

λ> mayorProducto (N 1 [N 2 [], N  3 []])
3
λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
12
λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
12
λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
90
λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
0
λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
λ> mayorProducto a
84

Leer más…

Sucesión contadora

Misceláneas

Definir las siguientes funciones

numeroContado           :: Integer -> Integer
contadora               :: Integer -> [Integer]
lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

tales que

  • (numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,
numeroContado 1                 == 11
numeroContado 114213            == 31121314
numeroContado 1111111111111111  == 161
  • (contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,
λ> take 14 (contadora 1)
[1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,
31221324,21322314,21322314]
λ> take 14 (contadora 5)
[5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,
3132132415,3122331415,3122331415,3122331415,3122331415]
  • (lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,
λ> lugarPuntoFijoContadora 1 100
Just 12
λ> contadora 1 !! 11
31221324
λ> contadora 1 !! 12
21322314
λ> contadora 1 !! 13
21322314
λ> lugarPuntoFijoContadora 1 10
Nothing
λ> lugarPuntoFijoContadora 5 20
Just 10
λ> lugarPuntoFijoContadora 40 200
Nothing

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz.

Leer más…

Punto de inflexión

Misceláneas

Definir la función

inflexion :: Ord a => [a] -> Maybe a

tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,

inflexion [2,2,3,5,4,6]    ==  Just 4
inflexion [9,8,6,7,10,10]  ==  Just 7
inflexion [2,2,3,5]        ==  Nothing
inflexion [5,3,2,2]        ==  Nothing

Leer más…

Número de divisores

Misceláneas

Definir la función

numeroDivisores :: Integer -> Integer

tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,

numeroDivisores 12  ==  6
numeroDivisores 25  ==  3
length (show (numeroDivisores (product (take 20000 primes)))) == 6021

Leer más…

Cadenas de sumas de factoriales de los dígitos

Misceláneas

Dado un número n se considera la sucesión cuyo primer término es n y los restantes se obtienen sumando los factoriales de los dígitos del anterior. Por ejemplo, la sucesión que empieza en 69 es

    69
363600  (porque 6! + 9! = 363600)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 0! = 1454)
   169  (porque 1! + 4! + 5! + 4! = 169)
363601  (porque 1! + 6! + 9! = 363601)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 1! = 1454)
......

La cadena correspondiente a un número n son los términos de la sucesión que empieza en n hasta la primera repetición de un elemento en la sucesión. Por ejemplo, la cadena de 69 es

[69,363600,1454,169,363601,1454]

Consta de una parte no periódica ([69,363600]) y de una periódica ([1454,169,363601]).

Definir las funciones

cadena  :: Integer -> [Integer]
periodo :: Integer -> [Integer]

tales que

  • (cadena n es la cadena correspondiente al número n. Por ejemplo,
cadena 69    ==  [69,363600,1454,169,363601,1454]
cadena 145   ==  [145,145]
cadena 78    ==  [78,45360,871,45361,871]
cadena 569   ==  [569,363720,5775,10320,11,2,2]
cadena 3888  ==  [3888,120966,364324,782,45362,872,45362]
maximum [length (cadena n) | n <- [1..5000]]  ==  61
length (cadena 1479)                          ==  61
  • (periodo n) es la parte periódica de la cadena de n. Por ejemplo,
periodo 69    ==  [169,363601,1454]
periodo 145   ==  [145]
periodo 78    ==  [45361,871]
periodo 569   ==  [2]
periodo 3888  ==  [872,45362]
maximum [length (periodo n) | n <- [1..5000]]  ==  3
length (periodo 1479)                          ==  3

Leer más…