Subárbol de profundidad dada
El árbol binario
|
1 2 3 4 5 6 |
9 / \ / \ 3 7 / \ 2 4 |
se puede representar por
|
1 |
N 9 (N 3 (H 2) (H 4)) (H 7) |
El tipo de los árboles binarios se puede definir por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
La función take está definida por
|
1 2 3 4 |
take :: Int -> [a] -> [a] take 0 = [] take (n+1) [] = [] take (n+1) (x:xs) = x : take n xs |
Definir la función
|
1 |
takeArbol :: Int -> Arbol a -> Arbol a |
tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,
|
1 2 3 4 |
takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) |
Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) takeArbol :: Int -> Arbol a -> Arbol a takeArbol _ (H x) = H x takeArbol 0 (N x _ _) = H x takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d) -- Generador para las comprobaciones -- ================================= -- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo, -- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int)) -- N 0 (H 0) (H 0) -- N 1 (N (-2) (H (-1)) (H 1)) (H 2) -- N 3 (H 1) (H 2) -- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4)) -- H 7 -- N (-8) (H (-8)) (H 9) -- H 2 -- N (-1) (H 7) (N 9 (H (-2)) (H (-8))) -- H (-3) -- N 0 (N 16 (H (-14)) (H (-18))) (H 7) -- N (-16) (H 18) (N (-19) (H (-15)) (H (-18))) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario 0 = H <$> arbitrary arbolArbitrario n = oneof [H <$> arbitrary, N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)] -- Arbol es subclase de Arbitrary instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- Función auxiliar para la comprobación -- ===================================== -- (profundidad x) es la profundidad del árbol x. Por ejemplo, -- profundidad (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 -- profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7)) == 3 -- profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4))) == 2 profundidad :: Arbol a -> Int profundidad (H _) = 0 profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_takeArbol :: Int -> Arbol Int -> Property prop_takeArbol n x = n >= 0 ==> profundidad (takeArbol n x) <= n -- La comprobación es -- λ> quickCheck prop_takeArbol -- +++ OK, passed 100 tests. |
|
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 |
from dataclasses import dataclass from random import choice, randint from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st 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 takeArbol(n: int, a: Arbol[A]) -> Arbol[A]: match (n, a): case (_, H(x)): return H(x) case (0, N(x, _, _)): return H(x) case (n, N(x, i, d)): return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d)) assert False # Generador para las comprobaciones # ================================= # (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, # >>> arbolArbitrario(4) # N(x=2, i=H(x=1), d=H(x=9)) # >>> arbolArbitrario(4) # H(x=10) # >>> arbolArbitrario(4) # N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6)) def arbolArbitrario(n: int) -> Arbol[int]: if n <= 1: return H(randint(0, 10)) m = n // 2 return choice([H(randint(0, 10)), N(randint(0, 10), arbolArbitrario(m), arbolArbitrario(m))]) # Función auxiliar para la comprobación # ===================================== # profundidad(x) es la profundidad del árbol x. Por ejemplo, # profundidad(N(9, N(3, H(2), H(4)), H(7))) == 2 # profundidad(N(9, N(3, H(2), N(1, H(4), H(5))), H(7))) == 3 # profundidad(N(4, N(5, H(4), H(2)), N(3, H(7), H(4)))) == 2 def profundidad(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + max(profundidad(i), profundidad(d)) assert False # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=12), st.integers(min_value=1, max_value=10)) def test_takeArbol(n: int, m: int) -> None: x = arbolArbitrario(m) assert profundidad(takeArbol(n, x)) <= n # La comprobación es # src> poetry run pytest -q subarbol_de_profundidad_dada.py # 1 passed in 0.23s |