Menu Close

La semana en Exercitium (13 de mayo de 2023)

José A. Alonso

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

A continuación se muestran las soluciones.

1. Integral definida de un polinomio

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

   integralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t

tal que integralDef p a b es la integral definida del polinomio p entre a y b. Por ejemplo,

   λ> ejPol = consPol 7 2 (consPol 4 5 (consPol 2 5 polCero))
   λ> ejPol
   2*x^7 + 5*x^4 + 5*x^2
   λ> integralDef ejPol 0 1
   2.916666666666667
   λ> integralDef ejPol 0 1 :: Rational
   35 % 12

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_Valor_de_un_polinomio_en_un_punto (valor)
import Pol_Integral_de_un_polinomio (integral)
 
integralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t
integralDef p a b = valor q b - valor q a
  where q = integral p


Soluciones en Python

from src.Pol_Integral_de_un_polinomio import integral
from src.Pol_Valor_de_un_polinomio_en_un_punto import valor
from src.TAD.Polinomio import Polinomio, consPol, polCero
 
 
def integralDef(p: Polinomio[float], a: float, b: float) -> float:
    q = integral(p)
    return valor(q, b) - valor(q, a)

2. Multiplicación de un polinomio por un número

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

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

tal que multEscalar c p es el polinomio obtenido multiplicando el número c por el polinomio p. Por ejemplo,

   λ> ejPol = consPol 1 2 (consPol 0 3 polCero)
   λ> ejPol
   2*x + 3
   λ> multEscalar 4 ejPol
   8*x + 12
   λ> multEscalar (1 % 4) ejPol
   1 % 2*x + 3 % 4

Soluciones

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


Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,
                      coefLider, restoPol)
import Data.Ratio
 
multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a
multEscalar c p
  | esPolCero p = polCero
  | otherwise   = consPol n (c*b) (multEscalar c r)
  where n = grado p
        b = coefLider p
        r = restoPol p


Soluciones en Python

from typing import TypeVar
 
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,
                               polCero, restoPol)
 
A = TypeVar('A', int, float, complex)
 
def multEscalar(c: A, p: Polinomio[A]) -> Polinomio[A]:
    if esPolCero(p):
        return polCero()
    n = grado(p)
    b = coefLider(p)
    r = restoPol(p)
    return consPol(n, c * b, multEscalar(c, r))

3. División de polinomios

Usando el tipo abstracto de los polinomios, definir las funciones

   cociente :: (Fractional a, Eq a) =>
               Polinomio a -> Polinomio a -> Polinomio a
   resto    :: (Fractional a, Eq a) =>
               Polinomio a -> Polinomio a -> Polinomio a

tales que

  • cociente p q es el cociente de la división de p entre q. Por ejemplo,
     λ> pol1 = consPol 3 2 (consPol 2 9 (consPol 1 10 (consPol 0 4 polCero)))
     λ> pol1
     2*x^3 + 9*x^2 + 10*x + 4
     λ> pol2 = consPol 2 1 (consPol 1 3 polCero)
     λ> pol2
     x^2 + 3*x
     λ> cociente pol1 pol2
     2.0*x + 3.0
  • resto p q es el resto de la división de p entre q. Por ejemplo,
     λ> resto pol1 pol2
     1.0*x + 4.0

Soluciones

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


Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol, grado, coefLider)
import Pol_Crea_termino (creaTermino)
import Pol_Producto_polinomios (multPol, multPorTerm)
import Pol_Resta_de_polinomios (restaPol)
import Pol_Multiplicacion_de_un_polinomio_por_un_numero (multEscalar)
 
cociente :: (Fractional a, Eq a) =>
            Polinomio a -> Polinomio a -> Polinomio a
cociente p q
  | n2 == 0   = multEscalar (1/a2) p
  | n1 < n2   = polCero
  | otherwise = consPol n3 a3 (cociente p3 q)
  where n1 = grado p
        a1 = coefLider p
        n2 = grado q
        a2 = coefLider q
        n3 = n1-n2
        a3 = a1/a2
        p3 = restaPol p (multPorTerm (creaTermino n3 a3) q)
 
resto :: (Fractional a, Eq a) =>
         Polinomio a -> Polinomio a -> Polinomio a
resto p q = restaPol p (multPol (cociente p q) q)


Soluciones en Python

from src.Pol_Crea_termino import creaTermino
from src.Pol_Multiplicacion_de_un_polinomio_por_un_numero import multEscalar
from src.Pol_Producto_polinomios import multPol, multPorTerm
from src.Pol_Resta_de_polinomios import restaPol
from src.TAD.Polinomio import Polinomio, coefLider, consPol, grado, polCero
 
 
def cociente(p: Polinomio[float], q: Polinomio[float]) -> Polinomio[float]:
    n1 = grado(p)
    a1 = coefLider(p)
    n2 = grado(q)
    a2 = coefLider(q)
    n3 = n1 - n2
    a3 = a1 / a2
    p3 = restaPol(p, multPorTerm(creaTermino(n3, a3), q))
    if n2 == 0:
        return multEscalar(1 / a2, p)
    if n1 < n2:
        return polCero()
    return consPol(n3, a3, cociente(p3, q))
 
