PUERTA | PUERTA-CS-2006 | Pregunta 1 – Part 2

Considere el polinomio p(x) = a0 + a1x + a2x ² + a3x ³ , donde ai ≠ 0 ∀i. El número mínimo de multiplicaciones necesarias para evaluar p en una entrada x es:
(A) 3
(B) 4
(C) 6
(D) 9

Respuesta: (A)
Explicación:
Antecedentes Explicación:
La regla de Horner para la división de polinomios es un algoritmo que se utiliza para simplificar el proceso de evaluar un polinomio f(x) en un cierto valor x = x0 dividiendo el polinomio en monomios (polinomios de primer grado). Cada monomio implica un máximo de un proceso de multiplicación y uno de suma. El resultado obtenido de un monomio se suma al resultado obtenido del siguiente monomio y así sucesivamente de forma acumulativa. Para explicar lo anterior, reescribamos el polinomio en su forma desarrollada;

f(x0) = a0 + a1x0+ a2x0^2+ … + anx0^n

Esto también se puede escribir como:

f(x0) = a0 + x0(a1+ x0(a2+ x0(a3+ … + (an-1 + anx0)….)

El algoritmo propuesto por esta regla se basa en evaluar los monomios formados arriba comenzando
desde el que está en el paréntesis más interno y avanzando para evaluar los monomios en el
paréntesis externo.

Solución:
usando la regla de Horner, podemos escribir el polinomio de la siguiente manera
a0 + (a1 + (a2 + a3x)x)x

En la forma anterior, necesitamos hacer solo 3 multiplicaciones

p = a3 X x    ------------ (1)

q = (a2 + p) X x  ---------(2)

r = (a1 + q) X x  ---------(3)

result = a0 + r 

Referencia:
https://www.geeksforgeeks.org/horners-method-polynomial-e
Evaluation/ Esta solución es aportada por Nitika Bansal.
Cuestionario de esta pregunta