Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Schemat Hornera


powrót

Schemat Hornera jest algorytmem służącym do bardzo szybkiego obliczania wartości wielomianu. Redukuje on ilość mnożeń do minimum. Przeanalizujmy następujący wielomian:

$$W(x) = 3x^3 + 3x^2 - 2x + 11$$.

Do wyznaczenia wartości wielomianu tradycyjnym sposobem należy wykonać 6 mnożeń:

$$W(x) = 3\cdot x\cdot x\cdot x+3\cdot x \cdot x - 2 \cdot x + 11$$

Schematem Hornera tych mnożeń należy wykonać tylko $$3$$:

$$W(x) = 3 \cdot x^3 + 3x^2 - 2x + 11 = x \cdot (3\cdot x^2 + 3x -2)+11 = x\cdot(x \cdot (3\cdot x+3)-2)+11 $$.

a więc mamy:

$$(1)\ \ \ W(x) = x\cdot (x\cdot (3\cdot x+3)-2)+11 $$

Dla wielomianu n-tego stopnia zwykle należy wykonać następującą ilość mnożeń (wliczając czynniki):

$$n+(n-1)+(n-2)+...+2+1 = \frac{n\cdot(n+1)}{2}$$

(suma ciągu arytmetycznego), natomiast dla omawianej metody zaledwie $$n$$ mnożeń.

Jak widać na przykładzie $$(1)$$ najpierw zaczniemy wykonywać działanie znajdujące się wewnątrz nawiasu:

$$3\cdot x+3$$

Następnie przemnażamy przez wartość argumentu $$x$$, potem odejmujemy $$2$$ i znów przemnażamy przez $$x$$. Czynności powtarzamy do momentu obliczenia wartości całego wielomianu.

Danymi wejściowymi będą współczynniki wielomianu oraz jego stopień. Następnie podamy argument, dla jakiego chcemy wyznaczyć wartość wielomianu. Zauważmy, że wielomian, którego stopień jest równy $$n$$ ma $$n+1$$ czynników.

Algorytm można testować na stronie z automatyczną sprawdzarką tutaj.

Rozwiązanie rekurencyjne w C++:

/*******www.algorytm.edu.pl***************/
#include<iostream>
using namespace std;

int horner(int wsp[],int st, int x)
{
	if(st==0)
		return wsp[0];
	
	return x*horner(wsp,st-1,x)+wsp[st];
}

int main()
{
	int *wspolczynniki;
	int stopien, argument;
	
	cout<<"Podaj stopień wielomianu: ";
	cin>>stopien;
	
	wspolczynniki = new int [stopien+1];
	
	//wczytanie współczynników
	for(int i=0;i<=stopien;i++)
	{
		cout<<"Podaj współczynnik stojący przy potędze "<<stopien-i<<": ";
		cin>>wspolczynniki[i];
	}
	
	cout<<"Podaj argument: ";
	cin>>argument;
	
	cout<<"W( "<<argument<<" ) = "<<horner(wspolczynniki,stopien,argument)<<endl;
	
	delete [] wspolczynniki;

	return 0;
}

Rozwiązanie iteracyjne:

int horner(int wsp[],int st, int x)
{
	int wynik = wsp[0];

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