Ciąg Fibonacciego w Pythonie i C++

Ciąg Fibonacciego to ciąg, w którym dwa pierwsze wyrazy są równe 1, a każdy kolejny jest sumą dwóch poprzednich: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… Prosty wzór, a jednocześnie jeden z najlepszych przykładów w nauce programowania: ten sam wynik można policzyć pętlą, rekurencją i rekurencją z zapamiętywaniem, a różnica w szybkości między tymi wersjami jest ogromna.

Na tej stronie znajdziesz wszystkie trzy wersje z kodem w Pythonie oraz C++, tabelę przebiegu pętli i liczbę wywołań rekurencji. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych i stosem wywołań.

Przejdź ciąg Fibonacciego krok po kroku

Definicja

Matematycznie ciąg zapisujemy tak:

• F(1) = 1, F(2) = 1,
• F(n) = F(n-1) + F(n-2) dla n > 2.

Czyli F(3) = 1 + 1 = 2, F(4) = 1 + 2 = 3, F(5) = 2 + 3 = 5 i tak dalej. Niektóre podręczniki zaczynają od F(0) = 0; wtedy wszystkie numery przesuwają się o jeden, ale same liczby są te same. W zadaniu zawsze sprawdź, od którego wyrazu liczy autor.

Fibonacci iteracyjnie (pętlą)

Żeby policzyć kolejny wyraz, wystarczą dwa ostatnie. Trzymamy je w zmiennych a i b i w każdym obrocie pętli przesuwamy o jeden wyraz dalej:

a, b = 1, 1
for i in range(10):
    print(a, end=" ")
    a, b = b, a + b
print()

1 1 2 3 5 8 13 21 34 55

Prześledźmy pierwsze obroty pętli:

Zapis a, b = b, a + b liczy całą prawą stronę przed przypisaniem, więc nie potrzeba zmiennej pomocniczej. Gdybyśmy napisali osobno a = b i b = a + b, druga linia użyłaby już nowego a i ciąg wyszedłby błędny. Wersja iteracyjna wykonuje około n dodawań i jest bardzo szybka: F(90) liczy natychmiast.

Tę samą pętlę łatwo przerobić na pytanie “który wyraz pierwszy przekracza 1000?”:

a, b = 1, 1
numer = 1
while a <= 1000:
    a, b = b, a + b
    numer += 1
print(numer, a)

17 1597

Ćwicz: pierwszy wyraz większy od tysiąca

Fibonacci rekurencyjnie

Wzór F(n) = F(n-1) + F(n-2) można przepisać wprost jako funkcję, która woła samą siebie. To rekurencja: przypadek bazowy (n <= 2) zatrzymuje wywołania, a reszta sprowadza zadanie do mniejszych. Dopiszmy licznik, żeby zobaczyć, ile pracy to kosztuje:

wywolania = 0


def fib(n):
    global wywolania
    wywolania += 1
    if n <= 2:
        return 1
    return fib(n - 1) + fib(n - 2)


print(fib(20))
print("wywolan:", wywolania)

6765
wywolan: 13529

Ponad 13 tysięcy wywołań dla wyniku, który pętla liczy w 20 krokach. Powód widać na małym przykładzie: fib(5) woła fib(4) i fib(3), fib(4) znowu woła fib(3) i fib(2), więc fib(3) liczy się dwa razy, a fib(2) trzy razy. Dla tej wersji liczba wywołań to dokładnie 2 * F(n) - 1:

Liczba wywołań rośnie tak szybko jak sam ciąg, czyli wykładniczo. F(40) prostą rekurencją to już ponad 200 milionów wywołań.

W przeglądarce warto krokować małe n, np. fib(4). Krok wchodzi do funkcji, a stos wywołań pokazuje kolejne wywołania jedno nad drugim: każde ma własne n, więc widać, jak rekurencja schodzi w głąb aż do przypadku bazowego i wraca z wynikami.

Krokuj rekurencję i licznik wywołań

Memoizacja: rekurencja z zapamiętywaniem

Skoro problemem jest liczenie tych samych wyrazów wiele razy, wystarczy je zapamiętać. Słownik pamiec przechowuje policzone już F(n). Ta technika to memoizacja (spamiętywanie) i jest pierwszym krokiem do programowania dynamicznego:

pamiec = {}
wywolania = 0


def fib(n):
    global wywolania
    wywolania += 1
    if n <= 2:
        return 1
    if n not in pamiec:
        pamiec[n] = fib(n - 1) + fib(n - 2)
    return pamiec[n]


print(fib(20))
print("wywolan:", wywolania)
print(fib(90))

6765
wywolan: 37
2880067194370816120

