google-code-prettify

Thursday, 24 January 2013

Fibonacci numbers - 4 solutions

Find the n-th Fibonacci number. The Fibonacci numbers are integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Wikipedia says:
By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two. 
For example the 7-th Fibonacci number in the sequence is 8. Here are a few solutions. The first one is a trivial one and follows the definition - i.e. it uses recursion.

long fibonacciRecursive(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}


The second solution is iterative. A drawback here is that the size of the array which is used to store the Fibonacci numbers needs to be defined statically.

long fibonacciIterative(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size + 1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
  
    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i] = fibonacciNumbers[i - 1]
                            + fibonacciNumbers[i - 2];
    }
    return fibonacciNumbers[n];
}


The third solution is again iterative. The difference here is that it uses an array with size 3. This is a very elegant and optimized solution.

long fibonacciIterativeLowMem(int n) {
    int[] fibonacciNumbers = new int[3];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i % 3] = fibonacciNumbers[(i - 1) % 3]
                                + fibonacciNumbers[(i - 2) % 3];
    }
    return fibonacciNumbers[n % 3];
}


Here is one more solution that uses an optimization called memoization. The idea here is that we avoid the calculation of the tasks we already had calculated.
long fibonacciMemoization(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size+1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
    for (int i = 2; i < size; i++) {
        fibonacciNumbers[i] = -1;
    }
  
    if (fibonacciNumbers[n] != -1) {
        return fibonacciNumbers[n];
    } else {
        fibonacciNumbers[n] = fibonacciMemoization(n - 1)
                            + fibonacciMemoization(n - 2);
        return fibonacciNumbers[n];
    }
}

3 comments:

  1. One more,

    Using matrix multiplication. You can find nth fibonacci number in O(log n) time.

    ReplyDelete
  2. Our IBM AppScan certified expert consultant will teach on real-time scenario-based case study and can provide study material and ppt. We will help you to clear IBM AppScan training certification by providing you with proper guidance. For more details kindly contact us. IBM AppScan Training

    ReplyDelete