Menu Zamknij

Ciąg Fibonacciego

Ciąg Fibonacciego to ciąg liczb, w którym pierwszy wyraz jest równy 0, drugi jest równy 1 a każdy następny jest sumą dwóch poprzednich. Można go przedstawić za pomocą następującego zapisu:

Jeżeli chcemy obliczyć wartość 4 wyrazu ciągu użyjemy wzoru:

F4 = F4-1 + F4-2 = F3 + F2

Wzór rekurencyjny nie dostarcza nam informacji o elemencie F3 i F2 więc musimy ponownie rozpisać te wyrazy posługując się wzorem na n:

F3 = F3−1 + F3−2 = F2 + F1
F2 = F2−1 + F2−2 = F1+F0 = 1 + 0 = 1

Już wiemy że, F2 wynosi 1. Dzięki temu możemy obliczyć wartość dla F3 i F4:

F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 =2 + 1 = 3

Ostatecznie 3 wyraz ciągu (czyli wyraz z indeksem 4) Fibonacciego wynosi 3.

Ciąg Fibonacciego – metoda iteracyjna

p – poprzedni wyraz (na początku równy zerowemu wyrazowi)
w – obecny wyraz (na początku równy pierwszemu wyrazowi)

Pętla for i in range(n-1) wykona się n-1 razy, czyli np. dla n=2 wykona się 1 raz.

Można oczywiście taki ciąg zapisać też w innej formie . Poniższy algorytm przedstawia trochę inny sposób obliczania danego elementu ciągu:

Ciąg Fibonacciego – metoda rekurencyjna

Rekurencja, rekursja (z łac. recurrere, przybiec z powrotem) – odwoływanie się funkcji lub definicji do samej siebie.

Tą metodą algorytm napisany w języku Python może przyjąć następujący format: