Menu Close

Etiqueta: Árboles

Valor de un árbol booleano

Se consideran los árboles con operaciones booleanas definidos por

   data Arbol = H Bool
              | Conj Arbol Arbol
              | Disy Arbol Arbol
              | Neg Arbol

Por ejemplo, los árboles

               Conj                            Conj
              /   \                           /   \
             /     \                         /     \
          Disy      Conj                  Disy      Conj
         /   \       /  \                /   \      /   \
      Conj    Neg   Neg True          Conj    Neg   Neg  True
      /  \    |     |                 /  \    |     |
   True False False False          True False True  False

se definen por

   ej1, ej2:: Arbol
   ej1 = Conj (Disy (Conj (H True) (H False))
                    (Neg (H False)))
              (Conj (Neg (H False))
                    (H True))
 
   ej2 = Conj (Disy (Conj (H True) (H False))
                    (Neg (H True)))
              (Conj (Neg (H False))
                    (H True))

Definir la función

   valor :: Arbol -> Bool

tal que valor a) es el resultado de procesar el árbol a realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,

   valor ej1 == True
   valor ej2 == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol = H Bool
           | Conj Arbol Arbol
           | Disy Arbol Arbol
           | Neg Arbol
 
ej1, ej2 :: Arbol
ej1 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H False)))
           (Conj (Neg (H False))
                 (H True))
 
ej2 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H True)))
           (Conj (Neg (H False))
                 (H True))
 
valor :: Arbol -> Bool
valor (H x)      = x
valor (Neg a)    = not (valor a)
valor (Conj i d) = valor i && valor d
valor (Disy i d) = valor i || valor d


Soluciones en Python

from dataclasses import dataclass
 
@dataclass
class Arbol:
    pass
 
@dataclass
class H(Arbol):
    x: bool
 
@dataclass
class Conj(Arbol):
    i: Arbol
    d: Arbol
 
@dataclass
class Disy(Arbol):
    i: Arbol
    d: Arbol
 
@dataclass
class Neg(Arbol):
    a: Arbol
 
ej1: Arbol = Conj(Disy(Conj(H(True), H(False)),
                       (Neg(H(False)))),
                  (Conj(Neg(H(False)),
                        (H(True)))))
 
ej2: Arbol = Conj(Disy(Conj(H(True), H(False)),
                       (Neg(H(True)))),
                  (Conj(Neg(H(False)),
                        (H(True)))))
 
def valor(a: Arbol) -> bool:
    match a:
        case H(x):
            return x
        case Neg(b):
            return not valor(b)
        case Conj(i, d):
            return valor(i) and valor(d)
        case Disy(i, d):
            return valor(i) or valor(d)
    assert False

Árbol de factorización

Los divisores medios de un número son los que ocupan la 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. Para los números que son cuadrados perfectos, sus divisores medios de son sus raíces cuadradas; por ejemplos, los divisores medios de 9 son 3 y 3.

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 -> Arbol

