TAD de los polinomios: Transformaciones entre polinomios y listas densas
Utilizando el tipo abstracto de datos de los polinomios definir las funciones
1 2 |
densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a] |
tales que
densaApolinomio xs
es el polinomio cuya representación densa esxs
. Por ejemplo,
1 2 |
λ> densaApolinomio [9,0,0,5,0,4,7] 9*x^6 + 5*x^3 + 4*x + 7 |
polinomioAdensa p
es la representación densa del polinomiop
. Por ejemplo,
1 2 3 4 5 |
λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero))) λ> ejPol 9*x^6 + 5*x^3 + 4*x + 7 λ> polinomioAdensa ejPol [9,0,0,5,0,4,7] |
Comprobar con QuickCheck que ambas funciones son inversas.
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 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 95 96 97 98 99 100 101 102 103 |
import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado, coefLider, restoPol) import Polinomios_Transformaciones_dispersa_y_densa (densaAdispersa, dispersaAdensa) import Polinomios_Transformaciones_polinomios_dispersas (dispersaApolinomio, polinomioAdispersa) import Polinomios_Coeficiente (coeficiente) import Data.List (sort, nub) import Test.QuickCheck -- 1ª definición de densaApolinomio -- ================================ densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a densaApolinomio [] = polCero densaApolinomio (x:xs) = consPol (length xs) x (densaApolinomio xs) -- 2ª definición de densaApolinomio -- ================================ densaApolinomio2 :: (Num a, Eq a) => [a] -> Polinomio a densaApolinomio2 = dispersaApolinomio . densaAdispersa -- La función densaAdispersa está definida en el ejercicio -- "Transformaciones entre las representaciones dispersa y densa" que se -- encuentra en https://bit.ly/3GTyIqe -- La función dispersaApolinomio se encuentra en el ejercicio -- "Transformaciones entre polinomios y listas dispersas" que se -- encuentra en https://bit.ly/41GgQaB -- Comprobación de equivalencia de densaApolinomio -- =============================================== -- La propiedad es prop_densaApolinomio :: [Int] -> Bool prop_densaApolinomio xs = densaApolinomio xs == densaApolinomio2 xs -- La comprobación es -- λ> quickCheck prop_densaApolinomio -- +++ OK, passed 100 tests. -- 1ª definición de polinomioAdensa -- ================================ polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a] polinomioAdensa p | esPolCero p = [] | otherwise = [coeficiente k p | k <- [n,n-1..0]] where n = grado p -- La función coeficiente está definida en el ejercicio -- "Coeficiente del término de grado k" que se encuentra en -- https://bit.ly/413l3oQ -- 2ª definición de polinomioAdensa -- ================================ polinomioAdensa2 :: (Num a, Eq a) => Polinomio a -> [a] polinomioAdensa2 = dispersaAdensa . polinomioAdispersa -- La función dispersaAdensa está definida en el ejercicio -- "Transformaciones entre las representaciones dispersa y densa" que se -- encuentra en https://bit.ly/3GTyIqe -- La función polinomioAdispersa se encuentra en el ejercicio -- "Transformaciones entre polinomios y listas dispersas" que se -- encuentra en https://bit.ly/41GgQaB -- Comprobación de equivalencia de polinomioAdensa -- =============================================== -- La propiedad es prop_polinomioAdensa :: Polinomio Int -> Bool prop_polinomioAdensa p = polinomioAdensa p == polinomioAdensa2 p -- La comprobación es -- λ> quickCheck prop_polinomioAdensa -- +++ OK, passed 100 tests. -- Propiedades de inversa -- ====================== -- La primera propiedad es prop_polinomioAdensa_densaApolinomio :: [Int] -> Bool prop_polinomioAdensa_densaApolinomio xs = polinomioAdensa (densaApolinomio xs') == xs' where xs' = dropWhile (== 0) xs -- La comprobación es -- λ> quickCheck prop_polinomioAdensa_densaApolinomio -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_densaApolinomio_polinomioAdensa :: Polinomio Int -> Bool prop_densaApolinomio_polinomioAdensa p = densaApolinomio (polinomioAdensa p) == p -- La comprobación es -- λ> quickCheck prop_densaApolinomio_polinomioAdensa -- +++ 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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
from typing import TypeVar from hypothesis import given from src.Polinomios_Coeficiente import coeficiente from src.Polinomios_Transformaciones_dispersa_y_densa import (densaAdispersa, densaAleatoria, dispersaAdensa) from src.Polinomios_Transformaciones_polinomios_dispersas import ( dispersaApolinomio, polinomioAdispersa) from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado, polCero, polinomioAleatorio, restoPol) A = TypeVar('A', int, float, complex) # 1ª definición de densaApolinomio # ================================ def densaApolinomio(xs: list[A]) -> Polinomio[A]: if not xs: return polCero() return consPol(len(xs[1:]), xs[0], densaApolinomio(xs[1:])) # 2ª definición de densaApolinomio # ================================ def densaApolinomio2(xs: list[A]) -> Polinomio[A]: return dispersaApolinomio(densaAdispersa(xs)) # La función densaAdispersa está definida en el ejercicio # "Transformaciones entre las representaciones dispersa y densa" que se # encuentra en https://bit.ly/3GTyIqe # La función dispersaApolinomio se encuentra en el ejercicio # "Transformaciones entre polinomios y listas dispersas" que se # encuentra en https://bit.ly/41GgQaB # Comprobación de equivalencia de densaApolinomio # =============================================== # La propiedad es @given(xs=densaAleatoria()) def test_densaApolinomio(xs: list[int]) -> None: assert densaApolinomio(xs) == densaApolinomio2(xs) # La función densaAleatoria está definida en el ejercicio # "Transformaciones entre las representaciones dispersa y densa" que se # encuentra en https://bit.ly/3GTyIqe # 1ª definición de polinomioAdensa # ================================ def polinomioAdensa(p: Polinomio[A]) -> list[A]: if esPolCero(p): return [] n = grado(p) return [coeficiente(k, p) for k in range(n, -1, -1)] # La función coeficiente está definida en el ejercicio # "Coeficiente del término de grado k" que se encuentra en # https://bit.ly/413l3oQ # 2ª definición de polinomioAdensa # ================================ def polinomioAdensa2(p: Polinomio[A]) -> list[A]: return dispersaAdensa(polinomioAdispersa(p)) # La función dispersaAdensa está definida en el ejercicio # "Transformaciones entre las representaciones dispersa y densa" que se # encuentra en https://bit.ly/3GTyIqe # La función polinomioAdispersa se encuentra en el ejercicio # "Transformaciones entre polinomios y listas dispersas" que se # encuentra en https://bit.ly/41GgQaB # Comprobación de equivalencia de polinomioAdensa # =============================================== # La propiedad es @given(p=polinomioAleatorio()) def test_polinomioAdensa(p: Polinomio[int]) -> None: assert polinomioAdensa(p) == polinomioAdensa2(p) # Propiedades de inversa # ====================== # La primera propiedad es @given(xs=densaAleatoria()) def test_polinomioAdensa_densaApolinomio(xs: list[int]) -> None: assert polinomioAdensa(densaApolinomio(xs)) == xs # La segunda propiedad es @given(p=polinomioAleatorio()) def test_densaApolinomio_polinomioAdensa(p: Polinomio[int]) -> None: assert densaApolinomio(polinomioAdensa(p)) == p # La comprobación es # > poetry run pytest -v Polinomios_Transformaciones_polinomios_densas.py # test_densaApolinomio PASSED # test_polinomioAdensa PASSED # test_polinomioAdensa_densaApolinomio PASSED # test_densaApolinomio_polinomioAdensa PASSED |