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.

a_nxⁿ + a_{n - 1}x^{n - 1} + .. + a₁x + a₀ = (x - c)(b_{n - 1}x^{n - 1} + b_{n - 2}x^{n - 2} + .. + b₁x + b₀) + 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 xⁱ.

a_nxⁿ + a_{n - 1}x^{n - 1} + .. + a₁x + a₀ = b_{n - 1}xⁿ + (b_{n - 2} - c·b_{n - 1})x^{n - 1} + .. + (b₀ - c·b₁)x + R - c·b₀

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

• bn - 1 = an
• bn - 2 = an - 1 + c·bn - 1
• ..
• b0 = a1 + c·b1
• R = a0 + c·b0

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 bⁱ.

Przykład

Dany jest wielomian w(x) = x⁴ - 2x³ - 2x² + 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:

Z tego wynika, że w(x) = (x - 2)(x³ - 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 b_i 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. }

• Kod źródłowy Implementacja
• Biblioteka wielomiany.h