Considere o algoritmo:
Dados
, Quantia
; Para
Fim para
Quantia
Quantia
;
O que o algoritmo faz? Explique.
Dados
Quantia
O que o algoritmo faz? Explique.
Passo 1
Beleza, o enunciado dá uma lista de coeficientes
e um valor
. O algoritmo faz assim:
- Inicializa
- Para
até , ele atualiza - Lá no final faz
O conteúdo é “avaliação de polinômios” e a técnica usada é o método de Horner, que reescreve o polinômio para economizar multiplicações. Para entender a resolução, a gente precisa saber o que é um polinômio
e como dá pra reorganizar essa soma de um jeito mais eficiente.
Passo 2
Vamos ver o que acontece em cada iteração. Definindo
como o valor de Quantia depois de
iterações do laço:
- Antes de entrar no laço:
- Na primeira iteração (
): Já apareceu parte do polinômio: . - Na segunda iteração (
): Agora acumulamos . - Seguindo assim, depois de
iterações a gente chega em - Por fim o algoritmo faz
Passo 3
O que rolou aqui é exatamente o cálculo do polinômio
avaliado em
. O truque do método de Horner é reescrever o polinômio como
assim a gente faz só
multiplicações e
adições, em vez de calcular cada termo
separadamente.
Resposta
O algoritmo calcula o valor do polinômio
no ponto
, usando o método de Horner.