TAD de las pilas: Máximo elemento de una pila
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
maxPila :: Ord a => Pila a -> a |
tal que maxPila p sea el mayor de los elementos de la pila p. Por ejemplo,
|
1 2 |
λ> maxPila (apila 3 (apila 5 (apila 1 vacia))) 5 |
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 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (pilaAlista) import Test.QuickCheck -- 1ª solución -- =========== maxPila1 :: Ord a => Pila a -> a maxPila1 p | esVacia dp = cp | otherwise = max cp (maxPila1 dp) where cp = cima p dp = desapila p -- 2ª solución -- =========== -- Se usará la función pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 maxPila2 :: Ord a => Pila a -> a maxPila2 = maximum . pilaAlista -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_maxPila :: Pila Int -> Property prop_maxPila p = not (esVacia p) ==> maxPila1 p == maxPila2 p -- La comprobación es -- λ> quickCheck prop_maxPila -- +++ OK, passed 100 tests; 17 discarded. |
|
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 |
from copy import deepcopy from typing import TypeVar from hypothesis import assume, given from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) from src.transformaciones_pilas_listas import pilaAlista A = TypeVar('A', int, float, str) # 1ª solución # =========== def maxPila1(p: Pila[A]) -> A: cp = cima(p) dp = desapila(p) if esVacia(dp): return cp return max(cp, maxPila1(dp)) # 2ª solución # =========== # Se usará la función pilaAlista del ejercicio # "Transformaciones entre pilas y listas" que se encuentra en # https://bit.ly/3ZHewQ8 def maxPila2(p: Pila[A]) -> A: return max(pilaAlista(p)) # 3ª solución # =========== def maxPila3Aux(p: Pila[A]) -> A: cp = p.cima() p.desapila() if esVacia(p): return cp return max(cp, maxPila3Aux(p)) def maxPila3(p: Pila[A]) -> A: q = deepcopy(p) return maxPila3Aux(q) # 4ª solución # =========== def maxPila4Aux(p: Pila[A]) -> A: r = p.cima() while not esVacia(p): cp = p.cima() if cp > r: r = cp p.desapila() return r def maxPila4(p: Pila[A]) -> A: q = deepcopy(p) return maxPila4Aux(q) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_maxPila(p: Pila[int]) -> None: assume(not esVacia(p)) r = maxPila1(p) assert maxPila2(p) == r assert maxPila3(p) == r assert maxPila4(p) == r # La comprobación es # src> poetry run pytest -q maxPila.py # 1 passed in 0.25s |
La función «maxPila» se puede definir de la siguiente manera: