91影视

A polynomial expression is the algebraic form of expression that has the degrees for the variables. The polynomial expression has the same variable with multiple degrees.

(a)

Consider the Horner鈥檚 ruleas follows,

z = a_n

for i = n - 1 down to 0 :

z = zx + a_i

Let the loop invariant be 2 , when looping to i, then

$z_i=a_i+a_{i+1}x+a_{i+2}{x}^2+a_n{x}^{n-1}$, Then on the twenty first loop,

$\begin{array}{rcl}{z}_{i-1}& =& z_{i}x+a_{i-1}\\ & =& a_{i-1}+a_{i+1-1}x+a_{i+2-1}{x}^2+...a_n{x}^{n-(i-1)}\\ & =& a_{i-1}+a_{i}x+a_{i+1}{x}^2+...a_n{x}^{n-(i-1)}\end{array}$

Therefore, it has been proved that the Horner鈥檚 rule compute the polynomials and store at z

(b)

Consider the Horner鈥檚 ruleas follows,

z = a_n

for i = n -1 down to 0 :

z = zx + a_i

One multiplication and one addition per loop is performed, in total n multiplications and n additions are performed in the given scheme.

No alternative method calculates polynomial better than the Horner鈥檚 rule.

Therefore, One multiplication and one addition per loop. The Horner鈥檚 rule is the optimal method to find the polynomial.