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             1             1
    /  \          / \           / \
   /    \        8   3         8   3
  2      3          /|\       /|\  |
 / \    / \        4 5 6     4 5 6 7
4   5  6   7

se representan por

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

Definir la función

espiral :: Arbol a -> [a]

tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,

espiral ej1  ==  [1,2,3,7,6,5,4]
espiral ej2  ==  [1,8,3,6,5,4]
espiral ej3  ==  [1,8,3,7,6,5,4]

Leer más…

Los huecos binarios de un número natural n son las listas de cer0 entre dos unos en la representación binaria de n. Por ejemplo, puesto que la representación binaria de 20 es 10100 tiene dos hecos binarios de longitudes 1 y 2. La longitud del mayor hueco binario de 529 es 4 ya que la representación binaria de 529 es 1000010001.

Definir las funciones

longMayorHuecoBinario        :: Int -> Int
graficaLongMayorHuecoBinario :: Int -> IO ()

tales que + (longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo,

longMayorHuecoBinario 20    ==  2
longMayorHuecoBinario 529   ==  4
longMayorHuecoBinario 2018  ==  3

• (graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja

Leer más…

Definir la función

divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

Leer más…

Las celdas de una retícula cuadrada se numeran consecutivamente. Por ejemplo, la numeración de la retícula cuadrada de lado 4 es

 1, 2, 3, 4
 5, 6, 7, 8
 9,10,11,12
13,14,15,16

Los números de sus celdas interiores son 6,7,10,11.

Definir la función

interiores :: Int -> [Int]

tal que (interiores n) es la lista de los números de las celdas interiores de la retícula cuadrada de lado n. Por ejemplo,

interiores 4  == [6,7,10,11]
interiores 5  == [7,8,9,12,13,14,17,18,19]
interiores 6  == [8,9,10,11,14,15,16,17,20,21,22,23,26,27,28,29]
interiores 2  == []
length (interiores 2018)  == 4064256

Comprobar con QuickCheck que el número de celdas interiores de la retícula cuadrada de lado n, con n > 1, es (n-2)^2.

Leer más…

Definir las funciones

digitosIniciales        :: [Int]
graficaDigitosIniciales :: Int -> IO ()

tales que

• digitosIniciales es la lista de los dígitos iniciales de los números naturales. Por ejemplo,

λ> take 100 digitosIniciales
[0,1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,
 3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,
 6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,
 9,9,9,9,9,9,9,9,9,9]

• (graficaDigitosIniciales n) dibuja la gráfica de los primeros n términos de la sucesión digitosIniciales. Por ejemplo, (graficaDigitosIniciales 100) dibuja

y (graficaDigitosIniciales 1000) dibuja

Leer más…

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

• El número 1 está en la sucesión.
• Si x está en la sucesión, entonces 2x, 3x y 5x también están.
• Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

sucExponentesHamming :: [(Int,Int,Int)]

cuyos elementos son los exponentes de los números de Hamming. Por ejemplo,

λ> take 20 sucExponentesHamming
[(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),
 (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),
 (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]
λ> sucExponentesHamming !! (5*10^5)
(74,82,7)

Leer más…

Los puntos de una retícula se representan mediante pares de enteros

type Punto = (Int,Int)

y los movimientos de un robot mediante el tipo

data Movimiento = N Int
                | S Int
                | E Int
                | O Int

donde (N x) significa que se mueve x unidades en la dirección norte y análogamente para las restantes direcciones (S es sur, E es este y O es oeste).

Definir la función

posicion :: [Movimiento] -> Punto

tal que (posicion ms) es la posición final de un robot que inicialmente está en el el punto (0,0) y realiza los movimientos ms. Por ejemplo,

posicion [N 3]                           ==  (0,3)
posicion [N 3, E 5]                      ==  (5,3)
posicion [N 3, E 5, S 1]                 ==  (5,2)
posicion [N 3, E 5, S 1, O 4]            ==  (1,2)
posicion [N 3, E 5, S 1, O 4, N 3]       ==  (1,5)
posicion [N 3, E 5, S 1, O 4, N 3, S 3]  ==  (1,2)

Leer más…

Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.

Una relación binaria es arbórea si

• hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
• todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).

Definir la función

arborea :: Eq a => [(a,a)] -> Bool

tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,

arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]  ==  True
arborea [(8,3),(8,5),(10,2),(2,2),(2,0)]         ==  False
arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)]  ==  False

Leer más…

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

     10
    /  \
   /    \
  8      1
 / \    / \
3   9  2   6

se puede representar por

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 9))
               (N 1 (H 2) (H 6))

La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.

Definir la función

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

tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,

maximaDistancia ejArbol                                     ==  9
maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1  (H 2) (H 6)))  ==  7
maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6)))  ==  8

Leer más…

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

     10
    /  \
   /    \
  8      2
 / \    / \
3   5  2   0

se pueden representar por

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))

Un árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y. Por ejemplo, la relación definida por el árbol anterior es [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)].

Definir la función

relacionDelArbol :: Arbol a -> [(a,a)]

tal que (relacionDelArbol a) es la relación binaria definida por el árbol a. Por ejemplo,

λ> relacionDelArbol ejArbol
[(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))
[(10,8),(10,2),(2,2),(2,0)]
λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
[(10,8),(8,3),(8,5),(10,2)]
λ> relacionDelArbol (H 10)
[]

Leer más…