Ir al contenido principal

Emparejamiento de árboles

Misceláneas

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

data Arbol a = N a [Arbol a]
  deriving (Show, Eq)

Por ejemplo, los árboles

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

se representan por

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

Definir la función

emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c

tal que (emparejaArboles f a1 a2) es el árbol obtenido aplicando la función f a los elementos de los árboles a1 y a2 que se encuentran en la misma posición. Por ejemplo,

λ> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []])
N 2 [N 8 []]
λ> emparejaArboles (+) ej1 ej2
N 4 [N 11 [],N 7 []]
λ> emparejaArboles (+) ej1 ej1
N 2 [N 12 [],N 6 [N 10 []]]

Leer más…

Separación por posición

Misceláneas

Definir la función

particion :: [a] -> ([a],[a])

tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,

particion [3,5,6,2]    ==  ([3,6],[5,2])
particion [3,5,6,2,7]  ==  ([3,6,7],[5,2])
particion "particion"  ==  ("priin","atco")

Leer más…

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…

Pim, Pam, Pum y divisibilidad

Misceláneas

Definir la función

sonido :: Int -> String

tal que (sonido n) escribe "Pim" si n es divisible por 3, además escribe "Pam" si n es divisible por 5 y también escribe "Pum" si n es divisible por 7. Por ejemplo,

sonido   3  ==  "Pim"
sonido   5  ==  "Pam"
sonido   7  ==  "Pum"
sonido   8  ==  ""
sonido   9  ==  "Pim"
sonido  15  ==  "PimPam"
sonido  21  ==  "PimPum"
sonido  35  ==  "PamPum"
sonido 105  ==  "PimPamPum"

Leer más…

Reiteración de una función

Misceláneas

Definir la función

reiteracion :: (a -> a) -> Int -> a -> a

tal que (reiteracion f n x) es el resultado de aplicar n veces la función f a x. Por ejemplo,

reiteracion (+1) 10 5  ==  15
reiteracion (+5) 10 0  ==  50
reiteracion (*2)  4 1  ==  16
reiteracion (5:)  4 [] ==  [5,5,5,5]

Leer más…

Elementos de una matriz con algún vecino menor

Misceláneas

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales. Su tipo se define por

type Matriz = Array (Int,Int) Int

Por ejemplo, la matriz

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

se define por

ej :: Matriz
ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]

Los vecinos de un elemento son los que están a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 sólo tiene 3 vecinos (el 4, 8 y 1).

Definir la función

algunoMenor :: Matriz -> [Int]

tal que (algunoMenor p) es la lista de los elementos de p que tienen algún vecino menor que él. Por ejemplo,

algunoMenor ej == [9,4,6,5,8,7,4,2,5,4]

pues sólo el 1 y el 3 no tienen ningún vecino menor en la matriz.

Leer más…

Enumeración de árboles binarios

Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

   data Arbol a = H a
                | N (Arbol a) a (Arbol a)
      deriving Show

Por ejemplo, el árbol

        "B"
        / \
       /   \
      /     \
    "B"     "A"
    / \     / \
  "A" "B" "C" "C"

se puede definir por

   ej1 :: Arbol String
   ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C"))

Definir la función

   enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

   λ> enumeraArbol ej1
   N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))

Gráficamente,

         3
        / \
       /   \
      /     \
     1       5
    / \     / \
   0   2   4   6

Leer más…