La semana en Exercitium (20 de mayo de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sibre el tipo abstracto de datos de los polinomios

1. Término independiente de un polinomio
2. Regla de Ruffini con representación densa
3. Regla de Ruffini
4. Reconocimiento de raíces por la regla de Ruffini
5. Raíces enteras de un polinomio

A continuación se muestran las soluciones.

1. Término independiente de un polinomio

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

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

1	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

λ> ejPol1 = consPol 4 3 (consPol 2 5 (consPol 0 3 polCero))

λ> ejPol1

3*x^4 + 5*x^2 + 3

λ> terminoIndep ejPol1

λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

λ> ejPol2

x^5 + 5*x^2 + 4*x

λ> terminoIndep ejPol2

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

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)

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)

2. Regla de Ruffini con representación densa

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

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

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

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

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

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

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

3. Regla de Ruffini

Usando el tipo abstracto de los polinomios, definir las funciones

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

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

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

λ> restoRuffini 2 ejPol

λ> restoRuffini (-2) ejPol

λ> restoRuffini 3 ejPol

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.

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

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

4. Reconocimiento de raíces por la regla de Ruffini

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

   esRaizRuffini :: Int -> Polinomio Int -> Bool

1	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

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

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

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

5. Raíces enteras de un polinomio

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

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)

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]

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)

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]

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

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

1. Término independiente de un polinomio

2. Regla de Ruffini con representación densa

3. Regla de Ruffini

4. Reconocimiento de raíces por la regla de Ruffini

5. Raíces enteras de un polinomio

Se puede imprimir o compartir con