Este exercício-programa tem duas partes.
A seguinte sessão interativa com o interpretador Python mostra o
funcionamento e o uso do módulo polynomials que você criará:
$ python3 Python 3.3.1 (default, Apr 17 2013, 22:30:32) [GCC 4.7.3] on linux Type "help", "copyright", "credits" or "license" for more information. >>> >>> from polynomials import pol >>> pol(3, 7) 3x^7 >>> pol(1, 4) - pol(2, 2) + pol(1, 0) x^4 - 2x^2 + 1
Os expoentes de um polinômio têm de ser inteiros não negativos, mas os coeficientes do polinômio podem ser números reais (floats ou ints) quaisquer:
>>> import math >>> pol(0.5, 2) + pol(-math.pi, 1) - pol(math.sqrt(2), 0) 0.5x^2 - 3.141592653589793x - 1.4142135623730951
Quando se especifica um polinômio, a ordem dos termos
pol(coef, exp) é irrelevante, pois os termos são mantidos
sempre em ordem decrescente dos expoentes:
>>> pol(1, 0) - pol(2, 1) + pol(3, 2) - pol(4, 3) -4x^3 + 3x^2 - 2x + 1 >>> pol(3, 2) - pol(4, 3) + pol(1, 0) - pol(2, 1) -4x^3 + 3x^2 - 2x + 1 >>> pol(1, 0) - pol(2, 1) + pol(3, 2) - pol(4, 3) == pol(3, 2) - pol(4, 3) + pol(1, 0) - pol(2, 1) True
Polinômios podem ser armazenados em variáveis:
>>> p = pol(1, 2) - pol(2, 1) + pol(1, 0) >>> p x^2 - 2x + 1 >>> q = pol(1, 1) - pol(1) >>> q x - 1
Note, no segundo exemplo acima, que pol(coef) é o mesmo que
pol(coef, 0).
A aritmética de polinômios funciona como era de se esperar:
>>> p + q x^2 - x >>> p - q x^2 - 3x + 2 >>> q * q x^2 - 2x + 1 >>> p / q (x - 1, 0)
Note que o resultado de uma divisão de polinômios é um par de polinômios: o primeiro polinômio do par é o quociente e o segundo é o resto. No caso da divisão
acima, o quociente é x - 1 e o resto é o polinômio nulo:
>>> quoc, resto = p / q >>> quoc x - 1 >>> resto 0 >>> resto == pol(0, 0) True
É claro que não se pode efetuar uma divisão pelo polinômio nulo:
>>> p / pol(0)
Traceback (most recent call last):
...
ZeroDivisionError: divisor cannot be zero
Note, também, que a comparação de polinômios funciona como deveria:
>>> p == q*q True >>> p != p + pol(0) False >>> p == p + q False
Pode-se usar operadores "+" e "-" unários:
>>> +p x^2 - 2x + 1 >>> -q -x + 1 >>> q = -q >>> q -x + 1
A aritmética de polinômios inclui operações mistas, que têm como segundo
operando um número real (float ou int):
>>> p + 100 x^2 - 2x + 101 >>> q - 41.7 -x - 40.7 >>> p * 5.3 5.3x^2 - 10.6x + 5.3
Em particular, temos que
>>> pol(7, 100) + pol(42) == pol(7, 100) + 42 True
O resultado da divisão de polinômios é um par de polinômios, mas o da divisão de um polinômio por um número real é um polinômio, pois no segundo caso o resto é sempre igual ao polinômio nulo:
>>> p / 2 0.5x^2 - x + 0.5 >>> p / pol(2) (0.5x^2 - x + 0.5, 0)
A aritmética mista (operações entre polinômios e números reais) também funciona quando o primeiro operando for um número:
>>> 7 + p x^2 - 2x + 8 >>> 100 - p -x^2 + 2x + 99 >>> 5 * p 5x^2 - 10x + 5 >>> 10 / p (0, 10)
Pode-se obter o grau de um polinômio e elevar um polinômio a uma potência especificada (a potência tem de ser um inteiro não negativo):
>>> p.degree() 2 >>> p**2 x^4 - 4x^3 + 6x^2 - 4x + 1 >>> p**3 x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6x + 1 >>> (p**4 + q**2).degree() 8
Quando aplicada a um polinômio, a função len() devolve o número de termos não nulos do polinômio:
>>> p x^2 - 2x + 1 >>> len(p) 3 >>> p**4 + q**2 x^8 - 8x^7 + 28x^6 - 56x^5 + 70x^4 - 56x^3 + 29x^2 - 10x + 2 >>> len(p**4 + q**2) 9
Obtém-se a derivada de um polinômio por meio do método deriv():
>>> p.deriv() 2x - 2 >>> (p**3).deriv() 6x^5 - 30x^4 + 60x^3 - 60x^2 + 30x - 6 >>> (p**3).deriv().deriv() 30x^4 - 120x^3 + 180x^2 - 120x + 30
Para obter o valor de um polinômio num certo x, basta aplicar
o polinômio ao número que ocupará o lugar do x:
>>> p x^2 - 2x + 1 >>> p(5) 16 >>> p(5.0) 16.0 >>> (p**3)(4) 729 >>> (p**3)(4.5) 1838.265625 >>> pol(1, 10)(2) # isto e' 2**10 1024
Finalmente, é possível fazer composição de dois polinômios, isto é, aplicar o primeiro polinômio ao segundo:
>>> p(q) x^2 >>> q(p) -x^2 + 2x >>> p(pol(1, 2)) x^4 - 2x^2 + 1 >>> p(pol(1, 4)) x^8 - 2x^4 + 1 >>> p(p) x^4 - 4x^3 + 4x^2
Como o resultado da composição de dois polinômios é um terceiro polinômio, esse resultado pode ser composto com outro polinômio ou aplicado a um número:
>>> (p(p))(p) x^8 - 8x^7 + 24x^6 - 32x^5 + 14x^4 + 8x^3 - 8x^2 + 1 >>> (p(p))(5) 225 >>> p(p(p)) x^8 - 8x^7 + 24x^6 - 32x^5 + 14x^4 + 8x^3 - 8x^2 + 1 >>> p(p(5)) 225 >>> p(p(p))(5) 50176
Polinômios são instâncias da classe Pol definida no módulo
polynomials:
>>> type(p) <class 'polynomials.Pol'> >>> type(pol(42, 25) + pol(1, 1000)) <class 'polynomials.Pol'> >>> type(p * q) <class 'polynomials.Pol'> >>> type((p+q)(p-q)) <class 'polynomials.Pol'>
Seu arquivo polynomials.py deve conter a definição da classe
Pol, cujas instâncias representam polinômios com coeficientes
reais, e a definição da função pol, que desempenha o papel de
"fábrica de monômios". Essa função recebe argumentos coef e
exp (o argumento exp é opcional e tem 0 como valor
default) e devolve uma instância da classe Pol que
corresponde ao monômio com coeficiente coef e expoente
exp.
Na medida do possível, os polinômios devem ser objetos imutáveis. Em outras
palavras, o estado interno de uma instância da classe Pol não
deve ser alterável por meio da interface "oficial" da classe Pol.
As operações aritméticas com polinômios produzem como resultado novos
polinômios, sem jamais modificar os polinômios usados como operandos.
O estado interno de um polinômio consiste dos termos do polinômio, dispostos
em ordem decrescente dos expoentes. Cada termo é uma tupla com dois
elementos: um par (coef, exp). Assim, o estado interno do
polinômio p(x)=-x5+2x3+5x2-7
poderia ser a seguinte lista de pares (coef, exp):
[(-1, 5), (2, 3), (5, 2), (-7, 0)]
Entretanto, como se deseja que polinômios sejam imutáveis, é mais adequado
que o estado de um polinômio seja uma tupla (imutável) em vez de ser
uma lista (mutável). Tomada essa decisão de projeto, o estado interno
do polinômio acima é a seguinte tupla de pares (coef, exp):
((-1, 5), (2, 3), (5, 2), (-7, 0))
Nenhum termo nulo (isto é, nenhum par com coef
igual a zero) pode estar presente na tupla de termos de algum polinômio.
Em particular, o polinômio nulo (que não possui
nenhum termo não nulo) deve ter uma tupla de termos vazia.
Como base para sua implementação você pode usar o seguinte esqueleto:
# funcao que cria um novo monomio
def pol(coef, exp = 0):
pass
class Pol:
# - Metodos/campos com nome da forma __algum_nome__ (com __ no inicio
# e no final) sao especiais. Cada um desses metodos tem um significado
# especifico para o interpretador Python.
#
# - Metodos/campos com nome da forma __algum_nome (com __ no inicio mas
# nao no final) sao "privados" e nao fazem parte da interface oferecida
# aos clientes da classe Pol.
#
# - Metodos/campos com nome da forma algum_nome (sem _ no inicio)
# sao "normais" e fazem parte da interface oferecida aos clientes da
# classe Pol.
# construtor:
def __init__(self, terms):
self.__terms = tuple(terms)
# metodo que implementa len():
def __len__(self):
return len(self.__terms)
# ----- aritmetica de polinomios -----------------------------------
# metodos que implementam as operacoes binarias +, -, * e / quando
# o primeiro operando for uma instancia de Pol:
def __add__(self, other):
pass
def __sub__(self, other):
pass
def __mul__(self, other):
pass
def __truediv__(self, other):
pass
# metodos que implementam as operacoes binarias +, -, * e / quando
# o primeiro operando nao for uma instancia de Pol mas o segundo for:
def __radd__(self, other):
pass
def __rsub__(self, other):
pass
def __rmul__(self, other):
pass
def __rtruediv__(self, other):
pass
# metodos que implementam os operadores unarios + e -:
def __neg__(self):
pass
def __pos__(self):
pass
# metodo que implementa `a exponenciacao do polinomio:
def __pow__(self, n):
pass
# ----- outras operacoes com polinomios ----------------------------
# metodos que implementam os operadores de comparacao == e !=:
def __eq__(self, other):
pass
def __ne__(self, other):
# metodo que devolve o grau do polinomio:
def degree(self):
pass
# metodo que devolve a derivada do polinomio:
def deriv(self):
pass
# aplicacao do polinomio a um numero ou a outro polinomio:
def __call__(self, x):
if isinstance(x, Pol):
pass # aplica o polinomio a outro (composicao de polinomios)
else:
pass # aplica o polinomio a um numero (a avaliacao do polinomio
# num valor de x deve ser feita usando a regra de Horner)
# conversao do polinomio em string:
def __repr__(self):
pass
def __str__(self):
pass
# ----- metodos auxiliares "privados" ------------------------------
# metodo com o codigo comum `as operacoes de adicao e subtracao
# (chamado por __add__, __sub__, __radd__ e __rsub__):
def __add_or_sub(self, other, sub):
pass
# metodo que multiplica o polinomio pelo termo (coef, exp) especificado:
def __mul_by_term(self, coef, exp):
pass
# metodo que implementa a multiplicacao de polinomios (chamado por
# __mul__ e __rmul__):
def __mul(self, other):
pass
# metodo auxiliar que implementa a divisao de polinomios (chamado por
# __truediv__ e __rtruediv__):
def __truediv(self, other):
pass
Os métodos auxiliares marcados com private são opcionais, porém
fortemente recomendados. A idéia é que tanto a adição como a subtração de polinômios sejam executado pelo método __add_or_sub. O terceiro argumento (sub) recebido por esse
método é um bool que indica se a operação é de adição (sub == False) ou subtração (sub == True). O polinômio devolvido
pelo método __add_or_sub deve conter uma tupla de termos que
satisfaz estes dois requisitos: (1) os elementos da tupla de termos
estão em ordem decrescente dos expoentes, e (2) a tupla de termos não
contêm nenhum termo nulo. Esses dois requisitos, que já eram satisfeitos
pelas pelas tuplas de termos dos polinômios usados como operandos
da adição ou da subtração, devem permanecem satisfeitos pela tupla de termos
do polinômio produzido como resultado da operação.
O método __add_or_sub deve rodar em tempo proporcional à quantidade total de termos nos polinômios somados ou subtraídos. Para tanto, ele
deve implementar um algoritmo semelhante ao conhecido algoritmo de
intercalação (merge) de duas listas ordenadas.
Além de fazer uma intercalação, ele também soma os
termos com o mesmo expoente, tomando o cuidado de não colocar na
sequência de termos resultante nenhum termo nulo que porventura seja produzido
como resultado da soma ou da subtração de dois termos com o mesmo expoente.
A classe Pol tem um método auxiliar que multiplica o polinômio
alvo por um termo. Embora muito simples, esse método simplifica bastante a
implementação das operações de mulltiplicação e de divisão de produto de polinômios.
Last modified: Mon Jun 24 11:52:43 BRT 2013