Menu Close

TAD de los polinomios: Raíces enteras de un polinomio

José A. Alonso, ,

Usando el tipo abstracto de los polinomios, definir la función

    raicesRuffini :: Polinomio Int -> [Int]

tal que raicesRuffini p es la lista de las raices enteras de p, calculadas usando el regla de Ruffini. Por ejemplo,

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Pol_Raices_enteras_de_un_polinomio where
 
import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Test.Hspec (Spec, hspec, it, shouldBe)
 
raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p
  | esPolCero p = []
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where aux [] = []
        aux (r:rs)
          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)
          | otherwise         = aux rs
 
-- (divisores n) es la lista de todos los divisores enteros de n. Por
-- ejemplo,
--    divisores 4     ==  [1,-1,2,-2,4,-4]
--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]
divisores :: Int -> [Int]
divisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]
 
-- Verificación
-- ============
 
verifica :: IO ()
verifica = hspec spec
 
spec :: Spec
spec = do
  it "e1" $
    raicesRuffini ejPol1 `shouldBe` []
  it "e2" $
    raicesRuffini ejPol2 `shouldBe` [0,-1]
  it "e3" $
    raicesRuffini ejPol3 `shouldBe` [0]
  it "e4" $
    raicesRuffini ejPol4 `shouldBe` [1,-1,-2]
  where
    ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0013 seconds
--    4 examples, 0 failures


Soluciones en Python

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero
 
 
# (divisores n) es la lista de todos los divisores enteros de n. Por
# ejemplo,
#    divisores(4)  == [1, 2, 4, -1, -2, -4]
#    divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]
def divisores(n: int) -> list[int]:
    xs = [x for x in range(1, abs(n)+1) if n % x == 0]
    return xs + [-x for x in xs]
 
def raicesRuffini(p: Polinomio[int]) -> list[int]:
    if esPolCero(p):
        return []
    def aux(rs: list[int]) -> list[int]:
        if not rs:
            return []
        x, *xs = rs
        if esRaizRuffini(x, p):
            return [x] + raicesRuffini(cocienteRuffini(x, p))
        return aux(xs)
 
    return aux([0] + divisores(terminoIndep(p)))
 
# Verificación
# ============
 
def test_raicesRuffini() -> None:
    ejPol1 = consPol(4, 3, consPol(2, -5, consPol(0, 3, polCero())))
    assert raicesRuffini(ejPol1) == []
    ejPol2 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert raicesRuffini(ejPol2) == [0, -1]
    ejPol3 = consPol(4, 6, consPol(1, 2, polCero()))
    assert raicesRuffini(ejPol3) == [0]
    ejPol4 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert raicesRuffini(ejPol4) == [1, -1, -2]
    print("Verificado")
 
# La verificación es
#    >>> test_raicesRuffini()
#    Verificado
Leer más →

TAD de los polinomios: Reconocimiento de raíces por la regla de Ruffini

José A. Alonso, ,

Usando el tipo abstracto de los polinomios, definir la función

   esRaizRuffini :: Int -> Polinomio Int -> Bool

tal que esRaizRuffini r p se verifica si r es una raiz de p, usando para ello el regla de Ruffini. Por ejemplo,

   λ> ejPol = consPol 4 6 (consPol 1 2 polCero)
   λ> ejPol
   6*x^4 + 2*x
   λ> esRaizRuffini 0 ejPol
   True
   λ> esRaizRuffini 1 ejPol
   False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini where
 
import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Regla_de_Ruffini (restoRuffini)
 
esRaizRuffini :: Int -> Polinomio Int -> Bool
esRaizRuffini r p = restoRuffini r p == 0


Soluciones en Python

from src.Pol_Regla_de_Ruffini import restoRuffini
from src.TAD.Polinomio import Polinomio, consPol, polCero
 
 
def esRaizRuffini(r: int, p: Polinomio[int]) -> bool:
    return restoRuffini(r, p) == 0
Leer más →

TAD de los polinomios: Regla de Ruffini

José A. Alonso, ,

Usando el tipo abstracto de los polinomios, definir las funciones

   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
   restoRuffini    :: Int -> Polinomio Int -> Int

tales que

  • cocienteRuffini r p es el cociente de dividir el polinomio p por el polinomio x-r. Por ejemplo:
     λ> 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 p es el resto de dividir el polinomio p por el polinomio x-r. Por ejemplo,
     λ> 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.


Soluciones en Haskell

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.


Soluciones en Python

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
Leer más →

TAD de los polinomios: Regla de Ruffini con representación densa

José A. Alonso, ,

Usando el tipo abstracto de los polinomios definir la función

   ruffiniDensa :: Int -> [Int] -> [Int]

tal que ruffiniDensa r cs es la lista de los coeficientes del cociente junto con el rsto que resulta de aplicar la regla de Ruffini para dividir el polinomio cuya representación densa es cs entre x-r. Por ejemplo,

   ruffiniDensa 2 [1,2,-1,-2] == [1,4,7,12]
   ruffiniDensa 1 [1,2,-1,-2] == [1,3,2,0]

ya que

     | 1  2  -1  -2           | 1  2  -1  -2
   2 |    2   8  14         1 |    1   3   2
   --+--------------        --+-------------
     | 1  4   7  12           | 1  3   2   0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
ruffiniDensa :: Int -> [Int] -> [Int]
ruffiniDensa _ [] = []
ruffiniDensa r p@(c:cs) =
  c : [x+r*y | (x,y) <- zip cs (ruffiniDensa r p)]
 
-- 2ª solución
-- ===========
 
ruffiniDensa2 :: Int -> [Int] -> [Int]
ruffiniDensa2 r =
  scanl1 (\s x -> s * r + x)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_ruffiniDensa :: Int -> [Int] -> Bool
prop_ruffiniDensa r cs =
  ruffiniDensa r cs == ruffiniDensa2 r cs
 
-- La comprobación es
--    λ> quickCheck prop_ruffiniDensa
--    +++ OK, passed 100 tests.


Soluciones en Python

def ruffiniDensa(r: int, p: list[int]) -> list[int]:
    if not p:
        return []
    res = [p[0]]
    for x in p[1:]:
        res.append(x + r * res[-1])
    return res
Leer más →

TAD de los polinomios: Término independiente de un polinomio

José A. Alonso, ,

Usando el tipo abstracto de datos de los polinomios definir la función

   terminoIndep :: (Num a, Eq a) => Polinomio  a -> a

tal que terminoIndep p es el término independiente del polinomio p. Por ejemplo,

   λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))
   λ> ejPol1
   3*x^4 + 5*x^2 + 3
   λ> terminoIndep ejPol1
   3
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> terminoIndep ejPol2
   0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Polinomio (Polinomio, consPol, polCero)
import Pol_Coeficiente (coeficiente)
 
terminoIndep :: (Num a, Eq a) => Polinomio  a -> a
terminoIndep = coeficiente 0


Soluciones en Python

from typing import TypeVar
 
from src.Pol_Coeficiente import coeficiente
from src.TAD.Polinomio import Polinomio, consPol, polCero
 
A = TypeVar('A', int, float, complex)
 
def terminoIndep(p: Polinomio[A]) -> A:
    return coeficiente(0, p)
Leer más →