Ir al contenido principal

TAD de los polinomios - Factorización de un polinomio

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

   factorizacion :: Polinomio Int -> [Polinomio Int]

tal que factorizacion p es la lista de la descomposición del polinomio p en factores obtenida mediante el regla de Ruffini. Por ejemplo,

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

Soluciones

Se usarán las siguientes funciones

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

Soluciones en Haskell

module Pol_Factorizacion_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Raices_enteras_de_un_polinomio (divisores)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Pol_Transformaciones_polinomios_densas (densaApolinomio)
import Test.Hspec (Spec, hspec, it, shouldBe)

factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p
  | esPolCero p = [p]
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where
    aux [] = [p]
    aux (r:rs)
        | esRaizRuffini r p =
            densaApolinomio [1,-r] : factorizacion (cocienteRuffini r p)
        | otherwise = aux rs

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    map show (factorizacion ejPol1)
      `shouldBe` ["1*x","1*x + 1","x^3 + -1*x^2 + 1*x + 4"]
  it "e2" $
    map show (factorizacion ejPol2)
      `shouldBe` ["1*x + -1","1*x + 1","1*x + 2","1"]
  where
    ejPol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol2 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0015 seconds
--    2 examples, 0 failures

Soluciones en Python

from src.Pol_Raices_enteras_de_un_polinomio import divisores
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.Pol_Transformaciones_polinomios_densas import densaApolinomio
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero


def factorizacion(p: Polinomio[int]) -> list[Polinomio[int]]:
    def aux(xs: list[int]) -> list[Polinomio[int]]:
        if not xs:
            return [p]
        r, *rs = xs
        if esRaizRuffini(r, p):
            return [densaApolinomio([1, -r])] + factorizacion(cocienteRuffini(r, p))
        return aux(rs)

    if esPolCero(p):
        return [p]
    return aux([0] + divisores(terminoIndep(p)))

# Verificación
# ============

def test_factorizacion() -> None:
    ejPol1 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert list(map(str, factorizacion(ejPol1))) \
        == ["1*x", "1*x + 1", "x^3 + -1*x^2 + 1*x + 4"]
    ejPol2 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert list(map(str, factorizacion(ejPol2))) \
        == ["1*x + -1", "1*x + 1", "1*x + 2", "1"]
    print("Verificado")

# La verificación es
#    >>> test_factorizacion()
#    Verificado