Neste exercício você criará uma implementação funcional de polinômios imutáveis
em Scala. Sua implementação consistirá da classe pfc.Pol e
do objeto acompanhante dessa classe. A seguinte sessão da shell de
Scala mostra o funcionamento e o uso da classe pfc.Pol:
scala> import pfc.Pol import pfc.Pol scala> Pol(3, 7) res0: pfc.Pol = 3x^7 scala> Pol(1, 4) - Pol(2, 2) + Pol(1, 0) res1: pfc.Pol = 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 (Double) quaisquer:
scala> Pol(0.5, 2) + Pol(-math.Pi, 1) - Pol(math.sqrt(2), 0) res2: pfc.Pol = 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 na ordem decrescente dos expoentes:
scala> Pol(1, 0) - Pol(2, 1) + Pol(3, 2) - Pol(4, 3) res3: pfc.Pol = -4x^3 + 3x^2 - 2x + 1 scala> Pol(3, 2) - Pol(4, 3) + Pol(1, 0) - Pol(2, 1) res4: pfc.Pol = -4x^3 + 3x^2 - 2x + 1 scala> res3 == res4 res5: Boolean = true
Polinômios podem ser armazenados em vals ou em vars:
scala> val p = Pol(1, 2) - Pol(2, 1) + Pol(1, 0) p: pfc.Pol = x^2 - 2x + 1 scala> var q = Pol(1, 1) - Pol(1) q: pfc.Pol = 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:
scala> p + q res6: pfc.Pol = x^2 - x scala> p - q res7: pfc.Pol = x^2 - 3x + 2 scala> q * q res8: pfc.Pol = x^2 - 2x + 1 scala> p / q res9: (pfc.Pol, pfc.Pol) = (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:
scala> res9._2 == Pol(0, 0) res10: Boolean = true
Note, também, que a comparação de polinômios funciona como deveria:
scala> p == q*q res11: Boolean = true scala> p != p + Pol(0) res12: Boolean = false scala> p == p + q res13: Boolean = false
Pode-se usar operadores "+" e "-" unários:
scala> +p res14: pfc.Pol = x^2 - 2x + 1 scala> -q res15: pfc.Pol = -x + 1 scala> q = -q q: pfc.Pol = -x + 1
A aritmética de polinômios inclui operações mistas, que têm como segundo operando um número real:
scala> p + 100 res16: pfc.Pol = x^2 - 2x + 101 scala> q - 41.7 res17: pfc.Pol = -x - 40.7 scala> p * 5.3 res18: pfc.Pol = 5.3x^2 - 10.6x + 5.3
Em particular, temos que
scala> Pol(7, 100) + Pol(42) == Pol(7, 100) + 42 res19: Boolean = 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:
scala> p / 2 res20: pfc.Pol = 0.5x^2 - x + 0.5
A aritmética mista (operações entre polinômios e números reais) funciona quando o primeiro operando for um polinômio. Se o primeiro operando for um número, a coisa não corre bem:
scala> 7 + p
<console>:8: error: overloaded method value + with alternatives:
(Double)Double <and>
(Float)Float <and>
(Long)Long <and>
(Int)Int <and>
(Char)Int <and>
(Short)Int <and>
(Byte)Int <and>
(java.lang.String)java.lang.String
cannot be applied to (pfc.Pol)
7 + p
^
O problema acima desaparece quando se importa o método que faz conversão
implícita de um Double em polinômio:
scala> import pfc.Pol.doubleToPol import pfc.Pol.doubleToPol scala> 7 + p res22: pfc.Pol = x^2 - 2x + 8 scala> 100 - p res23: pfc.Pol = -x^2 + 2x + 99 scala> 5 * p res24: pfc.Pol = 5x^2 - 10x + 5 scala> 10 / p res25: (pfc.Pol, pfc.Pol) = (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):
scala> p.degree res26: Int = 2 scala> p^2 res27: pfc.Pol = x^4 - 4x^3 + 6x^2 - 4x + 1 scala> p^3 res28: pfc.Pol = x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6x + 1 scala> (p^4) + (q^2) res29: pfc.Pol = x^8 - 8x^7 + 28x^6 - 56x^5 + 70x^4 - 56x^3 + 29x^2 - 10x + 2 scala> ((p^4) + (q^2)).degree res30: Int = 8
Obtém-se a derivada de um polinômio por meio do método deriv ou
do operador posfixo "!" (como não podemos usar p' para
a derivada de p, usamos p!):
scala> p.deriv res31: pfc.Pol = 2x - 2 scala> p! res32: pfc.Pol = 2x - 2 scala> (p^3)! res33: pfc.Pol = 6x^5 - 30x^4 + 60x^3 - 60x^2 + 30x - 6 scala> (p^3).deriv.deriv res34: pfc.Pol = 30x^4 - 120x^3 + 180x^2 - 120x + 30 scala> ((p^3)!)! res35: pfc.Pol = 30x^4 - 120x^3 + 180x^2 - 120x + 30
Para obter o valor de um polinômio para um certo x, basta aplicar
o polinômio ao número que ocupará o lugar do x:
scala> p res36: pfc.Pol = x^2 - 2x + 1 scala> p(5) res37: Double = 16.0 scala> (p^3)(4) res38: Double = 729.0 scala> Pol(1, 10)(2) res39: Double = 1024.0
Finalmente, é possível fazer composição de dois polinômios, isto é, aplicar o primeiro polinômio ao segundo:
scala> p(q) res40: pfc.Pol = x^2 scala> q(p) res41: pfc.Pol = -x^2 + 2x scala> p(Pol(1, 2)) res42: pfc.Pol = x^4 - 2x^2 + 1 scala> p(Pol(1, 4)) res43: pfc.Pol = x^8 - 2x^4 + 1 scala> p(p) res44: pfc.Pol = 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:
scala> (p(p))(p) res45: pfc.Pol = x^8 - 8x^7 + 24x^6 - 32x^5 + 14x^4 + 8x^3 - 8x^2 + 1 scala> (p(p))(5) res46: Double = 225.0 scala> p(p(p)) res47: pfc.Pol = x^8 - 8x^7 + 24x^6 - 32x^5 + 14x^4 + 8x^3 - 8x^2 + 1 scala> p(p(5)) res48: Double = 225.0 scala> p(p(p))(5) res49: Double = 50176.0
A classe pfc.Pol deve ser imutável e deve ter uma lista com
os termos não nulos do polinômio. Os termos devem aparecer nessa lista em
ordem decrescente dos expoentes. Nenhum termo nulo (isto é, nenhum
termo com coef igual a zero) pode estar presente na lista de
termos de algum polinômio. Em particular, o polinômio nulo (que não possui
nenhum termo não nulo) deve ter uma lista de termos vazia.
Como base para sua implementação, use o seguinte esqueleto:
package pfc
private case class Term(coef: Double, exp: Int) {
require(coef != 0 && exp >= 0)
}
class Pol private (private val terms: List[Term]) {
// construtor auxiliar
// (n.b.: tanto o construtor primario como o auxiliar sao privados)
private def this(coef: Double, exp: Int)
// aritmetica de polinomios
def + (that: Pol): Pol
def - (that: Pol): Pol
def * (that: Pol): Pol
def / (that: Pol): Tuple2[Pol, Pol]
// operadores unarios
def unary_+ : Pol
def unary_- : Pol
// aritmetica mista (o operando 1 e' um polinomio, o operando 2 e' um numero)
def + (d: Double): Pol
def - (d: Double): Pol
def * (d: Double): Pol
def / (d: Double): Pol
// grau, potenciacao e derivacao
def degree: Int
def ^(n: Int): Pol
def deriv: Pol
def ! : Pol
// calcula o valor do polinomio alvo para um dado valor de x
def apply(x: Double): Double
// composicao do polinomio alvo com outro polinomio
def apply(that: Pol): Pol
// sobrescrita de metodos da classe Any
override def equals(other: Any): Boolean
override def hashCode: Int
override def toString
// metodo auxiliar que multiplica o polinomio alvo por um termo simples
private def * (term: Term): Pol
}
object Pol {
// conversao implicita de Double em Pol
implicit def doubleToPol(d: Double): Pol
// metodos de fabrica acessiveis para os clientes
def apply(coef: Double, exp: Int): Pol
def apply(coef: Double): Pol
// metodo de fabrica interno (serve apenas para evitar o uso de new)
private def apply(terms: List[Term]): Pol
// metodo auxiliar para as operacoes de adicao e subtracao de polinomios
private def add(terms1: List[Term], terms2: List[Term]): List[Term]
}
Os métodos auxiliares marcados com private são opcionais, porém
fortemente recomendados. A idéia é que o grosso das tarefas envolvidas na adição e na subtração de polinômios seja executado pelo método add do
objeto Pol. Esse método recebe duas listas de termos. Por hipótese,
os elementos dessas listas aparecem em ordem decrescente dos expoentes, e elas
não contêm nenhum termo nulo. O método add devolve uma nova lista
com os termos do polinômio que é a soma dos polinômios correspondentes às duas
listas recebidas. A nova lista deve satisfazer os mesmos requisitos que as já
existentes: seus termos devem estar em ordem decrescente dos expoentes, e ela
não deve conter nenhum termo nulo.
O método add deve rodar em tempo proporcional ao número de termos
nas duas listas de entrada. 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 lista resultante
nenhum termo nulo que porventura seja produzido como resultado da soma 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 da operação de produto de polinômios.
A grande maioria dos métodos deve ser muito curta! A maioria deve ter
apenas uma linha. Aproveite bem as oportunidades de uso dos métodos de ordem
superior da classe List, como map,
filter e foldLeft (este último está disponível também
como um operador, o operador "/:").
Na minha implementação, todos os métodos ficaram extremamente curtos, menos
dois: o método toString da classe Pol (este foi o
método que ficou mais longo) e o método add do objeto
Pol. Descontadas as linhas vazias e as de comentários, o número de
linhas de código da classe Pol e do seu objeto acompanhante ficou
abaixo de 140.
Questão 1: Pode fazer em grupo?
Resposta: Este trabalho deve ser feito em grupos de uma ou duas
pessoas.
Questão 2: Pode haver grupo com mais de duas pessoas?
Resposta: Não.
Questão 3: O que exatamente deve ser entregue?
Resposta: Veja abaixo o ítem "Entrega".
Este trabalho deve ser entregue até o dia 13/11, por meio do sistema Paca/Moodle.
Entregue um arquivo fonte em Scala. O nome do arquivo deve ser da forma
ep3-<nomes-dos-membros-do-grupo>.scala.
Por exemplo: ep3-joao-maria.scala. No nome do arquivo devem ser
omitidos os acentos dos nomes dos membros do grupo. Além disso, a separação
entre palavras não deve ser feita com espaços. Ou seja, o arquivo não deve se
chamar "ep3-joão-maria.scala" nem
"ep3 joao maria.scala".
Last modified: Thu Oct 27 12:13:14 BRST 2011