Opis problemu

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. Sprawdźmy, ile operacji mnożenia musielibyśmy wykonać dla przedstawionego wielomianu:

Na początek rozwiążmy ten problem metodą tradycyjną:

Obliczając wartość wielomianu, musieliśmy wykonać sześć mnożeń. W celu zastosowania schematu Hornera, wyłączymy przed nawias $x$ w następujący sposób:

Następnie ponownie wyłączamy $x$ przed nawias. Będziemy powtarzać tę operację do momentu, gdy nasz wielomian będzie wyglądał tak:

Teraz musimy wykonać tylko trzy mnożenia, zatem znacząco zredukowaliśmy liczbę tych operacji.

Oto dwie metody implementacji algorytmu schematu Hornera – iteracyjną oraz rekurencyjną – które są zgodne z następującą specyfikacją:

Specyfikacja:

Dane:

• x – liczba rzeczywista, wartość argumentu

• stopien – liczba całkowita $>=0$, stopień wielomianu

• wsp[ ] – stopień $+1$–elementowa tablica liczb rzeczywistych, współczynniki wielomianu

Wynik:

• wynik – liczba rzeczywista, wartość wielomianu dla argumentu x

Implementacja algorytmu iteracyjnego

Na podstawie analizy przeprowadzonej na początku tego e‑materiału możemy zdefiniować następujący wzór iteracyjny algorytmu:

Rozpoczniemy od zaimplementowania schematu Hornera w języku Java przy użyciu iteracjiiteracjaiteracji. W tym celu zadeklarujemy funkcję o nazwie horner, której przyjmowanymi parametrami wyjściowymi będą:

• wsp[] – tablica współczynników wielomianu rozpoczynająca się od stojącego przy najwyższej potędze x, a kończąca na wyrazie wolnym,

• stopien – stopień wielomianu, czyli jego najwyższy wykładnik x,

• x – argument, dla którego chcemy obliczyć wartość wielomianu.

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
    
    }
}

Następnie do zmiennej wynik zapisujemy wartość pierwszego współczynnika. W już rozwiązywanym przykładzie znajdowała się ona w wewnętrznym nawiasie. Dla wielomianu:

jest to po prostu:

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        int wynik = wsp[0];
    }
}

Teraz możemy stworzyć pętlę, która będzie mnożyła nasz wynik razy x i dodawała kolejny współczynnik, aż osiągnie wartość stopien. Zatem po pierwszej iteracji nasze działanie będzie wyglądało tak:

a po ostatniej iteracji tak:

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        int wynik = wsp[0];
       
        for(int i = 1; i <= stopien; i++) {
            wynik = x * wynik + wsp[i];
        }
    }
}

Na koniec zwracamy otrzymaną wartość wielomianu, zapisaną w zmiennej wynik:

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        int wynik = wsp[0];
       
        for(int i = 1; i <= stopien; i++) {
            wynik = x * wynik + wsp[i];
        }
        return wynik;
    }
}

Teraz w głównej części programu wystarczy wywołać naszą funkcję z odpowiednimi współczynnikami, stopniem i argumentem, dla którego chcemy obliczyć wartość wielomianu.

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        int wynik = wsp[0];
       
        for(int i = 1; i <= stopien; i++) {
            wynik = x * wynik + wsp[i];
        }
        return wynik;
    }
 
    public static void main(String[] args) {
 
        int wsp[] = {2, 3, -4, -8};
        int stopien = 3;
        int x = 2;
        System.out.println(horner(wsp, stopien, x));
       
    }
}

Implementacja algorytmu rekurencyjnego

Wiemy już, jak stosować rekurencjęrekurencjarekurencję w programach. Pamiętajmy, że schemat Hornera również możemy zaimplementować tę techniką programowania. Wzór rekurencyjny algorytmu jest następujący:

Rozpoczynamy nasz program podobnie jak w sposobie iteracyjnym. Funkcja będzie miała nazwę horner, a przyjmowanymi parametrami wyjściowymi będą: tablica współczynników, stopień wielomianu oraz argument, dla którego chcemy obliczyć wartość wielomianu.

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {

    }
}

W następnym kroku będziemy wykorzystywać rekurencję. Zgodnie ze schematem Hornera będziemy mnożyć nasz argument przez wartość otrzymaną z rekurencyjnego wywołania funkcji dla stopnia mniejszego o $1$, a następnie dodawać do tego ostatni wyraz wolny. Np. w przypadku wywołania pierwszej funkcji horner dla wielomianu:

zostanie zwrócona następująca wartość:

R181iqxclboTR

x razy (2x kwadrat + 3x minus 4) minus 8.
Równanie w nawiasie oznaczone jako: horner(wsp, stopień minus 1, x)

Funkcja horner będzie wywoływana rekurencyjnie aż do przypadku podstawowegoprzypadek podstawowyprzypadku podstawowego – sytuacji, w której stopień wielomianu będzie równy $0$. Zostanie wtedy zwrócony pierwszy element naszej tablicy, czyli współczynnik leżący przy najwyższej potędze zmiennej x.

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        if(stopien==0) {
            return wsp[0];
    	}
        return x * horner(wsp, stopien - 1, x) + wsp[stopien];
    }
}

Teraz w głównej funkcji programu wystarczy wywołać funkcję horner z odpowiednimi współczynnikami, stopniem i wybranym argumentem dla danego wielomianu. Obliczmy wartość tego samego wielomianu i argumentu, co w przypadku iteracyjnym.

public class Horner {
   
    static int horner(int wsp[], int stopien, int x) {
        if(stopien==0) {
            return wsp[0];
    	}
        return x * horner(wsp, stopien - 1, x) + wsp[stopien];
    }
 
    public static void main(String[] args) {
 
        int wsp[] = {2, 3, -4, -8};
        int stopien = 3;
        int x = 2;
        System.out.println(horner(wsp, stopien, x));
       
    }
}

Tak samo jak w implementacji metodą iteracyjną, teraz również dla argumentu $2$ otrzymaliśmy wartość wielomianu równą $12$.

Słownik