Nodos con máxima suma de hijos
Los árboles se pueden representar mediante el siguiente tipo de datos
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
1 3 / \ /|\ 2 3 / | \ | 5 4 7 4 | /|\ 6 2 8 6 |
se representan por
|
1 2 3 4 5 |
ej1, ej2 :: Arbol Int ej1 = N 1 [N 2 [], N 3 [N 4 []]] ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 8 [], N 6 []]] |
Definir la función
|
1 |
nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t] |
tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. Por ejemplo,
|
1 2 |
nodosSumaMaxima ej1 == [1] nodosSumaMaxima ej2 == [7,3] |
Soluciones
|
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import Data.List (groupBy, sort) import Data.Function (on) data Arbol a = N a [Arbol a] deriving Show ej1, ej2 :: Arbol Int ej1 = N 1 [N 2 [], N 3 [N 4 []]] ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 8 [], N 6 []]] -- 1ª solución -- =========== nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima a = [x | (s,x) <- ns, s == m] where ns = reverse (sort (nodosSumas a)) m = fst (head ns) -- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del -- árbol x y s es la suma de sus hijos. Por ejemplo, -- λ> nodosSumas ej1 -- [(5,1),(0,2),(4,3),(0,4)] -- λ> nodosSumas ej2 -- [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)] nodosSumas :: Num t => Arbol t -> [(t,t)] nodosSumas (N x []) = [(0,x)] nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as -- (raices b) es la lista de las raíces del bosque b. Por ejemplo, -- raices [ej1,ej2] == [1,3] raices :: [Arbol t] -> [t] raices = map raiz -- (raiz a) es la raíz del árbol a. Por ejemplo, -- raiz ej1 == 1 -- raiz ej2 == 3 raiz :: Arbol t -> t raiz (N x _) = x -- 2ª solución -- =========== nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima2 a = [x | (s,x) <- ns, s == m] where ns = sort (nodosOpSumas a) m = fst (head ns) -- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del -- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo, -- λ> nodosOpSumas ej1 -- [(-5,1),(0,2),(-4,3),(0,4)] -- λ> nodosOpSumas ej2 -- [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)] nodosOpSumas :: Num t => Arbol t -> [(t,t)] nodosOpSumas (N x []) = [(0,x)] nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as -- 3ª solución -- =========== nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima3 a = [x | (s,x) <- ns, s == m] where ns = sort (nodosOpSumas a) m = fst (head ns) -- 4ª solución -- =========== nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima4 a = map snd (head (groupBy (\p q -> fst p == fst q) (sort (nodosOpSumas a)))) -- 5ª solución -- =========== nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima5 a = map snd (head (groupBy ((==) `on` fst) (sort (nodosOpSumas a)))) -- 6ª solución -- =========== nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t] nodosSumaMaxima6 = map snd . head . groupBy ((==) `on` fst) . sort . nodosOpSumas |