Created
August 9, 2017 15:43
-
-
Save sdpatil/37e9f026e9e46a6e2cae9fd403db2089 to your computer and use it in GitHub Desktop.
Calculate fibonacci sequence number for given number n
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.HashMap; | |
| import java.util.Map; | |
| /** | |
| * Problem: Calculate fibonacci sequence number for given number n | |
| * Ex. Fibonacci series generates numbers in the form n-1 + n-2 | |
| * 0 1 1 2 3 5 8 13 21 34 | |
| */ | |
| public class Fibonacci { | |
| private Map<Integer, Integer> cache = new HashMap<Integer, Integer>(); | |
| //Basic brute force recursion | |
| public int fibonacciRecursive(int n){ | |
| if(n <= 1) | |
| return n; | |
| else | |
| return fibonacciNonRecursive(n-1) + fibonacci(n-2); | |
| } | |
| //This is memorized version | |
| public int fibonacci(int n) { | |
| if (n <= 1) | |
| return n; | |
| else if (!cache.containsKey(n)) { | |
| cache.put(n, fibonacci(n - 1) + fibonacci(n - 2)); | |
| } | |
| return cache.get(n); | |
| } | |
| //This is DP solution for fibonacci number | |
| public int fibonacciNonRecursive(int n) { | |
| if (n <= 1) | |
| return n; | |
| int fMinus2 = 0; | |
| int fMinus1 = 1; | |
| int nextNumber = 0; | |
| for (int i = 2; i <= n; i++) { | |
| nextNumber = fMinus2 + fMinus1; | |
| fMinus2 = fMinus1; | |
| fMinus1 = nextNumber; | |
| } | |
| return nextNumber; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment