Paridad de un árbol

PorJosé A. Alonso 1-diciembre-20158-diciembre-2015

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 Show

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, el árbol

        5         
       / \        
      /   \       
     9     7      
    / \   / \     
   1   4 6   8

/ \

9 7

/ \ / \

1 4 6 8

se puede representar por

   N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

1	N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

Decimos que un árbol binario es par si la mayoría de sus valores (en nodos u hojas) son pares e impar en caso contrario.

Para representar la paridad se define el tipo Paridad

   data Paridad = Par | Impar deriving (Eq, Show)

1	data Paridad = Par \| Impar deriving (Eq, Show)

Definir la función

   paridad :: Arbol3 Int -> Paridad

1	paridad :: Arbol3 Int -> Paridad

tal que (paridad a) es la paridad del árbol a. Por ejemplo,

   paridad (N 8 (N 6 (H 3) (H 4)) (H 5))  ==  Par
   paridad (N 8 (N 9 (H 3) (H 4)) (H 5))  ==  Impar

1 2	paridad (N 8 (N 6 (H 3) (H 4)) (H 5)) == Par paridad (N 8 (N 9 (H 3) (H 4)) (H 5)) == Impar

Soluciones

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

data Paridad = Par | Impar deriving (Eq, Show)  
 
paridad :: Arbol Int -> Paridad
paridad a | x > y     = Par 
          | otherwise = Impar
          where (x,y) = paridades a

-- (paridades a) es un par (x,y) donde x es el número de valores pares
-- en el árbol a e i es el número de valores impares en el árbol a. Por
-- ejemplo,  
--    paridades (N (N (H 3) 6 (H 4)) 8 (H 5))  ==  (3,2)
--    paridades (N (N (H 3) 9 (H 4)) 8 (H 5))  ==  (2,3)
paridades :: Arbol Int -> (Int,Int)
paridades (H x) | even x    = (1,0)
                | otherwise = (0,1)
paridades (N x i d) | even x    = (1+a1+a2,b1+b2)
                    | otherwise = (a1+a2,1+b1+b2)
                    where (a1,b1) = paridades i
                          (a2,b2) = paridades d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad a | x > y = Par

| otherwise = Impar

where (x,y) = paridades a

-- (paridades a) es un par (x,y) donde x es el número de valores pares

-- en el árbol a e i es el número de valores impares en el árbol a. Por

-- ejemplo,

-- paridades (N (N (H 3) 6 (H 4)) 8 (H 5)) == (3,2)

-- paridades (N (N (H 3) 9 (H 4)) 8 (H 5)) == (2,3)

paridades :: Arbol Int -> (Int,Int)

paridades (H x) | even x = (1,0)

| otherwise = (0,1)

paridades (N x i d) | even x = (1+a1+a2,b1+b2)

| otherwise = (a1+a2,1+b1+b2)

where (a1,b1) = paridades i

(a2,b2) = paridades d

12 Comentarios

Derivando automáticamente el plegamiento sobre el árbol

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
import Data.Monoid (Sum (..), getSum)

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

paridad :: Arbol Int -> Paridad
paridad a | c > 0     = Impar
          | otherwise = Par
            where   c = getSum $ foldMap (Sum . (\x -> 2 * mod x 2 - 1)) a

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}

import Data.Monoid (Sum (..), getSum)

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

deriving (Show, Functor, Foldable)

paridad :: Arbol Int -> Paridad

paridad a | c > 0 = Impar

| otherwise = Par

where c = getSum $ foldMap (Sum . (\x -> 2 * mod x 2 - 1)) a

Responder

josejuan dice:

1-diciembre-2015 a las 09:55

O usando sum (con la derivación)

Haskell

paridad :: Arbol Int -> Paridad paridad a = if s > 0 then Impar else Par where s = sum $ (x -> 2 * mod x 2 - 1) <$> a

1
2
3

paridad :: Arbol Int -> Paridad
paridad a = if s > 0 then Impar else Par
where s = sum $ (x -> 2 * mod x 2 - 1) <$> a

Responder

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

paridad :: Arbol Int -> Paridad
paridad a | balancePares a >= 0 = Par
          | otherwise           = Impar

