12. Hornerova sema
Imamo neki polinom
P(x) = a[n]*x^n + a[n-1]*x^(n-1) + a[n-2] *x^(n-2) + … + a[1]*x + a[0]
P(x) = 3*x^4 + 5*x^3 + 7*x^2 – 4*x + 1
tj. koeficijenti su
3, 5, 7, -4, 1
4 do it 3 do it 2 do it 1 do it 0 do it
Izracuajmo P(4)
k P
0
4 0*x+a[k] = 0 * 4 + 3 = 3
3 3*x+a[k] = 3 * 4 + 5 = 17
2 17*x +a[k] = 17 * 4 + 7 = 7
1 75*x + a[k] = 75 * 4 -4 = 300 -4 = 296
0 296 * x + a[k] = 296 * 4 + 1 = 1185
———————————————–
double Horner(int n, double a[], double x) {
int k;
double p;
p = 0;
for (k = n; k >= 0; k++)
p = p * x + a[k];
return p;
}
————————————————
Slozenost Teta(n)
NTP 