Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

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:

{tex}W(x) = 3x^3 + 3x^2 - 2x + 11{/tex}.

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

{tex}W(x) = 3\cdot x\cdot x\cdot x+3\cdot x \cdot x - 2 \cdot x + 11{/tex}

Schematem Hornera tych mnożeń należy wykonać tylko {tex}3{/tex}:

{tex}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 {/tex}.

a więc mamy:

{tex}(1)\ \ \ W(x) = x\cdot (x\cdot (3\cdot x+3)-2)+11 {/tex}

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

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

(suma ciągu arytmetycznego), natomiast dla omawianej metody zaledwie {tex}n{/tex} mnożeń.

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

{tex}3\cdot x+3{/tex}

Następnie przemnażamy przez wartość argumentu {tex}x{/tex}, potem odejmujemy {tex}2{/tex} i znów przemnażamy przez {tex}x{/tex}. 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 {tex}n{/tex} ma {tex}n+1{/tex} czynników.

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

Rozwiązanie rekurencyjne w C++:

/*******www.algorytm.edu.pl***************/
#include<iostream>
#include<cstdlib>
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;
  system("pause");
  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;
}