Árboles – Exercitium

Árbol de factorización

José A. Alonso, 3-enero-2023, Haskell y Python

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

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

Leer más →

Elementos del nivel k de un árbol

José A. Alonso, 2-enero-2023, Haskell y Python

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

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

Leer más →

Existencia de elementos del árbol que verifican una propiedad

José A. Alonso, 30-diciembre-2022, Haskell y Python

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

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

Leer más →

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

José A. Alonso, 23-diciembre-2022, Haskell y Python

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]

Leer más →

Etiqueta: Árboles

Valor de un árbol booleano

Árbol de factorización

Elementos del nivel k de un árbol

Existencia de elementos del árbol que verifican una propiedad

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

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

Subscribe to Blog via Email

Entradas recientes

Etiquetas