TAD de los polinomios: Regla de Ruffini
Usando el tipo abstracto de los polinomios, definir las funciones
|
1 2 |
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int restoRuffini :: Int -> Polinomio Int -> Int |
tales que
cocienteRuffini r pes el cociente de dividir el polinomioppor el polinomiox-r. Por ejemplo:
|
1 2 3 4 5 6 7 8 9 |
λ> ejPol = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero))) λ> ejPol x^3 + 2*x^2 + -1*x + -2 λ> cocienteRuffini 2 ejPol x^2 + 4*x + 7 λ> cocienteRuffini (-2) ejPol x^2 + -1 λ> cocienteRuffini 3 ejPol x^2 + 5*x + 14 |
restoRuffini r pes el resto de dividir el polinomioppor el polinomiox-r. Por ejemplo,
|
1 2 3 4 5 6 |
λ> restoRuffini 2 ejPol 12 λ> restoRuffini (-2) ejPol 0 λ> restoRuffini 3 ejPol 40 |
Comprobar con QuickCheck que, dado un polinomio p y un número entero r, las funciones anteriores verifican la propiedad de la división euclídea.
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 |
import TAD.Polinomio (Polinomio, consPol, polCero) import Pol_Transformaciones_polinomios_densas (densaApolinomio, polinomioAdensa) import Pol_Division_de_Ruffini_con_representacion_densa (ruffiniDensa) import Pol_Producto_polinomios (multPol) import Pol_Suma_de_polinomios (sumaPol) import Pol_Crea_termino (creaTermino) import Test.QuickCheck -- 1ª definición de cocienteRuffini -- ================================ cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int cocienteRuffini r p = densaApolinomio (init (ruffiniDensa r (polinomioAdensa p))) -- 2ª definición de cocienteRuffini -- ================================ cocienteRuffini2 :: Int -> Polinomio Int -> Polinomio Int cocienteRuffini2 r = densaApolinomio . ruffiniDensa r . init . polinomioAdensa -- 1ª definición de restoRuffini -- ============================= restoRuffini :: Int -> Polinomio Int -> Int restoRuffini r p = last (ruffiniDensa r (polinomioAdensa p)) -- 2ª definición de restoRuffini -- ============================= restoRuffini2 :: Int -> Polinomio Int -> Int restoRuffini2 r = last . ruffiniDensa r . polinomioAdensa -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_diviEuclidea :: Int -> Polinomio Int -> Bool prop_diviEuclidea r p = p == sumaPol (multPol coci divi) rest where coci = cocienteRuffini r p divi = densaApolinomio [1,-r] rest = creaTermino 0 (restoRuffini r p) -- La comprobación es -- λ> quickCheck prop_diviEuclidea -- +++ 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 |
from hypothesis import given from hypothesis import strategies as st from src.Pol_Crea_termino import creaTermino from src.Pol_Division_de_Ruffini_con_representacion_densa import ruffiniDensa from src.Pol_Producto_polinomios import multPol from src.Pol_Suma_de_polinomios import sumaPol from src.Pol_Transformaciones_polinomios_densas import (densaApolinomio, polinomioAdensa) from src.TAD.Polinomio import (Polinomio, consPol, esPolCero, polCero, polinomioAleatorio) def cocienteRuffini(r: int, p: Polinomio[int]) -> Polinomio[int]: if esPolCero(p): return polCero() return densaApolinomio(ruffiniDensa(r, polinomioAdensa(p))[:-1]) def restoRuffini(r: int, p: Polinomio[int]) -> int: if esPolCero(p): return 0 return ruffiniDensa(r, polinomioAdensa(p))[-1] # Comprobación de la propiedad # ============================ # La propiedad es @given(r=st.integers(), p=polinomioAleatorio()) def test_diviEuclidea (r: int, p: Polinomio[int]) -> None: coci = cocienteRuffini(r, p) divi = densaApolinomio([1, -r]) rest = creaTermino(0, restoRuffini(r, p)) assert p == sumaPol(multPol(coci, divi), rest) # La comprobación es # src> poetry run pytest -q Pol_Regla_de_Ruffini.py # 1 passed in 0.32s |