Considere o algoritmo:
Dados a0, a1, cdots an, x, Quantia =x cdot an; Para j=1: n-1
Quantia =x( Quantia +an-j) ;
Fim para
Quantia = Quantia +a0;
O que o algoritmo faz? Explique.

Passo 1

Beleza, o enunciado dá uma lista de coeficientes Quantia = x cdot an e um valor Quantia = xl(Quantia + a,n-jr) . O algoritmo faz assim:
  1. Inicializa Quantia = Quantia + a0
  2. Para p(x)=an x^n + an-1 x^n-1 + cdots + a1 x + a0 até , ele atualiza
  3. 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 Q0 = x,an como o valor de Quantia depois de Q1 = xl(Q0 + an-1r) = xl(xan + an-1r) = x^2an + xan-1 iterações do laço:
  • Antes de entrar no laço: Q2 = xl(Q1 + an-2r) = xl(x^2an + xan-1 + an-2r) = x^3an + x^2an-1 + x,an-2
  • Na primeira iteração ( Qn-1 = x^n an + x^n-1an-1 + cdots + x,a1 ): Quantia = Qn-1 + a0 = x^n an + x^n-1an-1 + cdots + x,a1 + a0 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
p(x)=an x^n + an-1 x^n-1 + cdots + a1 x + a0
avaliado em p(x) = l(cdotsl((an x + an-1)x + an-2r)x + cdots + a1r)x + a0, . 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
p(x)=an x^n + an-1 x^n-1 + cdots + a1 x + a0
no ponto , usando o método de Horner.

Exercícios relacionados