Los árboles se pueden representar mediante el siguiente tipo de datos
|
1 2 |
data Arbol = N Int [Arbol] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
1 1 1 / \ / \ / \ / \ 8 3 8 3 2 6 /|\ /|\ | / \ / \ 4 2 6 4 5 6 2 4 5 5 7 |
se representan por
|
1 2 3 4 |
ej1, ej2, ej3 :: Arbol ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]] |
Definir la función
|
1 |
hojasEnNoDecreciente :: Arbol -> [Int] |
tal que (hojasEnNoDecreciente a) es el conjunto de las hojas de a que se encuentran en alguna rama no decreciente. Por ejemplo,
|
1 2 3 |
hojasEnNoDecreciente ej1 == [4,5,7] hojasEnNoDecreciente ej2 == [4,6,8] hojasEnNoDecreciente ej3 == [] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
import Data.List (sort, nub) data Arbol = N Int [Arbol] deriving Show ej1, ej2, ej3 :: Arbol ej1 = N 1 [N 2 [N 4 [], N 5 []], N 6 [N 5 [], N 7 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 2 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 2 []]] -- 1ª solución -- =========== hojasEnNoDecreciente :: Arbol -> [Int] hojasEnNoDecreciente a = sort (nub (map last (ramasNoDecrecientes a))) -- ramasNoDecrecientes ej1 == [[1,2,4],[1,2,5],[1,6,7]] -- ramasNoDecrecientes ej2 == [[1,8],[1,3,4],[1,3,6]] -- ramasNoDecrecientes ej3 == [] ramasNoDecrecientes :: Arbol -> [[Int]] ramasNoDecrecientes a = filter esNoDecreciente (ramas a) -- (ramas a) es la lista de las ramas del árbol a. Por ejemplo, -- λ> ramas ej1 -- [[1,2,4],[1,2,5],[1,6,5],[1,6,7]] -- λ> ramas ej2 -- [[1,8],[1,3,4],[1,3,2],[1,3,6]] -- λ> ramas ej3 -- [[1,8,4],[1,8,5],[1,8,6],[1,3,2]] ramas :: Arbol -> [[Int]] ramas (N x []) = [[x]] ramas (N x as) = map (x:) (concatMap ramas as) -- (esNoDecreciente xs) se verifica si la lista xs es no -- decreciente. Por ejemplo, -- esNoDecreciente [1,3,3,5] == True -- esNoDecreciente [1,3,5,3] == False esNoDecreciente :: [Int] -> Bool esNoDecreciente xs = and (zipWith (<=) xs (tail xs)) -- 2ª solución -- =========== -- hojasEnNoDecreciente ej1 == [4,5,7] -- hojasEnNoDecreciente ej2 == [4,6,8] -- hojasEnNoDecreciente ej3 == [] hojasEnNoDecreciente2 :: Arbol -> [Int] hojasEnNoDecreciente2 = sort . nub . aux where aux (N x []) = [x] aux (N x as) = concat [aux (N y bs) | (N y bs) <- as, x <= y] |