lis 18 2015 18 listopada 2015 23 listopada 2016 przez Michał Franczak

Liczby Fibonacciego i schemat Hornera – realizacja iteracyjna

Napisano w ,
  1. Liczby Fibonacciego – ciąg liczb naturalnych określony  w sposób następujący:

Pierwszy wyraz jest równy 0, drugi jest równy 1, każdy następny jest sumą dwóch poprzednich.

 

https://upload.wikimedia.org/math/f/0/4/f045bf12be8d813b78d7d0c1c2d2bf55.png

Kolejne wyrazy tego ciągu nazywane są liczbami Fibonacciego. Kwestia zaliczania zera do elementów ciągu Fibonacciego zależy od konwencji.

2.  Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń.

Jeśli dany jest wielomian W(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1}+a_nx^n\; to obliczając jego wartość

dla zadanego x\; bezpośrednio z podanego wzoru należy wykonać1 + 2 + 3 + ... + (n-1) + n = {n(n+1)\over2}\;mnożeń oraz n\; dodawań.

Tymczasem proste przekształcenie W(x)=a_0+x(a_1+x(a_2+\ldots +x(a_{n-1}+xa_n)\ldots))\;

sprawia, że wystarczy jedynie n\; mnożeń i n\; dodawań..

Dla przykładu, niech:

W(x)=2x^4-5x^2+4x+1\; chcemy obliczyć wartość tego wielomianu dla x=3/2.\;
Zapisujemy:
2x^4-5x^2+4x+1=x(x(x(x\cdot 2+0)-5)+4)+1; i podstawiamy x={3 \over 2}:

 

źródło wikipedia

Tagi: