La semana en Exercitium (13 de mayo de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de datos de los polinomios
- 1. Integral definida de un polinomio
- 2. Multiplicación de un polinomio por un número
- 3. División de polinomios
- 4. Divisibilidad de polinomios
- 5. Método de Horner del valor de un polinomio
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
|
1 |
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,
|
1 2 3 4 5 6 7 |
λ> 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.
|
1 2 3 4 5 6 7 |
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 |
|
1 2 3 4 5 6 7 8 |
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
|
1 |
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,
|
1 2 3 4 5 6 7 |
λ> 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.
|
1 2 3 4 5 6 7 8 9 10 11 |
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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
|
1 2 3 4 |
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 qes el cociente de la división depentreq. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> 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 qes el resto de la división depentreq. Por ejemplo,
|
1 2 |
λ> resto pol1 pol2 1.0*x + 4.0 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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
|
1 2 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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.
|
1 2 3 4 5 6 |
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) |
|
1 2 3 4 5 6 |
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
|
1 |
a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f |
se representa como
|
1 |
(((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f |
y se evalúa de dentro hacia afuera; es decir,
|
1 2 3 4 5 6 7 |
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
|
1 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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) |