Algorytmy – Fibonacci

Algorytmy są jednym z najwinniejszych tematów na rozmowach kwalifikacyjnych czy to w teorii czy w sprawdzeniu umiejętności programowania. W tym wpisie zajmę się opisaniem algorytmu Fibonacci w Javie.

Fibonacci to seria liczb naturalnych gdzie każda kolejna liczba jest równa sumie licz dwóm poprzednim. Pierwsze dwie liczby w ciągu Fibonacci’ego są zawsze 1, 1. Wynika to z: 0+1 =1 więc: 0, 1, 1, 2… Liczba zero jest czasem pomijana. Wzór na policzenie liczb jest następujący: n = fn-1 + fn-2.

Teraz przedstawię napisany algorytm w języku Java. Został on napisany za pomocą metody statycznej i wywołany w metodzie „main”. Liczbę ciągu Fibonacciego podaje użytkownik przy użyciu klasy Scanner. W metda fibonacciIteration (int number) przyjmuje parametr „number” który zostanie przekazany przez użytkownika do metody. Następnie w instrukcji warunkowej if został zdefiniowany przypadek gdy nasz użytkownik jako długość ciągu podaje wartość 1 lub 2. Chodzi tutaj o te dwie pierwsze liczby ciągu które równają się 1. Liczba 0 jest naszym indeksem 0, liczba 1 indeksem 1, liczba 2 jest sumą indeksu 0 i indeksu 1 a więc wynik również będzie wynosić 1.

 private static int fibonacciIteration(int number) {
    if (number == 1 || number == 2) {
        return 1;
    } 

Następnie definiujemy kolejno trzy zmienne : fib1, fib2 które przyjmują wartość 1 oraz Fibonacci która będzie pełnić role sumy. W tym rozwiązaniu wykorzystujemy pętle for w której iteracje rozpoczynamy od 3. Wcześniejsze iteracje zostały zdefiniowane już w instrukcji warunkowej. Natomiast w pętli suma równa się sumie dwóm kolejnym zmiennym. W kolejnych wierszach widzimy przypisanie zmiennej fib1 do fib2 oraz fib2 do fibonacci. Oznacza tyle że np: liczba 3 która występowała jako fib2 teraz jest zmienna fib1. Zmienną fib2 jest zaś suma czyli 5 (ponieważ fib1 = 2 + fib2 =3).

 int fib1 = 1, fib2 = 1, fibonacci = 1;
    for (int i = 3; i <= number; i++) {
        fibonacci = fib1 + fib2;
        fib1 = fib2;
        fib2 = fibonacci;
    } 

Całość algorytmu przedstawia się następująco:

private static int fibonacciIteration(int number) {
    if (number == 1 || number == 2) {
        return 1;
    }

    int fib1 = 1, fib2 = 1, fibonacci = 1;
    for (int i = 3; i <= number; i++) {
        fibonacci = fib1 + fib2;
        fib1 = fib2;
        fib2 = fibonacci;
    }
    return fibonacci;
}