Ciąg Fibonacciego: algorytm, schemat blokowy i kalkulator

23 maja 2024
Opublikował: Daria
Kategoria: Baza wiedzy

Jednym z zagadnień, które można określić jako podstawowe w zgłębianiu tajników algorytmiki, jest ciąg Fibonacciego. Pierwotnie został on opracowany przez włoskiego matematyka Leonarda z Pizy, który opisał przy jego pomocy proces rozmnażania się populacji królików. Warto jest ten ciąg poznać i zrozumieć, gdyż pozwala on na polepszenie zrozumienia różnic pomiędzy rekurencyjną, a iteracyjną metodą konstruowania algorytmów. Oprócz tego jest duża szansa, że trafi się on na maturze z informatyki oraz na studiach.

Spis treści

1 Kalkulator Ciągu Fibonacciego – Zakres liczb

2 Na czym polega Ciąg Fibonacciego – wzór i przykład

3 Jak liczyć Ciąg Fibonacciego – implementacja algorytmu

3.1 Rekurencyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

3.2 Rekurencyjny Ciąg Fibonacciego – Python, C++ i Java

3.3 Iteracyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

3.4 Iteracyjny Ciąg Fibonacciego – Python, C++ i Java

4 Najczęściej zadawane pytania o Ciąg Fibonacciego

Kalkulator Ciągu Fibonacciego – Zakres liczb

Jeśli potrzebujesz sprawdzenia, czy Twój algorytm działa prawidłowo lub też zorientowania się czy prawidłowo rozumiesz ten rodzaj ciągu, skorzystaj z poniższego kalkulatora. Przekonasz się, jakie wyrazy Ciągu Fibonacciego występują w podanym zakresie liczb. Natomiast jeśli interesuje Cię n-ty wyraz ciągu, to w obu polach podaj tę samą liczbę.

Dane wejściowe

Wyniki:

Komunikat:
Suma ciągu:
Ciąg Fibonacciego w podanym zakresie:

Na czym polega Ciąg Fibonacciego – wzór i przykład

Z ciągiem Fibonacciego zetkniemy się również w dziedzinach pozainformatycznych. W biologii z jego pomocą opiszemy naturalne linie spiralne spotykane w roślinach. Wynika to z tego, że kąt wyrastania nowych organów (np. łodyg czy liści) jest równy proporcji, którą opisuje iloraz dwóch kolejnych liczb z ciągu Fibonacciego (a im większe liczby z ciągu weźmiemy na warsztat, tym dokładniejszą proporcję uzyskamy). Zależność tę nazywamy: „złotym kątem”.

Innym przykładem jest sztuka: kompozytorzy czasem tworzą swoje utwory w oparciu o zależności wyprowadzone z relacji pomiędzy kolejnymi liczbami Fibonacciego, zaś malarze potrafią planować rozłożenie elementów na obrazie w oparciu o estetykę odnoszącą się do tzw.: „złotego podziału”. Ten algorytm znajdziemy nawet na giełdzie, gdzie inwestorzy czasem wykorzystują zniesienia Fibonacciego przy szacowaniu korekt cen instrumentów finansowych.

Podstawowa zasada jest następująca: każda kolejna liczba ciągu jest sumą dwóch poprzednich wyrazów ciągu. Dlatego pierwsze dwie liczby musimy zdefiniować sami, zaś kolejne będą wynikać z poprzednich. Zakładamy, że są one równe 1. W takim razie:

F₁ = 1

F₂ = 1

F_n = F_n-1 + F_n-2

Z powyższego wzoru wynika, że początek ciągu będzie wyglądał następująco:

F = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…}

Z punktu widzenia matury najważniejsza jest kwestia skonstruowania odpowiedniego algorytmu, który będzie wyliczał dla nas wartości konkretnych elementów ciągu. Musimy rozumieć zasadę działania na tyle, aby móc również rozwiązać zagadki oparte na ciągach zbliżonych do Fibonacciego. CKE często traktuje bazowy ciąg Fibonacciego jako inspirację pod algorytmy proponowane w zadaniach maturalnych, np. musimy być też gotowi na zrobienie podobnego ciągu, lecz opartego na sumowaniu trzech poprzednich elementów (takie rozwiązanie nazywamy ciągiem „Tribonacciego”). Omówmy wpierw wersję rekurencyjną algorytmu, a więc wprost wynikającą z definicji.

Jak liczyć Ciąg Fibonacciego – implementacja algorytmu

