1
Wielomian
y
1.1
P
ostac
p
otego
w
a
(naturalna)
wielomian
u
Wielomian
moze
b
yc
zapisan
y
w
bazie:
f1;
x;
x
2
;
:
:
:
;
x
n
g.
w
(x)
=
n
X
k =0
a
k
x
k
(1)
Algorytm:
s
=
a
0
;
xp
=
1;
f
or
i
=
1
to
n
beg
in
(2)
xp
=
xp
x;
s
=
s
+
a
i
xp
end
Liczba
dzialan
2n()
+
n(+).
1.2
Algorytm
Hornera
Ab
y
p
oliczyc
w
artosc
wielomian
u
mozna
zastoso
w
ac
szybszy
algorytm.
Korzystam
y
z
p
ostaci:
w
(x)
=
(:::(a
n
x
+
a
n
1
)x
+
:::
+
a
1
)x
+
a
0
(3)
Algorytm:
w
n
=
a
n
w
i
(x)
=
w
i+1
(x)x
+
a
i
dl
a
i
=
n
1;
n
2;
:
:
:
;
0
(4)
w
(x)
=
w
0
(x)
Liczba
dzialan
n()
+
n(+).
Twierdzenie:
Algorytm
Hornera
jest
jedyn
ym
algorytmem,
ktory
minimalizuje
liczb
e
do
da
w
an
i
mnozen
przy
obliczaniu
w
artosci
wielomian
u
danego
w
p
ostaci
p
otego
w
ej.
1.3
Dzielenie
wielomian
u
w
(x)
przez
(x
)
Algorytm
Hornera
moze
b
yc
wyk
orzystan
y
w
celu
p
o
dzielenia
wielomian
u
w
(x)
przez
(x
).
Jezeli:
n
X
k =0
a
k
x
k
=
(
n
1
X
k =0
b
k +1
x
k
)(x
)
+
b
0
;
(5)
gdzie
(
P
n
1
k =0
b
k +1
x
k
)
-
wynik
dzielenia,
b
0
-
reszta
z
dzielenia.
T
o:
a
n
=
b
n
a
k
=
b
k
b
k +1
dl
a
k
=
n
1;
n
2;
:
:
:
;
0
(6)
P
oro
wn
ujac
z
algorytmem
Hornera
(a
i
=
w
i
(x)
w
i+1
(x))
b
i
=
w
i
( ).
1
1.4
P
ostac
Newtona
wielomian
u
Wielomian
moze
b
yc
ro
wniez
zapisan
y
w
bazie:
f1;
x
x
0
;
(x
x
0
)(x
x
1
);
:
:
:
;
(x
x
0
)
(x
x
n
)g,
gdzie
x
0
;
x
1
;
:
:
:
;
x
n
sa
dan
ymi
liczbami.
w
(x)
=
b
0
+
n
X
i=1
b
i
(x
x
0
)
(x
x
i
)
(7)
Algorytm:
s
=
b
0
;
xp
=
1;
f
or
i
=
1
to
n
beg
in
(8)
xp
=
xp
(x
x
i
1
);
s
=
s
+
b
i
xp
end
Liczba
dzialan
2n()
+
2n(+).
1.5
Uogolnion
y
algorytm
Hornera
P
ono
wnie
mozna
zastoso
w
ac
szybsza
meto
de.
Korzystam
y
z
p
ostaci:
w
(x)
=
(:::(b
n
(x
x
n
1
)
+
b
n
1
)(x
x
n
2
)
+
:::
+
b
1
)(x
x
0
)
+
b
0
(9)
Algorytm:
w
n
=
b
n
w
i
(x)
=
w
i+1
(x
x
i
)x
+
b
i
dl
a
i
=
n
1;
n
2;
:
:
:
;
0
(10)
w
(x)
=
w
0
(x)
Liczba
dzialan
n()
+
2n(+).
1.6
Przejscie
o
d
p
ostaci
Newtona
do
p
ostaci
p
otego
w
ej
Zna
jac
wsp
olczynniki
wielomian
u
w
p
ostaci
Newtona
mozna
wyznaczyc
wsp
olczynniki
jego
p
ostaci
nat-
uralnej.
W
t
ym
celu
k
azdy
z
wielomiano
w
p
omo
cniczyc
h
zde nio
w
an
yc
h
wzorami
11
zapiszm
y
w
p
ostaci
naturalnej:
w
i
(x)
=
n
X
k =i
a
(i)
k
x
k
i
;
i
=
n;
n
1;
:
:
:
0
(11)
Ze
wzoru
11
otrzym
ujem
y
zaleznosci:
a
(n)
n
=
b
n
(12)
oraz
w
i
(x)
=
n
X
k =i+1
a
(i+1)
k
x
k
(i+1)
(x
x
i
)
+
b
i
=
n
X
k =i+1
a
(i+1)
k
x
k
i
n
X
k =i+1
a
(i+1)
k
x
k
(i+1)
x
i
+
b
i
=
a
(i+1)
n
x
n
i
+
n
1
X
k =i+1
(a
(i+1)
k
a
(i+1)
k +1
x
i
)x
k
i
+
(b
i
a
(i+1)
i+1
x
i
):
(13)
Stad
wsp
olczynniki
p
ostaci
p
otego
w
ej
k
olejn
yc
h
wielomiano
w
w
i
(i
=
n;
n
1;
:
:
:
;
0)
mozna
wyznaczyc
rekurencyjnie:
a
(i)
n
=
a
(i+1)
n
=
:
:
:
=
a
(n)
n
=
b
n
a
(i)
i
=
b
i
a
(i+1)
i+1
x
i
(14)
a
(i)
k
=
a
(i+1)
k
a
(i+1)
k +1
x
i
;
dl
a
k
=
i
+
1;
i
+
2;
:
:
:
;
n
1
2
P
amieta
jac,
ze
w
(x)
=
w
0
(x)
wiem
y
,
ze
szuk
ane
wsp
olczynniki
a
k
sa
ro
wne
a
(0)
k
(k
=
0;
1;
:
:
:
;
n).
Da
je
to
nastepujacy
algorytm
na
przejscie
o
d
p
ostaci
Newtona
do
p
ostaci
p
otego
w
ej:
a[n]
=
b[n];
f
or
i
=
n
1
dow
nto
0
do
beg
in
xi
=
x[i];
(15)
a[i]
=
b[i];
f
or
k
=
i
to
n
1
do
a[k
]
=
a[k
]
xi
a[k
+
1];
end
1.7
T
ablice
Deklaracja:
in
t
a[10];
de niuje
za
wsze
tablice
a[0..9].
Nie
istnieje
w
C
meto
da
zapisania
wprost
w
ektora
o
do
w
olnie
zaczyna-
jacym
sie
wsk
azniku
(np.
a[5..14]).
W
wielu
przypadk
ac
h
przyda
ja
sie
jednak
tablice
a[1..10].
Mozna
je
lat
w
o
zapisac
przy
p
omo
cy
wsk
aznik
o
w:
in
t
a[10],*ap;
ap=a-1;
Wsk
aznik
ap
wsk
azuje
na
p
ozycje
przed
a
dzieki
czem
u
st
w
orzylism
y
tablice
ap[1..10].
Mozna
nastepnie
wyk
on
yw
ac
na
niej
dzialania.
3