En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los 3 primeros ejercicios de la relación 9 sobre tipos de dato algebraico.
Los ejercicios y su solución se muestran a continuación
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En esta relación se presenta ejercicios sobre distintos tipos de -- datos algebraicos. Concretamente, -- * Árboles binarios: -- + Árboles binarios con valores en los nodos. -- + Árboles binarios con valores en las hojas. -- + Árboles binarios con valores en las hojas y en los nodos. -- + Árboles booleanos. -- * Árboles generales -- * Expresiones aritméticas -- + Expresiones aritméticas básicas. -- + Expresiones aritméticas con una variable. -- + Expresiones aritméticas con varias variables. -- + Expresiones aritméticas generales. -- + Expresiones aritméticas con tipo de operaciones. -- * Expresiones vectoriales -- -- Los ejercicios corresponden al tema 9 que se encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-17/temas/tema-9.html -- --------------------------------------------------------------------- -- Ejercicio 1.1. Los árboles binarios con valores en los nodos se -- pueden definir por -- data Arbol1 a = H1 -- | N1 a (Arbol1 a) (Arbol1 a) -- deriving (Show, Eq) -- Por ejemplo, el árbol -- 9 -- / \ -- / \ -- 8 6 -- / \ / \ -- 3 2 4 5 -- se puede representar por -- N1 9 (N1 8 (N1 3 H1 H1) (N1 2 H1 H1)) (N1 6 (N1 4 H1 H1) (N1 5 H1 H1)) -- -- Definir por recursión la función -- sumaArbol :: Num a => Arbol1 a -> a -- tal (sumaArbol x) es la suma de los valores que hay en el árbol -- x. Por ejemplo, -- ghci> sumaArbol (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1)) -- 21 -- --------------------------------------------------------------------- data Arbol1 a = H1 | N1 a (Arbol1 a) (Arbol1 a) deriving (Show, Eq) sumaArbol :: Num a => Arbol1 a -> a sumaArbol H1 = 0 sumaArbol (N1 x i d) = x + sumaArbol i + sumaArbol d -- --------------------------------------------------------------------- -- Ejercicio 1.2. Definir la función -- mapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b -- tal que (mapArbol f x) es el árbol que resulta de sustituir cada nodo -- n del árbol x por (f n). Por ejemplo, -- ghci> mapArbol (+1) (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1)) -- N1 3 (N1 6 (N1 4 H1 H1) (N1 8 H1 H1)) (N1 5 H1 H1) -- --------------------------------------------------------------------- mapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b mapArbol _ H1 = H1 mapArbol f (N1 x i d) = N1 (f x) (mapArbol f i) (mapArbol f d) -- --------------------------------------------------------------------- -- Ejercicio 1.3. Definir la función -- ramaIzquierda :: Arbol1 a -> [a] -- tal que (ramaIzquierda a) es la lista de los valores de los nodos de -- la rama izquierda del árbol a. Por ejemplo, -- ghci> ramaIzquierda (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1)) -- [2,5,3] -- --------------------------------------------------------------------- ramaIzquierda :: Arbol1 a -> [a] ramaIzquierda H1 = [] ramaIzquierda (N1 x i d) = x : ramaIzquierda i -- --------------------------------------------------------------------- -- Ejercicio 1.4. Diremos que un árbol está balanceado si para cada nodo -- v la diferencia entre el número de nodos (con valor) de sus subárboles -- izquierdo y derecho es menor o igual que uno. -- -- Definir la función -- balanceado :: Arbol1 a -> Bool -- tal que (balanceado a) se verifica si el árbol a está balanceado. Por -- ejemplo, -- balanceado (N1 5 H1 (N1 3 H1 H1)) == True -- balanceado (N1 5 H1 (N1 3 (N1 4 H1 H1) H1)) == False -- --------------------------------------------------------------------- balanceado :: Arbol1 a -> Bool balanceado H1 = True balanceado (N1 _ i d) = abs (numeroNodos i - numeroNodos d) <= 1 && balanceado i && balanceado d -- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo, -- numeroNodos (N1 5 H1 (N1 3 H1 H1)) == 2 numeroNodos :: Arbol1 a -> Int numeroNodos H1 = 0 numeroNodos (N1 _ i d) = 1 + numeroNodos i + numeroNodos d -- --------------------------------------------------------------------- -- Ejercicio 2. Los árboles binarios con valores en las hojas se pueden -- definir por -- data Arbol2 a = H2 a -- | N2 (Arbol2 a) (Arbol2 a) -- deriving Show -- Por ejemplo, los árboles -- árbol1 árbol2 árbol3 árbol4 -- o o o o -- / \ / \ / \ / \ -- 1 o o 3 o 3 o 1 -- / \ / \ / \ / \ -- 2 3 1 2 1 4 2 3 -- se representan por -- arbol1, arbol2, arbol3, arbol4 :: Arbol2 Int -- arbol1 = N2 (H2 1) (N2 (H2 2) (H2 3)) -- arbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3) -- arbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3) -- arbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1) -- -- Definir la función -- igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool -- tal que (igualBorde t1 t2) se verifica si los bordes de los árboles -- t1 y t2 son iguales. Por ejemplo, -- igualBorde arbol1 arbol2 == True -- igualBorde arbol1 arbol3 == False -- igualBorde arbol1 arbol4 == False -- --------------------------------------------------------------------- data Arbol2 a = N2 (Arbol2 a) (Arbol2 a) | H2 a deriving Show arbol1, arbol2, arbol3, arbol4 :: Arbol2 Int arbol1 = N2 (H2 1) (N2 (H2 2) (H2 3)) arbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3) arbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3) arbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1) igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool igualBorde t1 t2 = borde t1 == borde t2 -- (borde t) es el borde del árbol t; es decir, la lista de las hojas -- del árbol t leídas de izquierda a derecha. Por ejemplo, -- borde arbol4 == [2,3,1] borde :: Arbol2 a -> [a] borde (N2 i d) = borde i ++ borde d borde (H2 x) = [x] -- --------------------------------------------------------------------- -- Ejercicio 3.1. Los árboles binarios con valores en las hojas y en los -- nodos se definen por -- data Arbol3 a = H3 a -- | N3 a (Arbol3 a) (Arbol3 a) -- deriving Show -- Por ejemplo, los árboles -- 5 8 5 5 -- / \ / \ / \ / \ -- / \ / \ / \ / \ -- 9 7 9 3 9 2 4 7 -- / \ / \ / \ / \ / \ / \ -- 1 4 6 8 1 4 6 2 1 4 6 2 -- se pueden representar por -- ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int -- ej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8)) -- ej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2)) -- ej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2) -- ej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2)) -- -- Definir la función -- igualEstructura :: Arbol3 -> Arbol3 -> Bool -- tal que (igualEstructura a1 a1) se verifica si los árboles a1 y a2 -- tienen la misma estructura. Por ejemplo, -- igualEstructura ej3arbol1 ej3arbol2 == True -- igualEstructura ej3arbol1 ej3arbol3 == False -- igualEstructura ej3arbol1 ej3arbol4 == False -- --------------------------------------------------------------------- data Arbol3 a = H3 a | N3 a (Arbol3 a) (Arbol3 a) deriving Show ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int ej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8)) ej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2)) ej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2) ej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2)) igualEstructura :: Arbol3 a -> Arbol3 a -> Bool igualEstructura (H3 _) (H3 _) = True igualEstructura (N3 r1 i1 d1) (N3 r2 i2 d2) = igualEstructura i1 i2 && igualEstructura d1 d2 igualEstructura _ _ = False -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir la función -- algunoArbol :: Arbol3 t -> (t -> Bool) -> Bool -- tal que (algunoArbol a p) se verifica si algún elemento del árbol a -- cumple la propiedad p. Por ejemplo, -- algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>4) == True -- algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>7) == False -- --------------------------------------------------------------------- algunoArbol :: Arbol3 a -> (a -> Bool) -> Bool algunoArbol (H3 x) p = p x algunoArbol (N3 x i d) p = p x || algunoArbol i p || algunoArbol d p -- --------------------------------------------------------------------- -- Ejercicio 3.3. Un elemento de un árbol se dirá de nivel k si aparece -- en el árbol a distancia k de la raíz. -- -- Definir la función -- nivel :: Int -> Arbol3 a -> [a] -- tal que (nivel k a) es la lista de los elementos de nivel k del árbol -- a. Por ejemplo, -- nivel 0 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [7] -- nivel 1 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [2,9] -- nivel 2 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [5,4] -- nivel 3 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9)) == [] -- --------------------------------------------------------------------- nivel :: Int -> Arbol3 a -> [a] nivel 0 (H3 x) = [x] nivel 0 (N3 x _ _) = [x] nivel k (H3 _ ) = [] nivel k (N3 _ i d) = nivel (k-1) i ++ nivel (k-1) d -- --------------------------------------------------------------------- -- Ejercicio 3.4. Los divisores medios de un número son los que ocupan -- la posición media entre los divisores de n, ordenados de menor a -- mayor. Por ejemplo, los divisores de 60 son -- [1,2,3,4,5,6,10,12,15,20,30,60] y sus divisores medios son 6 y 10. -- -- El árbol de factorización de un número compuesto n se construye de la -- siguiente manera: -- * la raíz es el número n, -- * la rama izquierda es el árbol de factorización de su divisor -- medio menor y -- * la rama derecha es el árbol de factorización de su divisor -- medio mayor -- Si el número es primo, su árbol de factorización sólo tiene una hoja -- con dicho número. Por ejemplo, el árbol de factorización de 60 es -- 60 -- / \ -- 6 10 -- / \ / \ -- 2 3 2 5 -- -- Definir la función -- arbolFactorizacion :: Int -> Arbol3 -- tal que (arbolFactorizacion n) es el árbol de factorización de n. Por -- ejemplo, -- arbolFactorizacion 60 == N3 60 (N3 6 (H3 2) (H3 3)) (N3 10 (H3 2) (H3 5)) -- arbolFactorizacion 45 == N3 45 (H3 5) (N3 9 (H3 3) (H3 3)) -- arbolFactorizacion 7 == H3 7 -- arbolFactorizacion 14 == N3 14 (H3 2) (H3 7) -- arbolFactorizacion 28 == N3 28 (N3 4 (H3 2) (H3 2)) (H3 7) -- arbolFactorizacion 84 == N3 84 (H3 7) (N3 12 (H3 3) (N3 4 (H3 2) (H3 2))) -- --------------------------------------------------------------------- -- 1ª definición -- ============= arbolFactorizacion :: Int -> Arbol3 Int arbolFactorizacion n | esPrimo n = H3 n | otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y) where (x,y) = divisoresMedio n -- (esPrimo n) se verifica si n es primo. Por ejemplo, -- esPrimo 7 == True -- esPrimo 9 == False esPrimo :: Int -> Bool esPrimo n = divisores n == [1,n] -- (divisoresMedio n) es el par formado por los divisores medios de -- n. Por ejemplo, -- divisoresMedio 30 == (5,6) -- divisoresMedio 7 == (1,7) divisoresMedio :: Int -> (Int,Int) divisoresMedio n = (n `div` x,x) where xs = divisores n x = xs !! (length xs `div` 2) -- (divisores n) es la lista de los divisores de n. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `rem` x == 0] -- 2ª definición -- ============= arbolFactorizacion2 :: Int -> Arbol3 Int arbolFactorizacion2 n | x == 1 = H3 n | otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y) where (x,y) = divisoresMedio n -- (divisoresMedio2 n) es el par formado por los divisores medios de -- n. Por ejemplo, -- divisoresMedio2 30 == (5,6) -- divisoresMedio2 7 == (1,7) divisoresMedio2 :: Int -> (Int,Int) divisoresMedio2 n = (n `div` x,x) where m = ceiling (sqrt (fromIntegral n)) x = head [y | y <- [m..n], n `rem` y == 0] |