tal que arbolFactorizacion n es el árbol de factorización de n. Por ejemplo,

   arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5))
   arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3))
   arbolFactorizacion 7  == H 7
   arbolFactorizacion 9  == N 9 (H 3) (H 3)
   arbolFactorizacion 14 == N 14 (H 2) (H 7)
   arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7)
   arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2)))

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
arbolFactorizacion1 :: Int -> Arbol
arbolFactorizacion1 n
  | esPrimo n = H n
  | otherwise = N n (arbolFactorizacion1 x) (arbolFactorizacion1 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 16  ==  (4,4)
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ª solución
-- ===========
 
arbolFactorizacion2 :: Int -> Arbol
arbolFactorizacion2 n
  | x == 1    = H n
  | otherwise = N n (arbolFactorizacion2 x) (arbolFactorizacion2 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]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_arbolFactorizacion :: Int -> Property
prop_arbolFactorizacion n =
  n > 1 ==> arbolFactorizacion1 n == arbolFactorizacion2 n
 
-- La comprobación es
--    λ> quickCheck prop_arbolFactorizacion
--    +++ OK, passed 100 tests; 162 discarded.


Soluciones en Python

from dataclasses import dataclass
from math import ceil, sqrt
 
from hypothesis import given
from hypothesis import strategies as st
 
# 1ª solución
# ===========
 
@dataclass
class Arbol:
    pass
 
@dataclass
class H(Arbol):
    x: int
 
@dataclass
class N(Arbol):
    x: int
    i: Arbol
    d: Arbol
 
# divisores(n) es la lista de los divisores de n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]
 
# divisoresMedio(n) es el par formado por los divisores medios de
# n. Por ejemplo,
#    divisoresMedio(30)  ==  (5,6)
#    divisoresMedio(7)   ==  (1,7)
#    divisoresMedio(16)  ==  (4,4)
def divisoresMedio(n: int) -> tuple[int, int]:
    xs = divisores(n)
    x = xs[len(xs) // 2]
    return (n // x, x)
 
# esPrimo(n) se verifica si n es primo. Por ejemplo,
#    esPrimo(7)  ==  True
#    esPrimo(9)  ==  False
def esPrimo(n: int) -> bool:
    return divisores(n) == [1, n]
 
def arbolFactorizacion1(n: int) -> Arbol:
    if esPrimo(n):
        return H(n)
    (x, y) = divisoresMedio(n)
    return N(n, arbolFactorizacion1(x), arbolFactorizacion1(y))
 
# 2ª solución
# ===========
 
# divisoresMedio2(n) es el par formado por los divisores medios de
# n. Por ejemplo,
#    divisoresMedio2(30) ==  (5,6)
#    divisoresMedio2(7)  ==  (1,7)
#    divisoresMedio2(16) ==  (4,4)
def divisoresMedio2(n: int) -> tuple[int, int]:
    m = ceil(sqrt(n))
    x = [y for y in range(m, n + 1) if n % y == 0][0]
    return (n // x, x)
 
def arbolFactorizacion2(n: int) -> Arbol:
    if esPrimo(n):
        return H(n)
    (x, y) = divisoresMedio2(n)
    return N(n, arbolFactorizacion2(x), arbolFactorizacion2(y))
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=2, max_value=200))
def test_arbolFactorizacion(n: int) -> None:
    assert arbolFactorizacion1(n) == arbolFactorizacion2(n)
 
# La comprobación es
#    src> poetry run pytest -q arbol_de_factorizacion.py
#    1 passed in 0.14s

Elementos del nivel k de un árbol

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)

Por ejemplo, el árbol

        7
       / \
      /   \
     2     9
    / \
   5   4

se representa por

   N 7 (N 2 (H 5) (H 4)) (H 9)

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 -> Arbol a -> [a]

tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,

   nivel 0 (H 5)                          ==  [5]
   nivel 1 (H 5)                          ==  []
   nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [7]
   nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [2,9]
   nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  [5,4]
   nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9))  ==  []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
 
nivel :: Int -> Arbol a -> [a]
nivel 0 (H x)      = [x]
nivel 0 (N x _  _) = [x]
nivel _ (H _ )     = []
nivel k (N _ i d)  = nivel (k-1) i ++ nivel (k-1) d


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    x: A
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
def nivel(k: int, a: Arbol[A]) -> list[A]:
    match (k, a):
        case (0, H(x)):
            return [x]
        case (0, N(x, _, _)):
            return [x]
        case (_, H(_)):
            return []
        case (_, N(_, i, d)):
            return nivel(k - 1, i) + nivel(k - 1, d)
    assert False

Existencia de elementos del árbol que verifican una propiedad

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

Por ejemplo, el árbol

        5
       / \
      /   \
     3     2
    / \
   1   4

se representa por

   N 5 (N 3 (H 1) (H 4)) (H 2)

Definir la función

   algunoArbol :: Arbol t -> (t -> Bool) -> Bool

tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,

   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True
   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show
 
algunoArbol :: Arbol a -> (a -> Bool) -> Bool
algunoArbol (H x) p     = p x
algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p


Soluciones en Python

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    x: A
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
def algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool:
    match a:
        case H(x):
            return p(x)
        case N(x, i, d):
            return p(x) or algunoArbol(i, p) or algunoArbol(d, p)
    assert False

El tipo de los árboles binarios con valores en los nodos

1. El tipo de los árboles binarios con valores en los nodos en Haskell

El árbol, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.

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

2. El tipo de los árboles binarios con valores en los nodos en Python

El árbol binario, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))

usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.

from dataclasses import dataclass
 
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    pass
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]