TAD de las colas: Último elemento
Utilizando el tipo abstracto de datos de las colas, definir la función
1 |
ultimoCola :: Cola a -> a |
tal que ultimoCola c
es el último elemento de la cola c
. Por ejemplo,
1 2 |
ultimoCola (inserta 3 (inserta 5 (inserta 2 vacia))) == 3 ultimoCola (inserta 2 vacia) == 2 |
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 |
import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia) import Transformaciones_colas_listas (colaAlista) import Test.QuickCheck -- 1ª solución -- =========== ultimoCola :: Cola a -> a ultimoCola c | esVacia c = error "cola vacia" | esVacia rc = pc | otherwise = ultimoCola rc where pc = primero c rc = resto c -- 2ª solución -- =========== -- Se usarán la función colaAlista del ejercicio -- "Transformaciones entre colas y listas" que se encuentra en -- https://bit.ly/3Xv0oIt ultimoCola2 :: Cola a -> a ultimoCola2 c | esVacia c = error "cola vacia" | otherwise = last (colaAlista c) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ultimoCola :: Cola Int -> Property prop_ultimoCola c = not (esVacia c) ==> ultimoCola c == ultimoCola2 c -- La comprobación es -- λ> quickCheck prop_ultimoCola -- +++ OK, passed 100 tests; 16 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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
from copy import deepcopy from typing import TypeVar from hypothesis import assume, given from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero, resto, vacia) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A') # 1ª solución # =========== def ultimoCola(c: Cola[A]) -> A: if esVacia(c): raise ValueError("cola vacia") pc = primero(c) rc = resto(c) if esVacia(rc): return pc return ultimoCola(rc) # 2ª solución # =========== def ultimoCola2Aux(c: Cola[A]) -> A: if c.esVacia(): raise ValueError("cola vacia") pc = primero(c) c.resto() if c.esVacia(): return pc return ultimoCola2(c) def ultimoCola2(c: Cola[A]) -> A: _c = deepcopy(c) return ultimoCola2Aux(_c) # 3ª solución # =========== def ultimoCola3(c: Cola[A]) -> A: if esVacia(c): raise ValueError("cola vacia") while not esVacia(resto(c)): c = resto(c) return primero(c) # 4ª solución # =========== def ultimoCola4Aux(c: Cola[A]) -> A: if c.esVacia(): raise ValueError("cola vacia") r = primero(c) while not c.esVacia(): c.resto() if not c.esVacia(): r = primero(c) return r def ultimoCola4(c: Cola[A]) -> A: _c = deepcopy(c) return ultimoCola4Aux(_c) # 5ª solución # =========== # Se usarán la función colaAlista del ejercicio # "Transformaciones entre colas y listas" que se encuentra en # https://bit.ly/3Xv0oIt def ultimoCola5(c: Cola[A]) -> A: if esVacia(c): raise ValueError("cola vacia") return colaAlista(c)[-1] # Comprobación de equivalencia # ============================ # La propiedad es @given(c=colaAleatoria()) def test_ultimoCola(c: Cola[int]) -> None: assume(not esVacia(c)) r = ultimoCola(c) assert ultimoCola2(c) == r assert ultimoCola3(c) == r assert ultimoCola4(c) == r assert ultimoCola5(c) == r # La comprobación es # src> poetry run pytest -q ultimoCola.py # 1 passed in 0.25s |