Jakub Piskorowski on 28/02/2022 wersja: 1.1
Przedstawienie działania algorytmu ciągu Fibonacciego
Kod źródłowy:
ciag-fibonacciego.cpp
ciag-fibonacciego-rekurencja.cpp
📒 Poziom 1
Powrót do Algorytmika
Leonardo Fibonacci był włoskim matematykiem żyjącym w latach od 1175 do 1250. Jest on autorem specyficznego ciągu liczbowego, który pojawia się w wielu zastosowaniach informatycznych (i nie tylko ).
Ciąg Fibonacciego to szczególny rodzaj ciągu liczb naturalnych. Liczby tego ciągu nazywane są liczbami Fibonacciego. Spotykane są w wielu dziedzinach i sytuacjach np. w matematyce, w przyrodzie, na rynkach giełdowych.
Przykłady graficzne reprezentacji złotego podziału.
Żródło: e-kursy-walut.pl
Spirala poziomów Fibonacciego
Żródło: ciekawe.org
Zloty podział w naturze
❗ 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.
Oto kilka pierwszych wyrazów ciągu Fibonacciego:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584...
Obliczając n-ty
wyraz ciągu, musisz posługiwać się wartościami poprzednimi czyli n-1
, n-2
itd. aż dojdziesz do wartości które znasz. Są nimi wartości dla F0
i F1
.
Wejście:
n
- numer liczby ciągu Fibonacciego do wyliczenia, n
∈ N.
Wyjście:
n
- ta liczba ciągu Fibonacciego.
K1: jeżeli n < 3
wykonuj krok K2
K2: zwróć wartość 1
K3: zwróć funkcja(n-2) + funkcja(n-1)
Wynik działania programu:
Podaj nr wyrazu ciagu: 50
50 wyraz ciagu ma wartosc 12586269025
Kod źródłowy: ciag-fibonacciego-rekurencja.cpp
Wejście:
n
– numer liczby ciągu Fibonacciego do wyliczenia, n
∈ N.
Wyjście:
n
- ta liczba ciągu Fibonacciego.
Zmienne pomocnicze:
f0
, f1
, f
– kolejne trzy liczby Fibonacciego, f0, f1, f∈C.
Lista kroków:
K1: f0 ← 0
pierwsza lub f i-2 liczba Fibonacciego
K2: f1 ← 1
druga lub f i-1 liczba Fibonacciego
K3: Dla i = 0, 1, ..., n:
wykonuj kroki K4...K9
K4: Jeśli i > 1,
to wykonuj kroki K6 do k8
K5: inaczej f ← i
i następny obieg pętli K3
K6: f ← f0 + f1
obliczamy kolejną liczbę Fibonacciego
K7: f0 ← f1
zapamiętujemy wyniki obliczeń pośrednich
K8: f1 ← f
dla następnego obiegu pętli
K9: Pisz f
wypisujemy liczbę ciągu
K10: Zakończ
Wynik działania programu:
Ile wyrazow ciagu wypisac: 10
0
1
1
2
3
5
8
13
21
34
55
Kod źródłowy: ciag-fibonacciego.cpp