Reklama
Wizyt
Dzisiaj: 44Wszystkich: 184702

Liczby Fibonacciego, schemat Hornera

Informatyka » zakres rozszerzony » Iteracyjna realizacja wybranych algorytmów » Liczby Fibonacciego, schemat Hornera

 

Liczby Fibonacciego

Leonardo Fibonacci, włoski matematyk pochodzący z Pizy, żył w latach 1175-1250. Kształcił się początkowo po kierunkiem arabskiego nauczyciela na terenie obecnej algierskiej Beżai. W miarę postępów nauki i chęci dalszego studiowania zwiedził Europę i kraje Wschodu. Podczas swych podróży zapoznał się z osiągnięciami arabskich i hinduskich matematyków, między innymi z systemem dziesiętnym, który później propagował.

Fibonacci niezwykle pilnie studiował matematykę, umiał ją także wzbogacać. Wprawdzie jego prace, które dotyczyły teorii liczb, musiały czekać na kontynuację ponad czterysta lat, ale jego nazwisko weszło do matematyki – głównie dzięki ciągowi liczb, nazwanemu od jego nazwiska ciągiem Fibonacciego.

Ciąg Fibonacciego to ciąg liczb naturalnych określonych w następujący sposób:

 

 

  Kolejne wyrazy tego ciągu nazywane są liczbami Fibonacciego. Zaliczanie zera do elementów ciągu Fibonacciego zależy od umowy - część autorów definiuje ciąg od F1 = F2 = 1.

Pierwsze kilka wyrazów ciągu Fibonacciego to:

 

  Ciąg Fibonaciego należy do ulubionych ciągów spotykanych w  przyrodzie – można go odnaleźć w wielu jej aspektach – zarówno w kształtach fizycznych struktur, jak i w przebiegu zmian w strukturach dynamicznych.

  Zmiany dynamiczne pod tym względem najlepiej charakteryzuje rozmnażanie się królików. Przy założeniu, że początkowo mamy jedną parę – samca i samicę, którzy po miesiącu wydadzą na świat potomstwo, po kolejnym miesiącu ich progenitura jest zdolna do reprodukcji, rodzice zaś nadal się rozmnażają, łatwo policzyć roczny przyrost królików w sposób charakterystyczny dla naszego ciągu.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Program w C++ realizujący iteracyjny sposób obliczania liczb Fibonacciego

 

 

 

 

Schemat Hornera

Schemat Hornera jest algorytmem służącym do bardzo szybkiego obliczania wartości wielomianu. Redukuje on ilość mnożeń do minimum.

 

Algorytm obliczania wartości wielomianu:

schematem Hornera możemy zapisać w postaci:

 

 

 

 

 

Reklama