Algorytm obliczania n-tego wyrazu Ciągu Fibonacciego można zaimplementować na dwa sposoby, czyli rekurencyjnie oraz iteracyjnie. Warto jednak zauważyć, że pierwsza metoda jest mocno niewydajna, dlatego też rzadko się ją stosuje, szczególnie przy dużych zakresach liczb.

Rekurencyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

Wariant rekurencyjny jest wersją prostszą w zapamiętaniu. Właściwie sprowadza się do przepisania definicji na język, w którym programujemy, oraz osadzenie go w funkcji. Zwróć uwagę, że definicje matematyczne bardzo często są łatwe w implementacji rekurencyjnej.

Schemat blokowy - Ciąg Fibonacciego rekurencja — Liczby Fibonacciego i wzorce z nimi związane są również używane w dziedzinach związanych z technologią, takich jak projektowanie interfejsów użytkownika, grafika komputerowa, animacje, czy wzornictwo stron internetowych.

W algorytmie zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku. Złożoność rekurencyjnej metody Fibonacciego wynosi O(2ⁿ).

funkcja fibonacci(n)
    jeżeli n = 1 lub n = 2 wykonuj
        zwróć 1
    w przeciwnym razie
        zwróć fibonacci (n - 1) + fibonacci (n - 2)

funkcja fibonacci(n)

jeżeli n = 1 lub n = 2 wykonuj

zwróć 1

w przeciwnym razie

zwróć fibonacci (n - 1) + fibonacci (n - 2)

Opis Ciągu Fibonacciego – Pseudokod

1 linia – Definiujemy funkcję o nazwie Fibonacci, która przyjmuje argument n, czyli o który wyraz Ciągu Fibonacciego chodzi.
2 linia – Sprawdzamy warunek: jeśli n jest równe 1 lub 2, przechodzimy do linii 3, w przeciwnym razie przechodzimy do linii 4.
3 linia – Jeśli warunek jest spełniony, zwracamy wartość 1.
4 linia – W przeciwnym razie (jeśli n nie jest równe ani 1, ani 2), przechodzimy do iinii 5.
5 linia – Zwracamy wynik dodawania funkcji Fibonacci(n – 1) oraz Fibonacci(n – 2).

Rekurencyjny Ciąg Fibonacciego – Python, C++ i Java

Ciąg Fibonacciego – Python

def Fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return Fibonacci(n - 1) + Fibonacci(n - 2)

n = int(input("Podaj n: "))
print("N-ty wyraz Ciągu Fibonacciego to: ",Fibonacci(n))

def Fibonacci(n):

if n == 1 or n == 2:

return 1

return Fibonacci(n - 1) + Fibonacci(n - 2)

n = int(input("Podaj n: "))

print("N-ty wyraz Ciągu Fibonacciego to: ",Fibonacci(n))

Ciąg Fibonacciego – C++

#include <iostream>

using namespace std;

int Fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main() {
    int n;
    cout << "Podaj n: ";
    cin >> n;
    cout << "N-ty wyraz Ciągu Fibonacciego to: " << Fibonacci(n) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int Fibonacci(int n) {

if (n == 1 || n == 2) {

return 1;

}

return Fibonacci(n - 1) + Fibonacci(n - 2);

}

int main() {

int n;

cout << "Podaj n: ";

cin >> n;

cout << "N-ty wyraz Ciągu Fibonacciego to: " << Fibonacci(n) << endl;

return 0;

}

Ciąg Fibonacciego – Java

import java.util.Scanner;

public class Main {
    public static int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Podaj n: ");
        int n = scanner.nextInt();
        System.out.println("N-ty wyraz Ciągu Fibonacciego to: " + Fibonacci(n));
    }
}

import java.util.Scanner;

