Dados $x$ e um vetor com $n + 1$ números $a_0, a_1, a_2, \ldots, a_n$, onde $n \geq 0,$ calcular: $$a_0 x^{(0)} + a_1 x^{(1)} + a_2 x^{(2)} + \ldots + a_n x^{(n)},$$ sendo $x^{(k)} = x(x-1)(x-2)\ldots(x-k+1)$ o polinômio fatorial de grau $k$. Considere que $x^{(0)} = 1$.

Procure utilizar o menor número possível de multiplicações e adições em seu algoritmo.

Solução:

Com recursão:

	\begin{algorithm}
	\begin{algorithmic}
	\FUNCTION{PoliFat}{$x, a$}
	\STATE $n \gets \textrm{size}(a) - 1$
	\IF{$n = 0$}
	\RETURN $a[0]$
	\ELSE
	\RETURN $a[0] + x$ * \textsc{PoliFat}$(x-1, a[1..n])$
	\ENDIF
	\ENDFUNCTION
	\end{algorithmic}
	\end{algorithm}
      

Com iteração:

	\begin{algorithm}
	\begin{algorithmic}
	\FUNCTION{PoliFat}{$x, a$}
	\STATE $n \gets \textrm{size}(a) - 1$
	\STATE $sum \gets a[n]$
	\FOR{$k \gets n-1$ \textbf{downto} 0} 
	\STATE $sum \gets sum * (x - k) + a[k]$
	\ENDFOR
	\RETURN $sum$
	\ENDFUNCTION
	\end{algorithmic}
	\end{algorithm}