Oblicza n-ty wyraz ciągu Fibonacciego iteracyjnie, w czasie O(n) i pamięci O(1).
Ciąg Fibonacciego definiuje się następująco: pierwsze dwa wyrazy to 1, a każdy kolejny jest sumą dwóch poprzednich.
F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) dla n > 2
Pierwsze wyrazy: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
Wersja iteracyjna oblicza n-ty wyraz ciągu w pętli, przechowując tylko dwa ostatnie wyrazy. Dzięki temu mamy złożoność czasową O(n) i stałą pamięciową O(1).
Porównanie z wersją rekurencyjną: wersja iteracyjna jest drastycznie szybsza – rekurencyjna ma złożoność wykładniczą O(2ⁿ), bo wielokrotnie przelicza te same wyrazy. Dla n = 50 wersja iteracyjna kończy się natychmiast, a rekurencyjna może działać minuty.
Na maturze: wersja iteracyjna jest standardem przy implementacji ciągu Fibonacciego.
funkcja fibonacci_iter(n): jeżeli n ≤ 2: zwróć 1 poprzedni ← 1 aktualny ← 1 // budujemy ciąg od trzeciego wyrazu w górę dla i od 3 do n: nastepny ← poprzedni + aktualny poprzedni ← aktualny aktualny ← nastepny zwróć aktualny
def fibonacci_iter(n):
if n <= 2:
return 1
poprzedni = 1
aktualny = 1
for i in range(3, n + 1):
nastepny = poprzedni + aktualny
poprzedni = aktualny
aktualny = nastepny
return aktualny
# Przykład użycia
print(fibonacci_iter(10))
# Wynik: 55
print(fibonacci_iter(20))
# Wynik: 6765#include <iostream>
using namespace std;
long long fibonacci_iter(int n) {
if (n <= 2) return 1;
long long poprzedni = 1, aktualny = 1;
for (int i = 3; i <= n; i++) {
long long nastepny = poprzedni + aktualny;
poprzedni = aktualny;
aktualny = nastepny;
}
return aktualny;
}
int main() {
cout << fibonacci_iter(10) << "\n"; // 55
cout << fibonacci_iter(20) << "\n"; // 6765
}O(n)O(1)Wyznacz 10 kolejnych wyrazów ciągu Fibonacciego metodą iteracyjną. Wypisz stany pośrednie zmiennych poprzedni i aktualny po każdym kroku pętli.
Zapisz w wybranym języku programowania algorytm obliczający n-ty wyraz ciągu Fibonacciego bez użycia rekurencji. Złożoność pamięciowa nie może przekraczać O(1).
Wyznacz i wypisz wszystkie wyrazy ciągu Fibonacciego mniejsze niż 1000. Podaj ich liczbę.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: