Oblicza n-ty wyraz ciągu Fibonacciego w pętli, pamiętając tylko dwa ostatnie wyrazy.
Ciąg Fibonacciego to ciąg liczb, w którym pierwsze dwa wyrazy to 1, a każdy następny jest sumą dwóch poprzednich. Zapisujemy to tak: F(1) = 1, F(2) = 1, a dalej F(n) = F(n-1) + F(n-2). Pierwsze wyrazy to 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ….
Jak liczyć go w pętli? W wersji iteracyjnej nie liczymy niczego dwa razy. Pamiętamy tylko dwa ostatnie wyrazy – nazwijmy je poprzedni i aktualny. W każdym obrocie pętli robimy ich sumę (to nowy wyraz), a potem przesuwamy się o jeden do przodu: poprzedni staje się starym aktualny, a aktualny – nową sumą. Powtarzamy, aż dojdziemy do n-tego wyrazu.
Dlaczego wystarczą dwie zmienne? Bo do policzenia kolejnego wyrazu potrzeba tylko dwóch poprzednich – reszty ciągu w ogóle nie musimy trzymać w pamięci. Dlatego pamięć jest stała, O(1), niezależnie od tego, jak daleki wyraz liczymy.
Czym to bije wersję rekurencyjną? Prostota i szybkość. Wersja rekurencyjna w naiwnej postaci liczy te same wyrazy w kółko i ma złożoność wykładniczą – dla n = 50 potrafi liczyć bardzo długo. Wersja iteracyjna dla tego samego n kończy się w mgnieniu oka, bo robi tylko n prostych dodawań.
Na maturze: to standardowy sposób liczenia Fibonacciego. Zadania często proszą wprost o wersję „bez rekurencji" albo o pamięć O(1) – wtedy chodzi dokładnie o ten algorytm.
Prześledź krok po kroku, jak powstaje ciąg Fibonacciego. Startujemy od dwóch jedynek. W każdym kroku bierzemy dwa ostatnie wyrazy (podświetlone), dodajemy je i dokładamy wynik na koniec. I tak w kółko – to jest właśnie wersja iteracyjna, bez rekurencji.
Naciśnij „Krok", aby policzyć kolejny wyraz, albo „Auto".
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):
"""Zwraca n-ty wyraz ciągu Fibonacciego (F(1) = F(2) = 1)."""
if n <= 2:
return 1
poprzedni = 1
aktualny = 1
for i in range(3, n + 1):
nastepny = poprzedni + aktualny # nowy wyraz
poprzedni = aktualny # przesuwamy okno o jeden
aktualny = nastepny
return aktualny
# Przykłady 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; // nowy wyraz
poprzedni = aktualny; // przesuwamy okno o jeden
aktualny = nastepny;
}
return aktualny;
}
int main() {
cout << fibonacci_iter(10) << "\n"; // Wynik: 55
cout << fibonacci_iter(20) << "\n"; // Wynik: 6765
}Od dwóch jedynek: F(1) = 1 i F(2) = 1. Każdy następny wyraz to suma dwóch poprzednich, więc dalej idzie 2, 3, 5, 8, …. (Bywa też wersja zaczynająca się od 0, 1 – warto sprawdzić, którą przyjmuje zadanie.)
Bo nie liczy tego samego wielokrotnie. Naiwna rekurencja przelicza te same wyrazy w kółko i przez to jest wykładniczo wolna. Iteracja robi tylko n dodawań i pamięta dwie liczby.
Bo najpierw liczymy sumę do zmiennej pomocniczej, a dopiero potem przesuwamy okno dwóch wyrazów o jeden. Bez zmiennej pomocniczej nadpisalibyśmy wartość, która jest jeszcze potrzebna.
Za mały typ liczbowy. Wyrazy rosną tak szybko, że w int szybko przekraczają zakres – w C++ używaj long long.
Policz kolejne wyrazy ciągu (start: 1, 1, 2, 3, 5, …). Kliknij Sprawdź.
Ciąg to `1, 1, 2, 3, 5, , , . Po wyrazach 21 i 34` następny to .
Uzupełnij wartość wyrazu (numerujemy od F(1) = 1):
| Wyraz | Wartość |
|---|---|
| F(6) | |
| F(9) | |
| F(10) |
W pętli pamiętamy tylko ostatnie wyrazy, dlatego pamięć jest stała.
O(n)O(1)Pętla wykonuje się mniej więcej n razy, a w każdym obrocie robimy jedno dodawanie i dwa przepisania – stąd czas O(n). Pamięć jest stała, O(1), bo cały czas trzymamy tylko dwie liczby (dwa ostatnie wyrazy), a nie cały ciąg.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: