Created
October 15, 2017 16:52
-
-
Save shailrshah/3fb86aa5548932cd2da332d1ea6394ff to your computer and use it in GitHub Desktop.
Return the nth number in the Fibonacci Sequence
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.Map; | |
| import java.util.HashMap; | |
| class Fib { | |
| static long getFibIterative(int n) { | |
| if(n < 2) | |
| return n; | |
| long a = 0, b = 1, c = a + b; | |
| for(int i = 2; i <= n; c = a+b, a = b, b = c, i++); | |
| return c; | |
| } | |
| static long getFibRecursive(int n) { | |
| return n < 2 ? n : getFibRecursive(n-1) + getFibRecursive(n-2); | |
| } | |
| static Map<Integer, Long> map = new HashMap<>(); | |
| static long getFibRecursiveEnhanced(int n) { | |
| if(n < 2) | |
| return n; | |
| Long value = map.get(n); | |
| if(value == null){ | |
| long ans = getFibRecursiveEnhanced(n-1) + getFibRecursiveEnhanced(n-2); | |
| map.put(n, ans); | |
| value = ans; | |
| } | |
| return value; | |
| } | |
| public static void main(String[] args) { | |
| int n = Integer.parseInt(args[0]); | |
| for(int i = 0; i < n; i++) | |
| System.out.print(getFibIterative(i) + " "); | |
| // System.out.println(); | |
| // for(int i = 0; i < n; i++) | |
| // System.out.print(getFibRecursive(i) + " "); | |
| System.out.println(); | |
| for(int i = 0; i < n; i++) | |
| System.out.print(getFibRecursiveEnhanced(i) + " "); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment