TAD de las colas: Reconocimiento de ordenación de colas
Utilizando el tipo abstracto de datos de las colas, definir la función
1 |
ordenadaCola :: Ord a => Cola a -> Bool |
tal que ordenadaCola c
se verifica si los elementos de la cola c
están ordenados en orden creciente. Por ejemplo,
1 2 |
ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False |
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 |
import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto) import Transformaciones_colas_listas (colaAlista) import Test.QuickCheck -- 1ª solución -- =========== ordenadaCola :: Ord a => Cola a -> Bool ordenadaCola c | esVacia c = True | esVacia rc = True | otherwise = pc <= prc && ordenadaCola rc where pc = primero c rc = resto c prc = primero rc -- 2ª solución -- =========== ordenadaCola2 :: Ord a => Cola a -> Bool ordenadaCola2 = ordenadaLista . colaAlista -- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor -- a mayor. Por ejemplo, ordenadaLista :: Ord a => [a] -> Bool ordenadaLista xs = and [x <= y | (x,y) <- zip xs (tail xs)] -- La función colaAlista está definida en el ejercicio -- "Transformaciones entre colas y listas" que se encuentra en -- https://bit.ly/3Xv0oIt -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ordenadaCola :: Cola Int -> Bool prop_ordenadaCola c = ordenadaCola c == ordenadaCola2 c -- La comprobación es -- λ> quickCheck prop_ordenadaCola -- +++ 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 81 82 83 84 85 86 87 88 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero, resto, vacia) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A', int, float, str) # 1ª solución # =========== def ordenadaCola(c: Cola[A]) -> bool: if esVacia(c): return True pc = primero(c) rc = resto(c) if esVacia(rc): return True prc = primero(rc) return pc <= prc and ordenadaCola(rc) # 2ª solución # =========== # ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por # ejemplo, # >>> ordenadaLista([2, 5, 8]) # True # >>> ordenadalista([2, 8, 5]) # False def ordenadaLista(xs: list[A]) -> bool: return all((x <= y for (x, y) in zip(xs, xs[1:]))) def ordenadaCola2(p: Cola[A]) -> bool: return ordenadaLista(colaAlista(p)) # La función colaAlista está definida en el ejercicio # "Transformaciones entre colas y listas" que se encuentra en # https://bit.ly/3Xv0oIt # 3ª solución # =========== def ordenadaCola3Aux(c: Cola[A]) -> bool: if c.esVacia(): return True pc = c.primero() c.resto() if c.esVacia(): return True return pc <= c.primero() and ordenadaCola3Aux(c) def ordenadaCola3(c: Cola[A]) -> bool: _c = deepcopy(c) return ordenadaCola3Aux(_c) # 4ª solución # =========== def ordenadaCola4Aux(c: Cola[A]) -> bool: while not c.esVacia(): pc = c.primero() c.resto() if not c.esVacia() and pc > c.primero(): return False return True def ordenadaCola4(c: Cola[A]) -> bool: _c = deepcopy(c) return ordenadaCola4Aux(_c) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=colaAleatoria()) def test_ordenadaCola(p: Cola[int]) -> None: r = ordenadaCola(p) assert ordenadaCola2(p) == r assert ordenadaCola3(p) == r assert ordenadaCola4(p) == r # La comprobación es # src> poetry run pytest -q ordenadaCola.py # 1 passed in 0.27s |