Schemat Hornera

Schemat Hornera w informatyce szkolnej odnosi się do metody szybkiego obliczania wartości wielomianu. Na lekcjach matematyki, w szkole średniej, możemy wykorzystać schemat Hornera do rozkładu wielomianu na czynniki. My zajmiemy się tutaj tylko pierwszą kwestią.

Przykład

Obliczyć wartość wielomianu $f(x)=2x^3 + 6x^{2}-4x+1$, dla $x = 2$
Policzmy, ile działań należy wykonać obliczając $f(2)$
4 mnożenia dla potęg
3 mnożenia współczynników
3 dodawania
Łącznie – 10 operacji.
Zastosujmy teraz schemat Hornera – przekształcamy wielomian wyłączając wszędzie x przed nawias. $f(x)=2x^3 + 6x^{2}-4x+1 = x(2x^{2}+6x+4)+1=x(x(2x+6)-4)+1$
$f(2)=2\cdot(2\cdot(2\cdot2+6)-4)+1 = 2\cdot( 2\cdot10-4)+1 = 2\cdot16+1=33$
Liczba wykonanych operacji
3 mnożenia
3 dodawania
Łącznie – 6 operacji.
Zastosowanie schematu Hornera pozwoliło zmniejszyć dla n=3 liczbę operacji prawie o połowę. Wraz ze wzrostem n korzyść będzie coraz większa, gdyż pierwsza metoda ma złożoność kwadratową, druga zaś liniową. Narysuj oba wykresy i zobacz jak na wykresach zmienia się liczba operacji względem stopnia wielomianu n.
Schemat Hornera wykorzystujemy przy zamianie systemów liczbowych na system dziesiątkowy, bowiem obliczamy wtedy wartość wielomianu dla x = k, gdzie k jest podstawą systemu, który zamieniamy.

Pseudokod schematu Hornera

Oblicz wartość wielomianu stopnia n dla x=k.

Podaj stopień wielomianu n;
przypisz: w = 1;
Dla każdego i od n do 0  powtórz:
   podaj wspolczynnik a przy potędze i;
   przypisz: w = w * k + a;
wypisz: 'Wartosć wielomianu dla x = k wynosi:', w;
   

Ćwiczenie

Oblicz liczbę wszystkich operacji obliczania wartości wielomianu stopnia n metodą pierwszą (naiwną).

Wskazówka

Koszt mnożeń dla potęg wielomianu obliczyć ze wzoru na sumę ciągu arytmetycznego.

Zadanie

Napisz program w dowolnym języku, który zamienia liczbę daną w jednym systemie liczbowym na liczbę w drugim systemie.

Post Views: 28