Devagar se vai ao longe: polinómios

Nos testes recentes (teste 2) apareceram algumas questões relacionadas com polinómios. Uma delas pedia para calcular o valor do polinómio num ponto e, outra, para calcular a soma de dois polinómios.

Muitos alunos ficaram bloqueados com a questão de saber como é que se representava um polinómio. E acabaram por não responder à pergunta. O que a seguir se segue pretende mostrar como é possível responder parcialmente à questão mesmo sem saber como o polinómio seria representado.

Valor de um polinómio num ponto

Já conhecem, espero bem, a lenga lenga do costume: dado um problema, entendi o enunciado? consigo identificar os dados? consigo identificar o resultado? Creio que não terão problema em aceitar que da resposta a estas questões resulta um modelo de programa:

view sourceprint?

1.def valor_poli(polinomio,x):

2.    """Calcula o valor de um polinómio de grau n num ponto."""

3.    pass

4.    return valor

Agora é preciso pensar na solução. Para me facilitar a vida, vou supor um exemplo concreto:



Suponhamos ainda que quero saber o valor do polinómio no ponto x = 6. Então o que tenho que fazer é substituir na expressão do polinómio x por 6 e efectuar as contas:



Temos por isso que calcular uma soma de produtos. Por analogia, sabemos que a solução é simples, bastando usar o nosso velho conhecido padrão de ciclo-contador-acumulador. Quantas vezes vamos repetir o ciclo? Numa abordagem simplista, diremos tantas vezes quantas o grau do polinómio. Já agora: o grau de um polinómio é a maior potência de x cujo coeficiente é diferente de zero. No exemplo acima será por isso 2. Mas sem saber mais nada podemos imaginar a seguinte solução.

view sourceprint?

1.def valor_poli(polinomio,x):

2.    """Calcula o valor de um polinómio de grau n num ponto."""

3.    g = grau(polinomio)

4.    valor = 0 # <-- Acumulador

5.    for i in range(g + 1): # <-- i é o contador implícito

6.        parcela = coeficiente(polinomio, i) * (x ** i)

7.        valor = valor + parcela

8.    return valor

Se as funções grau e coeficiente fizerem o que o seu nome promete temos a questão resolvida. Quem fizesse até aqui já teria uma boa cotação na pergunta!

Mas agora precisamos falar na representação dos polinómios. Olhando para dois polinómios o mesmo grau, o que os distingue são os respectivos coeficientes. Por isso um polinómio pode ser representado apenas por estes. Mas como? Uma ideia simples é usar uma lista de tal modo que na posição i está o coeficiente de ordem i. Por exemplo, o caso anterior seria representado por:





E se alguns coeficientes forem zero como no caso de:



Usam-se zeros!










Baseados nesta representação vamos implementar o que nos falta.

view sourceprint?

1.def grau(polinomio):

2.    """Polinomio representado por uma lista de coeficientes, mesmo os negativos!."""

3.    return len(polinomio) - 1

4. 

5.def coeficiente(polinomio,k):

6.    """Polinomio representado por uma lista de coeficientes, mesmo os negativos!."""

7.    return polinomio[k]

Fácil, não acham?

Claro que seu tiver um polinómio na forma.



é um desperdício de espaço. Outra solução para a representação seria ter uma lista em que cada elemento é um par (expoente, coeficiente). O exemplo anterior daria:




E agora como calcular o grau, o coeficiente e o expoente? Mas para que queremos saber o grau? Afinal ele é dado no interior da nova representação, e só era preciso saber o seu valor para podermos determinar o número de vezes em que repetimos o ciclo. Mas agora esse número depende do comprimento da lista que representa o polinómio. Logo não precisamos dele:

view sourceprint?

1.def valor_poli_b(polinomio,x):

2.    """Calcula o valor de um polinómio de grau n num ponto."""

3.    valor = 0 # <-- Acumulador

4.    for i in range(len(polinomio)): # <-- i é o contador implícito

5.        parcela = coeficiente(polinomio, i) * (x ** expoente(polinomio,i))

6.        valor = valor + parcela

7.    return valor

Questão (quase) resolvida. Notar que agora precisamos, como já referimos de saber o expoente associado a cada coeficiente. Para terminar (ou talvez não...):

view sourceprint?

1.def coeficiente(polinomio,k):

2.    return polinomio[k][1]

3. 

4.def expoente(polinomio,k):

5.    return polinomio[k][0]

Olhando para o código acima até podemos ficar orgulhosos. Mas, a mudança de representação, deve levar-nos a pensar se não podemos simplificar as coisas. E se o fizermos, chegaremos com naturalidade a outra solução, baseada em percorrer a lista pelo conteúdo e não pelos índices.

view sourceprint?

1.def valor_poli_c(polinomio,x):

2.    """Calcula o valor de um polinómio de grau n num ponto."""

3.    valor = 0 # <-- Acumulador

4.    for par in polinomio: # <-- i é o contador implícito

5.        valor = valor + par[1] * (x ** par[0])

6.    return valor

Afinal a mudança de representação levou-nos a rever a nossa solução inicial.

Depois disto, achamos que podemos deixar a soma de dois polinómios como exercício para o leitor. Mas fica a moral desta história: programar (às vezes) tem muito de arte, e só treinando nos aperfeiçoamos.

Ah, já agora. Se quiserem mesmo saber como calcular o grau do polinómio para esta segunda representação, aqui fica. até porque pode ser preciso para outro tipo de problema...

view sourceprint?

1.def grau(polinomio):

2.    polinomio.sort()

3.    return polinomio[-1][0]