fibonacci series

fibonacci series is defined as:

    f(n) = n for 0 <= n <= 1
    f(n) = f(n-1) + f(n-2)

=============
O(2^n) unusable. Inefficiency comes from that fact that same fibonacci
number needs to be calculated again and again. If you trace the algorithm
for n=4,5,6 etc. you would know how.

/*
    for(int i=0; i < 10; i++)
        System.out.println(fib1(i));
*/
int fib1(int n){
    if ( n <= 1 ){
        return n;
    } else {
        return fib1(n-1) + fib1(n-2);
    }
}

=============
storing series in an array and get previous values from array
/*
    int[] fn = fib3[10];
    for(int i=0; i < fn.length; i++)
        System..out.println(fn[i]);
*/

int[] fib3(int n){
    int[] ret = new int[n];
    for(int i=0; i < n; i++){
        if(i <= 1){
            ret[i] = i;
        } else {
            ret[i] = ret[i-1] + ret[i-2];
        }
    }
    return ret;
}


===============
actually we need to store only last 2 items from the series not all the
numebrs

void fib4(int n){
    int prev_2=0, prev_1=1; // n-2 and n-1
    for(int i=0; i < n; i++){
        if(i <= 1){
            System.out.println(i);
        } else {
            int x = prev_1 + prev_2; // n = (n-1) + (n-2)
            System.out.println(x);
            prev_2 = prev_1;    // n-2 = n-1
            prev_1 = x;         // n-1 = n     
        }
    }
}

=================
and some people might write like which is no very obvious and intuitive to
me, I prefer "fib4" function.

void fib2(int n){
    int f = 0;
    int g = 1;
    for(int i=0; i < n; i++){
        System.out.println(f);
        f = f + g;
        g = f - g;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s