Ir al contenido principal

Clausura de un conjunto respecto de una función

Misceláneas

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]

Leer más…

Números con todos sus dígitos primos

Misceláneas

La sucesión A046034 de la OEIS (The On-Line Encyclopedia of Integer Sequences) está formada por los números tales que todos sus dígitos son primos. Los primeros términos de A046034 son

2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223

Definir la constante

numerosDigitosPrimos :: [Int]

cuyos elementos son los términos de la sucesión A046034. Por ejemplo,

λ> take 22 numerosDigitosPrimos
[2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]

Leer más…

Matriz permutación

Misceláneas

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

Leer más…

Inserción en árboles binarios de búsqueda

Misceláneas

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:

   5
  / \
 /   \
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))

Leer más…

Producto de matrices como listas de listas

Misceláneas

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]]

Leer más…

Todas tienen par

Misceláneas

Definir el predicado

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

Leer más…

Producto cartesiano de una familia de conjuntos

Misceláneas

Definir la función

producto :: [[a]] -> [[a]]

tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,

λ> producto [[1,3],[2,5]]
[[1,2],[1,5],[3,2],[3,5]]
λ> 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 []
[[]]

Leer más…

Código Morse

Misceláneas

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

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
 "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
 "..-","...-",".--","-..-","-.--","--..",".----","..---","...--",
 "....-",".....","-....","--...","---..","----.","-----"]

Ayuda: Se puede usar la función splitOn de la librería Data.List.Split.

Leer más…