Rekurencyjna i iteracyjna realizacja ciągu Fibonacciego

Człowiek od dawna dążył do znalezienia opisu ideału. Jednym z pomysłów opisu jest ciąg Fibonacciego, zwanego inaczej Złotym Podziałem.

Zajmiemy się tutaj implementacją kodu obliczającego kolejne wyrazy ciągu Fibonacciego dwoma metodami.

Zanim przejdziemy do realizacji programowej, zapoznajmy się z odrobiną teorii. Ciąg Fibonacciego można opisać wzorem ogólnym:

,

,

,

Czyli nasze kolejne wyrazy ciągu dla wynosi:

Tyle teorii nam wystarczy. Po większą dawkę wiedzy na ten temat odsyłam do źródeł zewnętrznych.

Przejdziemy teraz to programu. Głównym celem programu jest wydruk liczb ciągu Fibonacciego w zakresie osiągalnych liczb całkowitych. Program posiada opcję wyboru metody przebiegu algorytmu – rekurencyjnie lub iteracyjnie. Idzie za tym inna forma wyświetlania wyniku. Rekurencyjny – użytkownik podaj numer interesującego go wyrazu ciągu. Iteracyjny – wyniki są wyświetlane w formie tablicy, użytkownik wybiera ile wyrazów ciągu ma zawierać tablica. Użytkownik ma prawo wyboru poprzez menu. Przypomnijmy czym jest rekurencja i iteracja oraz czym się różnią.

Iteracja – jest to czynność powtarzania tej samej czynności określoną ilość razy np. w pętlach.

Rekurencja – jest to odwoływanie się naszej napisanej funkcji do samej siebie.

Pierwszym blokiem programowym jest menu użytkownika:

int choice;
    do {
            printf("Podaj opcje: \n1 - obliczanie n-tego wyrazu fibbonaciego \n");
            printf("2 - wypisanie pierwszych n wyrazow \n");
            printf("0 - wyjdz\n\n");
            scanf("%d", &choice);
            if(choice == 1)

Mówiłem wcześniej, że zależy nam na jak największym zasięgu naszego programu. Właśnie dla tego pojawia się tutaj kolejny blok programu:

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long int ULLI;

Zadeklarowane tu zostały dwie najczęściej stosowane biblioteki oraz globalna zmienna ULLI (skrót od unsigned long long int).

Element typedef pozwala zamienić stosowanie wyrazu int na ULLI. Poprawia to znacznie klarowność kodu oraz ułatwia pracę.

Element unsigned pozwala mi przesunąć zakres typu int w stronę liczb dodatnich. Jest to korzystne gdyż korzystamy z liczb całkowitych dodatnich. Poprawia to znaczenie zasięg i moc algorytmu. Konkretniej mówiąc pozwala mi to wykorzystać 64 bity przypisane dla typu long long int w stronę operatorów ciągu tj. z zakresu −9 223 372 036 854 775 808 — +9 223 372 036 854 775 807, do zakresu 0 — +18 446 744 073 709 551 615.

Omówimy teraz część rekurencyjną kodu:

ULLI fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

Niestety… Aby zrozumieć rekurencję, trzeba zrozumieć rekurencję. Ale zastosowany powyżej algorytm opisuje rysunek:

Jest to typowa rekurencja. Algorytm działa po przez dodawane kolejnych wyrazów. Dodaje on dwa składniki bazowe a potem dodaje powielenie.

Ten segment programu wykazuje się błędem podczas podania przez użytkownika innego znaku niż cyfra. Objawia się to zawieszeniem programu. Przy podaniu liczby ujemnej program powraca do wyboru metody obliczeniowej. Skuteczne i szybkie obliczenia można otrzymać do ok. 43 wyrazu ciągu. Jest to spowodowane specyfikacją metody rekurencji (ilość dodawań) oraz możliwościami hardwareowymi.

Metoda iteracyjna:

void print_fib(int n)
{
    ULLI a = 0;
    ULLI b = 1;
    ULLI c = a+b;
    int i;

    for(i = 1; i <= n; i++)
    {
        printf("%i %llu\n", i, c);
        c = a+b;
        a=b;
        b=c;

    }
    printf("\n");
}

Na początku deklarowane są zmienne typu int pod nazwą ULLI. Są to zmienne lokalne. Pętla for pobiera i=1, sprawdza warunek i zwiększa i o jeden. Printf wyświetla numer wyrazu i obliczony wyraz zgodnie z zastosowaną arytmetyką.

Tak samo jak w poprzedniej metodzie wprowadzenie liczy ujemnej powoduje powrót do menu. Wprowadzenie innego znaku niż liczba powoduje zapętlenie algorytmu na jednym wyrazie ciągu lub zapętla się w nieskończoność. Obliczenia są prawidłowe do 93 wyrazu ciągu włącznie. Dalej następuje koniec zakresu i podanie fałszywych wartości.

Zachęcam do doczytania odnośnie Złotego Podziału. Jak widzicie jest to całkiem ciekawy temat, który można opisać za pomocą nieskomplikowanego kodu. Na zakończenie podaję kod całościowy:

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long int ULLI;



ULLI fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n-1)+fib(n-2);
}

void print_fib(int n)
{
    ULLI a = 0;
    ULLI b = 1;
    ULLI c = a+b;
    int i;

    for(i = 1; i <= n; i++)
    {
        printf("%i %llu\n", i, c);
        c = a+b;
        a=b;
        b=c;

    }
    printf("\n");
    //max is fib(93)
}

void info()
{
    printf("Radoslaw Sakowicz\n");
    printf("www.uengineering.net\n\n");
    printf("Rekurencyjne obliczanie liczb Fibonacciego.\n\n");
}

int main()
{

    info();

    int choice;
    do {
            printf("Podaj opcje: \n1 - obliczanie n-tego wyrazu fibbonaciego \n");
            printf("2 - wypisanie pierwszych n wyrazow \n");
            printf("0 - wyjdz\n\n");
            scanf("%d", &choice);
            if(choice == 1)
            {
                int n;

                do {
                    printf("Podaj numer wyrazu (liczba ujemna - koniec obliczen), n = ");
                    scanf("%d", &n);
                    if(n < 0)
                        break;
                    printf("(%d) = %d\n\n", n, fib(n));
                } while(1);

            }
            else if(choice == 2)
            {
                int n;
                do {
                    printf("Podaj ile wyrazow chcesz poznac (liczba ujemna - koniec obliczen): \n\n");
                    scanf("%d", &n);
                    print_fib(n);

                } while (n >= 0);
            }
            else if(choice == 0)
            {
                break;
            }


    } while(1);

    scanf("%c");
    return 0;
}