Ciąg Fibonacciego w C++. Algorytm w ujęciu dynamicznym

Ciąg Fibonacciego to ciąg liczb, w którym każda liczba jest sumą dwóch poprzednich. Początkowe kilka liczb w ciągu Fibonacciego wygląda tak: 1, 1, 2, 3, 5, 8, 13, 21, 34, … Formalnie, ciąg Fibonacciego zaczyna się od dwóch pierwszych elementów, które są zazwyczaj ustawiane na 0 i 1, a kolejne liczby są generowane według wzoru:

F(n) = F(n-1) + F(n-2)

przy założeniu, że F(0) = 0; F(1) = F(2) = 1

Istota ciągu Fibonacciego jest szeroko wykorzystywana w matematyce, informatyce, a także w różnych dziedzinach nauki i życia codziennego. Kilka zastosowań to:

1. Algorytmy i struktury danych: Ciąg Fibonacciego jest często używany do zilustrowania różnych algorytmów i struktur danych, takich jak rekurencja, programowanie dynamiczne czy też przykłady problemów optymalizacyjnych.
2. Finanse: Ciąg Fibonacciego ma zastosowanie w niektórych modelach finansowych, zwłaszcza w kontekście analizy rynków finansowych i prognozowania trendów.
3. Informatyka: W informatyce ciąg Fibonacciego może być używany w różnych kontekstach, takich jak optymalizacja algorytmów czy też do generowania pewnych struktur danych.
4. Sztuka i natura: Ciąg Fibonacciego występuje w wielu aspektach sztuki, architektury i przyrodzie. Na przykład, jego proporcje są często widoczne w projektowaniu kompozycji artystycznych i wzorców naturalnych.
5. Kody i kryptografia: W niektórych przypadkach ciąg Fibonacciego jest używany w kryptografii i generowaniu pseudolosowych liczb.
6. Złoty podział: Liczby w ciągu Fibonacciego mają tendencję do zbiegania się do tzw. złotego podziału, co ma zastosowanie w architekturze, projektowaniu graficznym i innych dziedzinach, gdzie proporcje estetyczne są istotne.

Algorytm wyznaczania n-tego wyrazu tego ciągu będzie się składał z funkcji fib, która będzie otrzymywała jako parametr wyraz ciągu, który ma zwrócić. Kompletny kod w języku C++ wygląda następująco:

#include <iostream>
#include <vector>
using namespace std;

int fib(int n)
{
    vector<int> dp(n + 1, 0);

    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main()
{
    int wej;
    cout << "Ktory wyraz ciagu Fibonacciego podac?\n";
    cin >> wej;
    cout << fib(wej) << "\n";

    return 0;
}

W programie została użyta standardowa klasa wektora #include <vector> z biblioteki standardowej C++, aby przechowywać wcześniej obliczone wartości ciągu Fibonacciego, co pozwala na efektywne wykorzystanie programowania dynamicznego i eliminuje konieczność wielokrotnego obliczania tych samych wartości.

Funkcja fib jest to rekurencyjna funkcja, która oblicza n-ty element ciągu Fibonacciego. Utworzono wektor dp o rozmiarze n+1 do przechowywania wcześniej obliczonych wartości. Zainicjowane zostały pierwsze dwa elementy ciągu (dp[1] i dp[2]) jako 1. Następnie użyta została pętla for, aby obliczyć pozostałe elementy ciągu Fibonacciego w sposób iteracyjny, unikając wielokrotnego obliczania tych samych wartości. Wynik obliczeń przechowywany jest w zmiennej dp[n] i jest zwracany jako wynik funkcji fib.

Podsumowanie

Ciąg Fibonacciego nie tylko stanowi fascynujące wyzwanie matematyczne, ale także odnajduje swoje zastosowanie w różnych dziedzinach nauki, informatyki, finansów czy nawet sztuki. Niniejszy artykuł stanowi jedynie wstęp do tematu ciągu Fibonacciego i jego implementacji w C++. Zachęcamy do eksperymentowania, zgłębiania bardziej zaawansowanych aspektów oraz odkrywania dodatkowych zastosowań tego fascynującego ciągu liczb.