Fibonacci Classes
Collegeboard learnings
/*
* 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;
/* Objective will require changing to abstract class with one or more abstract methods below */
public class Fibo {
String name; // name or title of method
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
ArrayList<Long> list; // captures current Fibonacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public Fibo() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
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.hash = new HashMap<>();
//initialize fibonacci and time mvc
this.init();
}
/*
This Method should be "abstract"
Leave method as protected, as it is only authorized to extender of the class
Make new class that extends and defines init()
Inside references within this class would change from this to super
Repeat process using for, while, recursion
*/
protected void init() {
this.name = "Stream";
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
.limit(this.size)
.forEach(f -> this.setData(f[0]) );
}
/*
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 last fibonacci sequence in HashMap
*/
public Object getNthSeq(int i) {
return hash.get(i);
}
/*
Console/Terminal supported print method
*/
public void print() {
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);
for (int i=0 ; i<this.size; i++ ) {
System.out.println("fibonacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
}
}
/*
Tester class method. If this becomes abstract you will not be able to test it directly ...
Change this method to call "main" class of each of the extended classes
*/
static public void main(String[] args) {
Fibo fib = new Fibo();
fib.print();
}
}
Fibo.main(null);
public class FiboFor extends Fibo {
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public FiboFor() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public FiboFor(int nth) {
this.size = nth;
this.list = new ArrayList<>();
//initialize fibonacci and time mvc
this.init();
}
protected void init(){
this.name = "For";
this.setData(0);
this.setData(1);
// 1b. for each index up to the desired index, calculate and set the data and move to the next index
// 4c. both the for loop and while loop end up looping over the same numbers and perform the same action, so the result is expected to be the same
// 5a. recursion recalculates each of the previous indexes each time it runs, while the for loop and while loop calculate every index only once.
for(int iter = 2; iter < this.size; iter++){
this.setData(this.list.get(iter-2)+this.list.get(iter-1));
}
}
static public void main(String[] args) {
FiboFor fib = new FiboFor(5);
fib.print();
}
}
FiboFor.main(null);
public class FiboWhile extends Fibo {
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public FiboWhile() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public FiboWhile(int nth) {
this.size = nth;
this.list = new ArrayList<>();
//initialize fibonacci and time mvc
this.init();
}
protected void init(){
this.name = "While";
this.setData(0);
this.setData(1);
int iter = 2;
// 1b. while the index is less than the desired index, calculate and set the data and move to the next index
// 4c. both the for loop and while loop end up looping over the same numbers and perform the same action, so the result is expected to be the same
while(iter < this.size){
this.setData(this.list.get(iter-2)+this.list.get(iter-1));
iter++;
}
}
static public void main(String[] args) {
FiboWhile fib = new FiboWhile();
fib.print();
}
}
FiboWhile.main(null);
public class FiboRecursion extends Fibo {
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public FiboRecursion() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public FiboRecursion(int nth) {
this.size = nth;
this.list = new ArrayList<>();
//initialize fibonacci and time mvc
this.init();
}
protected void init(){
this.name = "Recursion";
for(int index = 0; index < this.size; index++){
this.setData(this.calc(index));
}
}
// 1b. Calculate the result based on the previous two indexes starting with 0 and 1 at the bottom
public int calc(int index) {
if (index < 2) {
return index;
}
return this.calc(index-2) + this.calc(index-1);
}
static public void main(String[] args) {
FiboRecursion fib = new FiboRecursion();
fib.print();
}
}
FiboRecursion.main(null);
Hacks
- Skill 1.B: Used different types of loops or methods of program for each situation
I did a for loop, while loops, and recursion method to show different situations with Fibonacci Calculations.
- Skill 4.C: Code segments produce same results because the output is printed in the same format, the only thing changing is the type of loop. Key Finding: Different Loops can produce same output as long as the loops have the same purpose- in this case with for and while loops
All the methods produce the same output.
Skill 5.A: Recursion runs the fastest since it's not a loop, but all methods work equally well. It's important to know how to recreate a program in different ways.
We recreated the fibonacci program in different ways that all work successfully. Recursion is the slowest while the for and while loops are the fastest.