Twoje Centrum Szkoleniowe

C++: Ciąg Fibonacciego i złota liczba

Ciąg Fibonacciego to sekwencja liczb, w której każda liczba (poza dwiema pierwszymi) jest sumą dwóch poprzednich. Rozpoczyna się od 0 i 1, a następne liczby tworzy się przez dodanie dwóch poprzedzających je liczb. 

• 0 (pierwszy element ciągu)
• 1 (drugi element)
• 1 (0+1, trzeci element)
• 2 (1+1, czwarty element)
• 3 (1+2, piąty element)
• 5 (2+3, szósty element)
• 8 (3+5, siódmy element)
• 13 (5+8, ósmy element)
• 21 (8+13, dziewiąty element)
• 34 (13+21, dziesiąty element)
• i tak dalej...

Historia ciągu

Nazwa "ciąg Fibonacciego" pochodzi od Leonarda z Pizy, znanego jako Fibonacci, który opisał tę sekwencję w swojej książce "Liber Abaci" z 1202 roku. Fibonacci przedstawił ciąg jako rozwiązanie problemu rozmnażania się królików. Mimo, że idea ciągu była znana w matematyce indyjskiej już wcześniej, to Fibonacci przyczynił się do jej popularyzacji w świecie zachodnim.

Związek z złotą liczbą

Ciąg Fibonacciego ma fascynujący związek ze "złotą liczbą" czyli phi (φ), określoną jako (1 + √5) / 2, która wynosi około 1.61803398875. Stosunek kolejnych liczb w ciągu Fibonacciego, jak się okazuje, zbliża się do złotej liczby. Im dalej w ciągu, tym stosunek dwóch kolejnych liczb Fibonacciego jest bliższy wartości phi. To odkrycie ma szerokie zastosowania w sztuce, architekturze, przyrodzie i finansach, gdzie złota liczba często pojawia się jako symbol harmonii i estetycznego piękna.

Przykładowa implementacja w C++

Wersja rekurencyjna

W metodzie rekurencyjnej obliczanie ciągu Fibonacciego polega na wywoływaniu funkcji, która odwołuje się do samej siebie. Każdy element ciągu jest sumą dwóch poprzednich elementów.

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

W powyższym przykładzie, jeśli n jest mniejsze lub równe 1, funkcja zwraca n, co odpowiada dwóm pierwszym liczbom ciągu (0 i 1). W przeciwnym wypadku, funkcja wywołuje siebie samej dla dwóch poprzednich liczb (n-1 i n-2) i zwraca ich sumę.

Wersja iteracyjna

Iteracyjne podejście do ciągu Fibonacciego polega na sekwencyjnym obliczaniu wartości ciągu w pętli.

int fibonacciIteracyjnie(int n) {
    int a = 0, b = 1, c;
    if (n == 0)
        return a;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

W tym kodzie, dla n równego 0 zwracana jest wartość 0. W pętli for, sumowane są dwie poprzednie wartości (a i b), a następnie wartości są przesuwane: a przyjmuje wartość b, a b - wartość c. W ten sposób, każdy kolejny element ciągu jest obliczany i przechowywany w zmiennej b, która jest zwracana po zakończeniu pętli.

Obie metody mają swoje zalety i wady. Metoda rekurencyjna jest bardziej zwięzła i bliższa matematycznej definicji ciągu, jednak może być mniej wydajna ze względu na wielokrotne wywołania funkcji, szczególnie dla dużych wartości n. Z kolei metoda iteracyjna jest zazwyczaj szybsza i bardziej efektywna pod względem zużycia pamięci, ale jest nieco bardziej skomplikowana.