public class Main {

public static int Fibonacci(int n) {

if (n == 1 || n == 2) {

return 1;

}

return Fibonacci(n - 1) + Fibonacci(n - 2);

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Podaj n: ");

int n = scanner.nextInt();

System.out.println("N-ty wyraz Ciągu Fibonacciego to: " + Fibonacci(n));

}

Iteracyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

Cechą charakterystyczną tej wersji algorytmu jest to, że musimy wykorzystać w nim dodatkowe zmienne pomocnicze. Jest to konieczne, aby w trakcie wykonywania kolejnych operacji nie zgubić żadnej z wartości. Algorytm jest o tyle niewygodny, że wymaga swoistego „wachlowania” wartościami zmiennych.

W przykładzie posłużymy się następującymi zmiennymi: a i b będą służyły do przechowywania poprzedniego oraz bieżącego wyrazu ciągu, przy założeniu, że b zachowuje właściwy wynik dla każdej iteracji (więc co do zasady będzie „tą większą liczbą”). Żeby operacja była możliwa, musimy również przy każdym powtórzeniu przechować jej wartość tak, aby na skutek wyliczania kolejnej sumy, nie utracić jej wartości, bowiem przy kolejnej iteracji to „ta większa” będzie musiała stać się „tą mniejszą”. Wykorzystamy do tego zmienną temp (skrót od temporary czyli tymczasowa).

Schemat blokowy - Ciąg Fibonacciego Iteracja — Co ciekawe liczby Fibonacciego znalazły zastosowanie w teorii muzyki i kompozycji. Wykorzystanie wzorców opartych na ciągu Fibonacciego może nadać muzyce ciekawszy i harmonijny charakter.

Tak samo jak w wersji rekurencyjnej, zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku. Złożoność czasowa iteracyjnej metody Fibonacciego wynosi O(n).

funkcja fibonacci(n)
    a ← 1
    b ← 1
    dla i = 2, 3, …, n-1 wykonuj
        temp ← b
        b ← a + b
        a ← temp
    zwróć b i zakończ

funkcja fibonacci(n)

a ← 1

b ← 1

dla i = 2, 3, …, n-1 wykonuj

temp ← b

b ← a + b

a ← temp

zwróć b i zakończ

Opis Ciągu Fibonacciego – Pseudokod

1 linia – Definiujemy funkcję o nazwie Fibonacci, która przyjmuje argument n, czyli o który wyraz Ciągu Fibonacciego chodzi.
2 linia – Inicjujemy zmienną a jako 1.
3 linia – Inicjujemy zmienną b jako 1.
4 linia – Rozpoczynamy pętlę dla (odpowiednik for), w której zmienna i będzie przyjmować wartości od 2 do n-1.
5 linia – Wewnątrz pętli zapisujemy aktualną wartość zmiennej b do zmiennej tymczasowej temp.
6 linia – Przypisujemy zmiennej b sumę wartości a i b, czyli kolejny wyraz Ciągu Fibonacciego jak wynika ze wzoru.
7 linia – Przypisujemy zmiennej a, wartość zmiennej temp.
8 linia – Po zakończeniu pętli, zwracamy wartość zmiennej b, czyli n-ty wyraz Ciągu Fibonacciego.

Iteracyjny Ciąg Fibonacciego – Python, C++ i Java

Ciąg Fibonacciego – Python

def Fibonacci(n):
    a = 1
    b = 1
    for i in range(2, n):
        temp = b
        b = a + b
        a = temp
    return b

n = int(input("Podaj n: "))
print("N-ty wyraz Ciągu Fibonacciego to: ",Fibonacci(n))

def Fibonacci(n):

a = 1

b = 1

for i in range(2, n):

temp = b

b = a + b

a = temp

return b

n = int(input("Podaj n: "))

print("N-ty wyraz Ciągu Fibonacciego to: ",Fibonacci(n))

Ciąg Fibonacciego – C++

#include <iostream>

using namespace std;

int Fibonacci(int n) {
    int a = 1;
    int b = 1;
    for (int i = 2; i < n; i++) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n;
    cout << "Podaj n: ";
    cin >> n;
    cout << "N-ty wyraz Ciągu Fibonacciego to: " << Fibonacci(n) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int Fibonacci(int n) {

int a = 1;

int b = 1;

for (int i = 2; i < n; i++) {

int temp = b;

b = a + b;

a = temp;

}

return b;

}

int main() {

int n;

cout << "Podaj n: ";

cin >> n;

cout << "N-ty wyraz Ciągu Fibonacciego to: " << Fibonacci(n) << endl;

return 0;

}

Ciąg Fibonacciego – Java

import java.util.Scanner;

public class Main {
    public static int Fibonacci(int n) {
        int a = 1;
        int b = 1;
        for (int i = 2; i < n; i++) {
            int temp = b;
            b = a + b;
            a = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Podaj n: ");
        int n = scanner.nextInt();
        System.out.println("N-ty wyraz Ciągu Fibonacciego to: " + Fibonacci(n));
    }
}

import java.util.Scanner;

public class Main {

public static int Fibonacci(int n) {

int a = 1;

int b = 1;

for (int i = 2; i < n; i++) {

int temp = b;

b = a + b;

a = temp;

}

return b;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("Podaj n: ");

int n = scanner.nextInt();

System.out.println("N-ty wyraz Ciągu Fibonacciego to: " + Fibonacci(n));

}

Podsumowanie

Jeżeli opracujesz i w pełni zrozumiesz obie wersje algorytmu, bez problemu poradzisz sobie również z algorytmami podobnymi do ciągu Fibonacciego. Zadania tego typu możesz napotkać zarówno w zadaniach teoretycznych jak i praktycznych na egzaminie maturalnym, więc nigdy nie ucz się algorytmów na pamięć – najważniejsze jest ich zrozumienie. Bądź też gotowy do wykorzystania zarówno wersji rekurencyjnej jak i iteracyjnej. Może być bowiem tak, że w zadaniu teoretycznym natrafisz na polecenie, które już na wstępie precyzuje, w jakiej wersji musisz skonstruować algorytm. Dlatego nigdy nie pomijaj zagadnień niewygodnych, lecz wykorzystaj je, aby poszerzyć swoje umiejętności.

Najczęściej zadawane pytania o Ciąg Fibonacciego

Jakie są różnice między iteracyjnym a rekurencyjnym podejściem do obliczania ciągu Fibonacciego?

Rekurencyjne podejście bez optymalizacji może prowadzić do wielokrotnego obliczania tych samych wartości, co powoduje znaczny narzut czasowy. Dodatkowo też wymaga dużej ilości pamięci.
Iteracyjne podejście jest bardziej wydajne i eliminuje potrzebę wielokrotnego obliczania tych samych wartości, co jest możliwe dzięki korzystaniu z pętli. Na dodatek potrzebuje mniejszych zasobów pamięci.

Na czym polegają zastosowania ciągu Fibonacciego?

Algorytmy optymalizacyjne – ciąg Fibonacciego jest stosowany w rozwiązaniach, takich jak optymalizacja wyszukiwania binarnego, wyszukiwanie złotego punktu, czy optymalizacja jednowymiarowych funkcji jednomodalnych.
Finanse i ekonomia – wykorzystuje się go w analizie rynków finansowych, prognozowaniu cen akcji i innych instrumentów finansowych.
Architektura i sztuka – wzory bazujące na ciągu Fibonacciego są stosowane w projektowaniu architektonicznym, wzornictwie, sztuce i wzornictwie wnętrz, tworząc estetyczne proporcje.

Jakie są właściwości matematyczne ciągu Fibonacciego?

Złoty podział (Golden Ratio) – stosunek kolejnych liczb Fibonacciego zbliża się do wartości stałej matematycznej zwanej “złotym podziałem”. Stała ta jest bliska wartości 1.61803398875. W miarę zwiększania wartości n, stosunek kolejnych liczb Fibonacciego jest coraz bliższy tej stałej.
Wzór bineta – to wzór matematyczny, który pozwala obliczyć n-tą liczbę Fibonacciego bez potrzeby iteracyjnych obliczeń. Wzór ten wykorzystuje Złoty Stosunek i potęgi liczby 1,618. Jest to bardziej wydajna metoda obliczania dużych wartości z ciągu Fibonacciego.
Liczby Fibonacciego w przyrodzie – liczby Fibonacciego można zaobserwować w różnych wzorach wzrostu w przyrodzie, takich jak kształt muszli ślimaków, układ liści roślin, wzory rozkwitających kwiatów, itp. Wzorce te są znane jako “fraktale”.

Jak zoptymalizować ciąg Fibonacciego?

Memoizacja (Memoization) – używa się tablicy, która służy do zapisywania już obliczonych wartości ciągu Fibonacciego. W momencie obliczania n-tej liczby, sprawdzane jest, czy wartość ta została już obliczona i zapisana w tablicy. Jeśli tak, używany jest zapisany wynik bez konieczności ponownego obliczania. To ogranicza liczbę rekurencyjnych wywołań i zwiększa wydajność obliczeń.

Wpisy, które mogą Cię zainteresować:

Kalkulator Ciągu Fibonacciego – Zakres liczb

Na czym polega Ciąg Fibonacciego – wzór i przykład

Jak liczyć Ciąg Fibonacciego – implementacja algorytmu

Rekurencyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

Rekurencyjny Ciąg Fibonacciego – Python, C++ i Java

Iteracyjny Ciąg Fibonacciego – Schemat blokowy i pseudokod

Iteracyjny Ciąg Fibonacciego – Python, C++ i Java

Najczęściej zadawane pytania o Ciąg Fibonacciego

Matura z informatyki – dlaczego Python jest najlepszym wyborem?

Microsoft Access – przydatne narzędzie na maturze z informatyki

Dlaczego warto uczyć się informatyki?

Dbamy o prywatność Twoich danych

Mapa witryny: Korepetycje z informatyki

Polecane wpisy na blogu poświęconemu nauce informatyki