Skip to content

Instantly share code, notes, and snippets.

@bytecodeman bytecodeman/FibMain.java Secret
Created Nov 7, 2019

Embed
What would you like to do?
Fibonacci with Memoization
/*
* Name: Prof. Antonio C. Silvestri (STCC)
* Date: 11/05/2019
* Course Number: CSC-220
* Course Name: Data Structures and Algorithms
* Problem Number: NAH
* Email: silvestri@stcc.edu
* Description: Fibonacci Application
*/
import java.util.InputMismatchException;
import java.util.Scanner;
public class FibMain {
private static final String TITLE = "Fibonacci Application V1.0";
private static final String CONTINUE_PROMPT = "Do this again? [y/N] ";
// **********************************************
private static int getNumber(Scanner sc) {
do {
try {
System.out.print("Enter Number: ");
return sc.nextInt();
} catch (InputMismatchException ex) {
System.out.println("Number must be an integer!");
} finally {
sc.nextLine();
}
} while (true);
}
// **********************************************
private static void process(Scanner sc, String args[]) {
try {
int n = getNumber(sc);
int ans = Fibonacci1.fib(n);
System.out.println("Ans = " + ans);
}
catch (RuntimeException ex) {
System.out.println("Fibonacci Exception: " + ex.getMessage());
}
}
// **********************************************
private static boolean doThisAgain(Scanner sc, String prompt) {
System.out.print(prompt);
String doOver = sc.nextLine();
return doOver.equalsIgnoreCase("Y");
}
// **********************************************
public static void main(String args[]) {
System.out.println("Welcome to " + TITLE);
Scanner sc = new Scanner(System.in);
do {
process(sc, args);
} while (doThisAgain(sc, CONTINUE_PROMPT));
sc.close();
System.out.println("Thank you for using " + TITLE);
}
}
import java.util.ArrayList;
import java.util.Collections;
public class Fibonacci1 {
private static int fib(int n, ArrayList<Integer> fibList) {
if (n == 0)
return 0;
if (n == 1)
return 1;
if (fibList.get(n) == 0)
fibList.set(n, fib(n-1, fibList) + fib(n-2, fibList));
return fibList.get(n);
}
public static int fib(int n) {
final int MAX_FIB = 60;
final ArrayList<Integer> fibList = new ArrayList<>(Collections.nCopies(MAX_FIB, 0));
if (n > fibList.size())
throw new RuntimeException("n must be <= 60");
return fib(n, fibList);
}
}
import java.util.ArrayList;
import java.util.Collections;
public class Fibonacci2 {
private final static ArrayList<Integer> fibList = new ArrayList<Integer>(Collections.nCopies(60, 0));
private static int fibHelper(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
if (fibList.get(n) == 0)
fibList.set(n, fibHelper(n-1) + fibHelper(n-2));
return fibList.get(n);
}
public static int fib(int n) {
if (n > fibList.size())
throw new RuntimeException("n must be <= 60");
return fibHelper(n);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.