Strona główna » Algorytmy » Artykuły » Schemat Hornera
 

Schemat Hornera

Wstęp

Schemat Hornera to wygodny sposób na dzielenie wielomianu przez dwumian. Działanie to można zapisać przy pomocy układu równań, a sama implementacja algorytmu jest bardzo krótka.

Algorytm

Algorytm Hornera pozwala na szybkie obliczenie wielomianu w'(x) jeśli w(x)=w'(x)p(x), gdzie p(x) = (x - c). Na początek weźmy dowolny wielomian stopnia n-tego. Następnie przyrównajmy obydwie strony.

anxn + an - 1xn - 1 + .. + a1x + a0 = (x - c)(bn - 1xn - 1 + bn - 2xn - 2 + .. + b1x + b0) + R

Teraz należy wymnożyć prawą stronę równania. Wielomiany są takie same, gdy ich odpowiednie współczynniki mają tą samą wartość. Oznacza to, że po pomnożeniu należy sprawdzić co się znajduje obok xi.

anxn + an - 1xn - 1 + .. + a1x + a0 = bn - 1xn + (bn - 2 - c·bn - 1)xn - 1 + .. + (b0 - c·b1)x + R - c·b0

Porównując pary współczynników obu wielomianów oraz przekształcając równania tak, aby po jednej stronie samo bi otrzymujemy:

Oznacza to, że każdy następny wyraz jest zależny od wyniku poprzedniego wyrazu. Reguła jest zawsze taka sama: pobierz następny współczynnik wielomianu w(x) i dodaj iloczyn c i ostatni wyliczonego współczynnika bi.

Przykład

Dany jest wielomian w(x) = x4 - 2x3 - 2x2 + 5x + 1. Zadanie polega na podzieleniu go przez dwumian p(x) = (x - 2). Tu należy zwrócić uwagę, że c = 2. Wyliczanie kolejnych współczynników odbywa się wtedy następująco:

WyrazWzórObliczenia
b3a41
b2a3 + c·b3-2 + 2·1 = 0
b1a2 + c·b2-2 + 2·0 = -2
b0a1 + c·b15 + 2·(-2) = 1
Ra0 + c·b01 + 2·1 = 3

Z tego wynika, że w(x) = (x - 2)(x3 - 2x + 1) + 3

Zadanie

Napisz program, który wczyta od użytkownika współczynniki wielomianu w(x) oraz wartość c z dwumianu p(x) = x - c przez który ma zostać podzielony wielomian w(x). Zakładamy, że wielomian w(x) jest co najmniej stopnia n = 1. Wypisz na ekran wynik w postaci pokazane poniżej:

  1. (x - 2)(x^3 - 2x + 1) + 3

Założenia

Program będzie wykorzystywać funkcje napisane w bibliotece wielomiany.h, które zawiera podstawowe funkcje do wczytywania i wypisywania wielomianów.

Rozwiązanie

Funkcja dzielPrzezDwumian() przyjmuje dwa argumenty, którymi są: wielomian w - do podzielenia przez dwumian oraz c - wartość z dwumianu p(x) = x - c. W wyniku działania funkcji wielomian w zostaje zmodyfikowany, a funkcja zwraca resztę z dzielenia R.

  1. double dzielPrzezDwumian(wielomian* w, double c) {
  2.   int n = w->stopien;
  3.   double* a = new double[n];
  4.   if (n > 0) {
  5.     a[0] = zwrocWyrazStn(w, n);
  6.     for (int i = 1; i < n; i++)
  7.       a[i] = zwrocWyrazStn(w, n - i) + a[i - 1] * c;
  8.   }
  9.   double R = zwrocWyrazStn(w, 0) + a[n - 1] * c;
  10.   w->stopien = n - 1;
  11.   w->wspolczynniki = a;
  12.   return R;
  13. }

(2.) Pobierz stopień wielomianu i (3.) przygotuj tablicę pod nowe współczynniki. (3. - 7.) Oblicz w pętli kolejne współczynniki bi oraz (8.) resztę z dzielenia. Na koniec (9. - 10.) zaktualizuj wielomian i (11.) zwróć obliczoną reszte.

Testowanie funkcji

W celu przetestowania napisanej funkcji jak również spełnieniu wymagań zadania poniższy fragment kodu wczytuje potrzebne dane i wypisuje wynik:

  1. int main () {
  2.   cout << "Podaj stopien wielomianu i wspolczynniki\n";
  3.   wielomian* w = wczytajWieloman();
  4.   double c;
  5.   cout << "Podaj wartosc c we wzorze dwumianu p(x) = x - c\n c = ";
  6.   cin >> c;
  7.   double R = dzielPrzezDwumian(w, c);
  8.   double pdane[2] = { 1, -c };
  9.   wielomian* p = nowyWielomian(1, pdane);
  10.   cout << "w(x) = (";
  11.   wypiszWieloman(p);
  12.   cout << ")(";
  13.   wypiszWieloman(w);
  14.   cout << ") + " << R << endl;
  15.   system("pause");
  16.   return 0;
  17. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1