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:

def valor_poli(polinomio,x):
    """Calcula o valor de um polinómio de grau n num ponto."""
    pass
    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.

def valor_poli(polinomio,x):
    """Calcula o valor de um polinómio de grau n num ponto."""
    g = grau(polinomio)
    valor = 0 # <-- Acumulador
    for i in range(g + 1): # <-- i é o contador implícito
        parcela = coeficiente(polinomio, i) * (x ** i)
        valor = valor + parcela
    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.

def grau(polinomio):
    """Polinomio representado por uma lista de coeficientes, mesmo os negativos!."""
    return len(polinomio) - 1

def coeficiente(polinomio,k):
    """Polinomio representado por uma lista de coeficientes, mesmo os negativos!."""
    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:

def valor_poli_b(polinomio,x):
    """Calcula o valor de um polinómio de grau n num ponto."""
    valor = 0 # <-- Acumulador
    for i in range(len(polinomio)): # <-- i é o contador implícito
        parcela = coeficiente(polinomio, i) * (x ** expoente(polinomio,i))
        valor = valor + parcela
    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...):

def coeficiente(polinomio,k):
    return polinomio[k][1]

def expoente(polinomio,k):
    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.

def valor_poli_c(polinomio,x):
    """Calcula o valor de um polinómio de grau n num ponto."""
    valor = 0 # <-- Acumulador
    for par in polinomio: # <-- i é o contador implícito
        valor = valor + par[1] * (x ** par[0])
    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...

def grau(polinomio):
    polinomio.sort()
    return polinomio[-1][0]