Wikipedia says:

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.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.

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]; } }

One more,

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

Thanks, Dhaval!

Deletehttp://bit.ly/1bO4mjF