19-mayo-2023 – Exercitium

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

PorJosé A. Alonso 19-mayo-202322-mayo-2023

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

    raicesRuffini :: Polinomio Int -> [Int]

1	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]

λ> 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

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

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

Día: 19-mayo-2023

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

Entradas recientes

Buscar

Correo electrónico