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}