37 wywołań zamiast 13529, a F(90) liczy się natychmiast, choć prostą rekurencją nie doczekalibyśmy się wyniku. W Pythonie to samo daje gotowy dekorator functools.lru_cache, ale warto raz napisać słownik samodzielnie, żeby zrozumieć, co się dzieje.

Krokuj rekurencję z zapamiętywaniem

Ciąg Fibonacciego w C++

Wersja iteracyjna w C++ potrzebuje zmiennej pomocniczej, bo nie ma przypisania dwóch zmiennych naraz:

#include <iostream>
using namespace std;

int main() {
  int a = 1;
  int b = 1;
  for (int i = 1; i <= 15; i++) {
    cout << a << " ";
    int nastepny = a + b;
    a = b;
    b = nastepny;
  }
  cout << endl;
  return 0;
}

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

Typ int mieści wyrazy do F(46) = 1836311903; dalej trzeba użyć long long (do F(92)). Wersja rekurencyjna z licznikiem wywołań w C++:

#include <iostream>
using namespace std;

int wywolania = 0;

int fib(int n) {
  wywolania++;
  if (n <= 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

int main() {
  cout << fib(10) << endl;
  cout << "wywolan: " << wywolania << endl;
  return 0;
}

55
wywolan: 109

W C++ memoizację robi się zwykłą tablicą zamiast słownika: zero oznacza “jeszcze nie policzone”. Tablicę zerujemy na początku programu pętlą, żeby nie zależeć od wartości startowych.

#include <iostream>
using namespace std;

int pamiec[50];

int fib(int n) {
  if (n <= 2) {
    return 1;
  }
  if (pamiec[n] == 0) {
    pamiec[n] = fib(n - 1) + fib(n - 2);
  }
  return pamiec[n];
}

int main() {
  for (int i = 0; i < 50; i++) {
    pamiec[i] = 0;
  }
  cout << fib(30) << endl;
  cout << fib(40) << endl;
  return 0;
}

832040
102334155

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Ciąg Fibonacciego iteracyjnie

Specyfikacja. Dane: liczba naturalna n ≥ 1. Wynik: n-ty wyraz ciągu Fibonacciego (F1 = F2 = 1).

Lista kroków:

1. Wczytaj n. Ustaw a = 1 i b = 1 (dwa pierwsze wyrazy).
2. Powtórz n - 2 razy: oblicz c = a + b, potem zastąp a liczbą b, a b liczbą c.
3. Wypisz b i zakończ.

Pseudokod:

wczytaj n
a ← 1
b ← 1
dla i = 3, 4, ..., n wykonuj
  c ← a + b
  a ← b
  b ← c
wypisz b

Schemat blokowy:

Drzewo wywołań rekurencji fib(5). Wersja rekurencyjna liczy fib(n) jako fib(n - 1) + fib(n - 2). Drzewo pokazuje wszystkie wywołania dla fib(5): jest ich 9, a fib(3) liczy się dwa razy, fib(2) trzy razy. Wersja z pętlą liczy każdy wyraz tylko raz.

Najczęstsze błędy

• Brak przypadku bazowego. Funkcja rekurencyjna bez if n <= 2: return 1 woła się bez końca i kończy błędem przepełnienia stosu (w Pythonie RecursionError).
• Zła kolejność przypisań w pętli. a = b, a potem b = a + b używa już nowego a. W Pythonie pisz a, b = b, a + b, w C++ użyj zmiennej pomocniczej.
• Przesunięte numerowanie. Ciąg od F(0) = 0 i ciąg od F(1) = 1 mają te same liczby, ale inne numery. Przeczytaj w treści zadania, który wyraz jest pierwszy.
• Prosta rekurencja dla dużych n. fib(35) bez memoizacji to ponad 18 milionów wywołań. Dla dużych n używaj pętli albo zapamiętywania.
• Przepełnienie w C++. F(47) nie mieści się w int. W Pythonie liczby całkowite nie mają limitu.

Ćwicz w przeglądarce

W temacie “Ciąg Fibonacciego: iteracyjnie i rekurencyjnie” kursu Algorytmy z podstawy programowej czekają trzy przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• pierwsze 20 wyrazów ciągu Fibonacciego,
• pierwszy wyraz większy od tysiąca (z numerem wyrazu),
• suma parzystych wyrazów poniżej 4 milionów.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości zmiennych. Przy rekurencji Krok wchodzi do funkcji, a stos wywołań pokazuje wszystkie aktywne wywołania fib z ich własnymi n. Dalsze algorytmy z tego samego kursu: algorytm Euklidesa (też ma wersję rekurencyjną) oraz suma cyfr liczby. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Fibonacci to najlepszy temat na pierwszą rozmowę o rekurencji i jej koszcie: uczniowie piszą trzy wersje tego samego, mierzą liczbę wywołań i oglądają stos w trakcie krokowania. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.