Schemat Hornera jest sposobem obliczania wartości wielomianu dla podanego argumentu. Dzięki tej metodzie ograniczamy liczbę mnożeń, którą musimy wykonać w celu rozwiązania problemu. W tym materiale zaimplementujemy w języku C++ dwie wersje algorytmu: iteracyjną oraz rekurencyjną.

Specyfikacja problemu:

Dane:

• wspolczynniki[] – tablica zawierająca liczby rzeczywiste (kolejne współczynniki wielomianu)

• stopienWielomianu – liczba naturalna

• x – liczba rzeczywista; argument, dla którego obliczana jest wartość wielomianu

Wynik:

• wynik – liczba rzeczywista

Przykładowe wyjście:

Wartość wielomianu dla argumentu x = 4

Schemat Hornera – wersja iteracyjna

Zapiszmy krok po kroku algorytm obliczający wartość wielomianu w wersji iteracyjnejiteracjaiteracyjnej.

Krok 1.

Zapiszmy nagłówek naszej funkcji.

Najpierw zapisujemy typ zwracanych wartości przez naszą funkcję. W tym przypadku może to być zarówno typ int, float, double, jak i void. W przypadku funkcji typu void musimy w ciele funkcji zawrzeć wypisywanie na ekran obliczonej wartości.

Następnie zapisujemy nazwę naszej funkcji horner, a potem w okrągłych nawiasach zapisujemy argumenty funkcji. Pierwszym z argumentów jest tablica wspolczynniki zawierająca, jak sama nazwa wskazuje, wszystkie współczynniki znajdujące się przy kolejnych potęgach naszego wielomianu. Kolejnym argumentem jest stopienWielomianu. Jest to zmienna, w której przechowywana jest największa potęga naszego wielomianu. Ostatnim argumentem jest zmienna x. Jest to argument, dla którego będziemy obliczać wartość wielomianu.

int hornerIteracyjnie(int wspolczynniki[],int stopienWielomianu, int x)

Krok 2.

Deklarujemy zmienną wynik. Może być ona zarówno typu int, double, jak i float.

int wynik;

Krok 3.

Kolejnym krokiem będzie przypisanie do zmiennej wynik wartości równej wyrazowi wolnemu w naszym wielomianie.

wynik = wspolczynniki[0];

Krok 4.

Następnie tworzymy pętlę wykonującą się od i = 1 do i = stopienWielomianu. Zaczynamy pętlę od wartości równej 1, ponieważ wartość współczynnika wyrazu wolnego została uwzględniona w obliczeniach poza pętlą. Pętla wykonuje się do wartości równej stopienWielomianu, ponieważ zaczynamy od stopnia równego 1 i wykonujemy pętlę do momentu, w którym obliczymy cały wielomian.

for(int i = 1; i <= stopienWielomianu; i++)

Krok 5.

W pętli do zmiennej wynik przypisujemy jej obecną wartość przemnożoną przez argument x, a do tego dodajemy zmienną zapisaną w tabeli wspolczynniki pod indeksem i.

wynik = wynik * x + wspolczynniki[i];

Krok 6.

Po wykonaniu pętli dla funkcji typu void wypisujemy wartość zmiennej wynik w odpowiednim komunikacie.

cout<<"Wartość wielomianu dla argumentu x = "<<wynik;

Dla funkcji typu całkowitego (int) zwracamy zmienną wynik

return wynik;

Cały algorytm, włącznie z krokiem 6. zapisanym dla funkcji typu całkowitego, prezentuje się następująco:

int hornerIteracyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{
    int wynik = wspolczynniki[0];

    for(int i = 1; i <= stopienWielomianu; i++) 
        wynik = wynik * x + wspolczynniki[i];
	
    return wynik;	
}

Sprawdźmy jego działanie dla przykładowych danych. Przetestujemy działanie programu dla następującego wielomianu:

$W\left(x\right) = x^2 + 3x - 6$

oraz $x = 2$.

#include<iostream>
using namespace std;

int hornerIteracyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{
    int wynik = wspolczynniki[0];

    for(int i = 1; i <= stopienWielomianu; i++) 
        wynik = wynik * x + wspolczynniki[i];
	
    return wynik;	
}

int main()
{
    int wspolczynniki[] = {1, 3, -6};
    int stopienWielomianu = 2;
    int x = 2;
    cout << hornerIteracyjnie(wspolczynniki, stopienWielomianu, x);
    
    return 0;
}

Program na wyjściu daje liczbę 4, co jest poprawnym wynikiem.

Schemat Hornera – wersja rekurencyjna

Zapiszmy, krok po kroku, algorytm schematu Hornera w wersji rekurencyjnejrekurencjarekurencyjnej.

Krok 1.

Zapiszmy nagłówek naszej funkcji:

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)

Składa się on z następujących elementów:

• typu zwracanych wartości przez funkcję – w tym przypadku może to być zarówno int, float, jak i double,

• nazwy funkcji hornerRekurencyjnie,

• argumentów funkcji zapisanych w okrągłych nawiasach.

Pierwszym z argumentów jest tablica wspolczynniki zawierająca wszystkie współczynniki znajdujące się przy kolejnych potęgach naszego wielomianu. Kolejnym argumentem jest stopienWielomianu. Jest to zmienna, w której przechowywana jest największa potęga naszego wielomianu. Ostatnim argumentem jest zmienna x. Jest to argument, dla którego będziemy obliczali wartość wielomianu.

Krok 2.

Kolejnym krokiem jest ustalenie warunku przerwania rekurencji. Tym warunkiem będzie to, czy zmienna stopienWielomianu jest równa 0.

if(stopienWielomianu == 0)

Krok 3.

Jeśli warunek zapisany w kroku 2 jest spełniony, zwracamy współczynnik z indeksem zero – jest to wyraz wolny naszego wielomianu.

return wspolczynniki[0];

Krok 4.

Jeśli nasz warunek nie jest spełniony, zwracamy argument, dla którego obliczamy wartość wielomianu pomnożoną przez wartość, jaką zwróci nam wywołana rekurencyjnie funkcja hornerRekurencyjnie() z argumentami wspolczynniki, stopienWielomianu - 1, x oraz dodanym współczynnikiem zapisanym pod indeksem stopienWielomianu.

return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu ‑ 1,x) + wspolczynniki[stopienWielomianu];

Algorytm obliczający wartość wielomianu zapisany w wersji rekurencyjnej zaimplementowany w języku C++ wygląda następująco:

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{

    if(stopienWielomianu == 0)
    	return wspolczynniki[0];
    else
        return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu];
}

Sprawdźmy jego działanie dla przykładowych danych. Przetestujemy działanie programu dla następującego wielomianu:

$W\left(x\right) = x^2 + 3x - 6$

oraz $x = 2$.

#include<iostream>
using namespace std;

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{

    if(stopienWielomianu == 0)
    	return wspolczynniki[0];
    else
        return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu];
}

int main()
{
    int wspolczynniki[] = {1, 3, -6};
    int stopienWielomianu = 2;
    int x = 2;
    cout << hornerRekurencyjnie(wspolczynniki, stopienWielomianu, x);
    
    return 0;
}

Program na wyjściu daje liczbę 4, co jest poprawnym wynikiem.

Słownik