def resto(p: Polinomio[float], q: Polinomio[float]) -> Polinomio[float]:
    return restaPol(p, multPol(cociente(p, q), q))

4. Divisibilidad de polinomios

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

   divisiblePol :: (Fractional a, Eq a) =>
                   Polinomio a -> Polinomio a -> Bool

tal que divisiblePol p q se verifica si el polinomio p es divisible por el polinomio q. Por ejemplo,

   λ> pol1 = consPol 2 8 (consPol 1 14 (consPol 0 3 polCero))
   λ> pol1
   8*x^2 + 14*x + 3
   λ> pol2 = consPol 1 2 (consPol 0 3 polCero)
   λ> pol2
   2*x + 3
   λ> pol3 = consPol 2 6 (consPol 1 2 polCero)
   λ> pol3
   6*x^2 + 2*x
   λ> divisiblePol pol1 pol2
   True
   λ> divisiblePol pol1 pol3
   False

Soluciones

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


Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol, esPolCero)
import Pol_Division_de_polinomios (resto)
 
divisiblePol :: (Fractional a, Eq a) =>
                Polinomio a -> Polinomio a -> Bool
divisiblePol p q = esPolCero (resto p q)


Soluciones en Python

from src.Pol_Division_de_polinomios import resto
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero
 
 
def divisiblePol(p: Polinomio[float], q: Polinomio[float]) -> bool:
    return esPolCero(resto(p, q))

5. Método de Horner del valor de un polinomio

El método de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de

   a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f

se representa como

  (((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f

y se evalúa de dentro hacia afuera; es decir,

  v(0) = 0
  v(1) = v(0)*x+a = 0*x+a = a
  v(2) = v(1)*x+b = a*x+b
  v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c
  v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d
  v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e
  v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f

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

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

tal que horner p x es el valor del polinomio p al sustituir su variable por el número x. Por ejemplo,

   λ> pol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> pol1
   x^5 + 5*x^2 + 4*x
   λ> horner pol1 0
   0
   λ> horner pol1 1
   10
   λ> horner pol1 1.5
   24.84375
   λ> import Data.Ratio
   λ> horner pol1 (3%2)
   795 % 32

Soluciones

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


Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol)
import Pol_Transformaciones_polinomios_densas (polinomioAdensa)
 
-- 1ª solución
-- ===========
 
horner :: (Num a, Eq a) => Polinomio a -> a -> a
horner p x = hornerAux (polinomioAdensa p) 0
  where hornerAux [] v     = v
        hornerAux (a:as) v = hornerAux as (v*x+a)
 
-- El cálculo de (horner pol1 2) es el siguiente
--    horner pol1 2
--    = hornerAux [1,0,0,5,4,0] 0
--    = hornerAux   [0,0,5,4,0] ( 0*2+1) = hornerAux   [0,0,5,4,0] 1
--    = hornerAux     [0,5,4,0] ( 1*2+0) = hornerAux     [0,5,4,0] 2
--    = hornerAux       [5,4,0] ( 2*2+0) = hornerAux       [5,4,0] 4
--    = hornerAux         [4,0] ( 4*2+5) = hornerAux         [4,0] 13
--    = hornerAux           [0] (13*2+4) = hornerAux           [0] 30
--    = hornerAux            [] (30*2+0) = hornerAux            [] 60
 
-- 2ª solución
-- ===========
 
horner2 :: (Num a, Eq a) => Polinomio a -> a -> a
horner2 p x = foldl (\a b -> a*x + b) 0 (polinomioAdensa p)


Soluciones en Python

from functools import reduce
 
from src.Pol_Transformaciones_polinomios_densas import polinomioAdensa
from src.TAD.Polinomio import Polinomio, consPol, polCero
 
# 1ª solución
# ===========
 
def horner(p: Polinomio[float], x: float) -> float:
    def hornerAux(ys: list[float], v: float) -> float:
        if not ys:
            return v
        return hornerAux(ys[1:], v * x + ys[0])
 
    return hornerAux(polinomioAdensa(p), 0)
 
# El cálculo de horner(pol1, 2) es el siguiente
#    horner pol1 2
#    = hornerAux [1,0,0,5,4,0] 0
#    = hornerAux   [0,0,5,4,0] ( 0*2+1) = hornerAux   [0,0,5,4,0] 1
#    = hornerAux     [0,5,4,0] ( 1*2+0) = hornerAux     [0,5,4,0] 2
#    = hornerAux       [5,4,0] ( 2*2+0) = hornerAux       [5,4,0] 4
#    = hornerAux         [4,0] ( 4*2+5) = hornerAux         [4,0] 13
#    = hornerAux           [0] (13*2+4) = hornerAux           [0] 30
#    = hornerAux            [] (30*2+0) = hornerAux            [] 60
 
# 2ª solución
# ===========
 
def horner2(p: Polinomio[float], x: float) -> float:
    return reduce(lambda a, b: a * x + b, polinomioAdensa(p) , 0.0)
Posted in PFH