Fibonacci
This shows mutliple ways of doing fibonacci using inheritance
/*
* Creator: Nighthawk Coding Society
* Mini Lab Name: Fibonacci sequence, featuring a Stream Algorithm
*
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
abstract class Fibo {
String name; // name or title of method
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
long time; // stores the time it takes for code to run
ArrayList<Long> list; // captures current Fibonacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
/*
Default Fibo does 30 numbers
@param: none
*/
public Fibo() {
this(30); // telescope to avoid code duplication, using default as 30
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public Fibo(int nth) {
this.size = nth;
this.list = new ArrayList<>();
this.hashID = 0;
this.time = 0;
this.hash = new HashMap<>();
//initialize fibonacci and time mvc
this.init();
}
/*
Abstract method for how fibo is calculated
*/
abstract protected void init();
/*
Number is added to fibonacci sequence, current state of "list" is added to hash for hashID "num"
*/
public void setData(long num) {
list.add(num);
hash.put(this.hashID++, list.clone());
}
/*
Custom Getter to return last element in fibonacci sequence
*/
public long getNth() {
return list.get(this.size - 1);
}
/*
Custom Getter to return an element of fibonacci sequence in HashMap
*/
public Object getNthSeq(int i) {
return hash.get(i);
}
/*
Console/Terminal supported print method
*/
public void print() {
System.out.println("Time (ms) = " + this.time);
System.out.println("Init method = " + this.name);
System.out.println("fibonacci Number " + this.size + " = " + this.getNth());
System.out.println("fibonacci List = " + this.list);
System.out.println("fibonacci Hashmap = " + this.hash);
System.out.println("fibonacci Sequence " + (this.size) + " = " + this.getNthSeq(this.size-1));
}
}
public class ForFibo extends Fibo {
@Override
protected void init () {
long startTime = System.currentTimeMillis();
this.name = "for";
long[] fibo = new long[this.size];
fibo[0] = 0;
fibo[1] = 1;
this.setData(fibo[0]);
this.setData(fibo[1]);
for (int i = 2; i<this.size; i++) {
fibo[i] = fibo[i-1] + fibo[i-2];
this.setData(fibo[i]);
}
this.time = System.currentTimeMillis() - startTime;
}
public static void main (String[] args) {
ForFibo forFib = new ForFibo();
forFib.print();
}
}
ForFibo.main(null);
public class WhileFibo extends Fibo {
@Override
protected void init () {
long startTime = System.currentTimeMillis();
this.name = "while";
long fib1 = 1;
long fib2 = 0;
this.setData(fib2);
this.setData(fib1);
int idx = 2;
while (idx < this.size) {
this.setData(fib1 + fib2);
long oldFib1 = fib1;
fib1 += fib2;
fib2 = oldFib1;
idx++;
}
this.time = System.currentTimeMillis() - startTime;
}
public static void main (String[] args) {
WhileFibo whileFib = new WhileFibo();
whileFib.print();
}
}
WhileFibo.main(null);
public class RecurseFibo extends Fibo {
private long calculateFibo (int num) {
if (num == 0) {
return 0;
}
if (num == 1) {
return 1;
}
return calculateFibo(num-1) + calculateFibo(num-2);
}
@Override
protected void init () {
long startTime = System.currentTimeMillis();
this.name = "recursive";
for (int i = 0; i<this.size; i++) {
this.setData(calculateFibo(i));
}
this.time = System.currentTimeMillis() - startTime;
}
public static void main (String[] args) {
RecurseFibo recurseFib = new RecurseFibo();
recurseFib.print();
}
}
RecurseFibo.main(null);
Dynamic Programming
This class extends the Fibo class and therefore inherits methods and properties from Fibo class. Uses recursion with dynamic programming to calculate the Fibonacci sequence. As the recursion redoes a lot of the calculations, a dynamic programming solution can be used to give it better speed (as seen by time being 25ms compared to other solutions at ~0ms).
public class DynamicFibo extends Fibo {
private long[] cache;
private long calculateFibo (int num) {
if (num == 0) {
return 0;
}
if (this.cache[num] != 0) {
return this.cache[num];
}
this.cache[num] = calculateFibo(num-1) + calculateFibo(num-2);
return this.cache[num];
}
@Override
protected void init () {
this.cache = new long[this.size];
this.cache[1] = 1;
long startTime = System.currentTimeMillis();
this.name = "dynamic";
this.calculateFibo(this.size-1);
// use generated cache to set data
for (int i = 0; i<this.size; i++) {
this.setData(this.cache[i]);
}
this.time = System.currentTimeMillis() - startTime;
}
public static void main (String[] args) {
DynamicFibo dynamicFib = new DynamicFibo();
dynamicFib.print();
}
}
DynamicFibo.main(null);
For Skill 1.B, in all the examples I filled out different types of statements such as for, while, recusion, and even dynamic programming.
Addressing CollegeBoard Skill 4.C, we know results are the same because the algorithms perform the same oeprations and alwso the output from our print functions in all 3 methods is the same.
For Skill Skill 5.A, I've added timers to each method where we can see recursion is the slowest because it has to recalculate a lot of value while the caching used in the for/while loops is faster. We can also see in the dynamic programming example the recursive solution can become much faster.