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.