balancePares :: Arbol Int -> Integer
balancePares x =
    case x of 
      (H n)       -> aux n
      (N n a b)   -> aux n + balancePares a + balancePares b
    where aux n = if even n then 1 else -1

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad a | balancePares a >= 0 = Par

| otherwise = Impar

balancePares :: Arbol Int -> Integer

balancePares x =

case x of

(H n) -> aux n

(N n a b) -> aux n + balancePares a + balancePares b

where aux n = if even n then 1 else -1

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

nElementos :: Arbol3 a -> Int
nElementos (H a) = 1
nElementos (N a i d) = 1 + nElementos i + nElementos d

listaArbol :: Arbol3 a -> [a]
listaArbol (H a) = [a]
listaArbol (N a i d) = [a] ++ (listaArbol i) ++ (listaArbol d)

paridad :: Arbol3 Int -> Paridad
paridad x | length (filter even (listaArbol x)) > (nElementos x `div` 2) = Par
          | otherwise = Impar

data Arbol3 a = H a

| N a (Arbol3 a) (Arbol3 a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

nElementos :: Arbol3 a -> Int

nElementos (H a) = 1

nElementos (N a i d) = 1 + nElementos i + nElementos d

listaArbol :: Arbol3 a -> [a]

listaArbol (H a) = [a]

listaArbol (N a i d) = [a] ++ (listaArbol i) ++ (listaArbol d)

paridad :: Arbol3 Int -> Paridad

paridad x | length (filter even (listaArbol x)) > (nElementos x `div` 2) = Par

| otherwise = Impar

Responder

Esta definición se puede simplificar sin necesidad de la función nElementos x, puesto que esta es precisamente la longitud de listaArbol x:

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

data Paridad = Par | Impar deriving (Eq, Show)

listaArbol :: Arbol3 a -> [a]
listaArbol (H a) = [a]
listaArbol (N a i d) = [a] ++ (listaArbol i) ++ (listaArbol d)

paridad :: Arbol3 Int -> Paridad
paridad x | length (filter even (listaArbol x)) > (length (listaArbol x) `div` 2) = Par
          | otherwise = Impar

data Arbol3 a = H a

| N a (Arbol3 a) (Arbol3 a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

listaArbol :: Arbol3 a -> [a]

listaArbol (H a) = [a]

listaArbol (N a i d) = [a] ++ (listaArbol i) ++ (listaArbol d)

paridad :: Arbol3 Int -> Paridad

paridad x | length (filter even (listaArbol x)) > (length (listaArbol x) `div` 2) = Par

| otherwise = Impar

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

-- Primero definimos la función auxiliar:
listaArbol :: Arbol a -> [a]
listaArbol (H a) = [a]
listaArbol (N a i d) = a : listaArbol i ++ listaArbol d

-- Y a continuación la que se nos pide:
paridad :: Arbol Int -> Paridad
paridad a | length (filter even xs) > div (length xs) 2 = Par
          | otherwise = Impar
                        where xs = listaArbol a

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

-- Primero definimos la función auxiliar:

listaArbol :: Arbol a -> [a]

listaArbol (H a) = [a]

listaArbol (N a i d) = a : listaArbol i ++ listaArbol d

-- Y a continuación la que se nos pide:

paridad :: Arbol Int -> Paridad

paridad a | length (filter even xs) > div (length xs) 2 = Par

| otherwise = Impar

where xs = listaArbol a

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad
paridad x | genericLength (pares x) > genericLength (impares x) = Par
          | otherwise = Impar

pares :: Arbol Int -> [Int]
pares x = filter (even) (lista2arbol x)

impares :: Arbol Int -> [Int]
impares x = filter (odd) (lista2arbol x)

lista2arbol :: Arbol Int -> [Int]
lista2arbol (H a) = [a]
lista2arbol (N a i d)= [a] ++ lista2arbol i ++ lista2arbol d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad x | genericLength (pares x) > genericLength (impares x) = Par

| otherwise = Impar

pares :: Arbol Int -> [Int]

pares x = filter (even) (lista2arbol x)

impares :: Arbol Int -> [Int]

impares x = filter (odd) (lista2arbol x)

lista2arbol :: Arbol Int -> [Int]

lista2arbol (H a) = [a]

lista2arbol (N a i d)= [a] ++ lista2arbol i ++ lista2arbol d

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad
paridad a | v > w     = Par
          | otherwise = Impar
  where (v,w) = auxParidad (0,0) a
        auxParidad :: (Int,Int) -> Arbol Int -> (Int,Int)
        auxParidad (v,w) (H a) | even a    = (v+1,w)
                               | otherwise = (v,w+1)
        auxParidad (v,w) (N a ai ad) 
                   | even a    = auxParidad (auxParidad (v+1,w) ad) ai
                   | otherwise = auxParidad (auxParidad (v,w+1) ad) ai

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

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad a | v > w = Par

| otherwise = Impar

where (v,w) = auxParidad (0,0) a

auxParidad :: (Int,Int) -> Arbol Int -> (Int,Int)

auxParidad (v,w) (H a) | even a = (v+1,w)

| otherwise = (v,w+1)

auxParidad (v,w) (N a ai ad)

| even a = auxParidad (auxParidad (v+1,w) ad) ai

| otherwise = auxParidad (auxParidad (v,w+1) ad) ai

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad
paridad e 
    | length (filter even (valArb e)) > length (filter odd (valArb e)) = Par
    | length (filter even (valArb e)) < length (filter odd (valArb e)) = Impar
 
valArb :: Arbol t -> [t]
valArb (H a)     = [a]
valArb (N a i d) = [a] ++ (valArb i) ++ (valArb d)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad e

| length (filter even (valArb e)) > length (filter odd (valArb e)) = Par

| length (filter even (valArb e)) < length (filter odd (valArb e)) = Impar

valArb :: Arbol t -> [t]

valArb (H a) = [a]

valArb (N a i d) = [a] ++ (valArb i) ++ (valArb d)

Responder

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

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad
paridad a       | elemp a > elemi a = Par
                | elemp a < elemi a = Impar

elemp (H a)     | even a            = 1
                | otherwise         = 0
elemp (N n i d) | even n            = 1+elemp i+elemp d
                | otherwise         =   elemp i+elemp d


elemi (H a)     | odd a             = 1
                | otherwise         = 0
elemi (N n i d) | odd n             = 1+elemi i+elemi d
                | otherwise         =   elemi i+elemi d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad a | elemp a > elemi a = Par

| elemp a < elemi a = Impar

elemp (H a) | even a = 1

| otherwise = 0

elemp (N n i d) | even n = 1+elemp i+elemp d

| otherwise = elemp i+elemp d

elemi (H a) | odd a = 1

| otherwise = 0

elemi (N n i d) | odd n = 1+elemi i+elemi d

| otherwise = elemi i+elemi d

Responder

paridad :: Arbol Int -> Paridad
paridad x 
    | length (filter even (elementos x)) > length(filter odd (elementos x)) = Par
    | otherwise = Impar
    where elementos (H a)       = [a]
          elementos (N a ai ad) = a : elementos ai ++ elementos ad

paridad :: Arbol Int -> Paridad

paridad x

| length (filter even (elementos x)) > length(filter odd (elementos x)) = Par

| otherwise = Impar

where elementos (H a) = [a]

elementos (N a ai ad) = a : elementos ai ++ elementos ad

Responder

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

paridad :: Arbol Int -> Paridad
paridad x 
    | length (filter even (elementos x)) > length (filter odd (elementos x)) = Par
    | otherwise = Impar
    where elementos (H a)       = [a]
          elementos (N a ai ad) = a : (elementos ai) ++ (elementos ad)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

data Paridad = Par | Impar deriving (Eq, Show)

paridad :: Arbol Int -> Paridad

paridad x

| length (filter even (elementos x)) > length (filter odd (elementos x)) = Par

| otherwise = Impar

where elementos (H a) = [a]

elementos (N a ai ad) = a : (elementos ai) ++ (elementos ad)

Responder

Paridad de un árbol

Soluciones

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico