/*
* 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 */
abstract 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 abstract 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 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));
}
System.out.println();
}
}
public class FibF extends Fibo {
public void init() {
super.name = "For";
int count = super.size;
long[] previous = new long[] {0, 1};
for (int i = 0; i < count; i++) {
super.setData(previous[0]);
previous = new long[] {previous[1], previous[0] + previous[1]};
}
}
static public void main(String[] args) {
long start = System.nanoTime();
FibF fibF = new FibF();
long end = System.nanoTime();
fibF.print();
System.out.println("Time: " + (end-start) + " ns");
}
}
FibF.main(null);
public class FibW extends Fibo {
public void init() {
super.name = "While";
int count = 0;
long[] previous = new long[] {0, 1};
while (count < super.size) {
super.setData(previous[0]);
previous = new long[] {previous[1], previous[0] + previous[1]};
count++;
}
}
static public void main(String[] args) {
long start = System.nanoTime();
FibW fibW = new FibW();
long end = System.nanoTime();
fibW.print();
System.out.println("Time: " + (end-start) + " ns");
}
}
FibW.main(null);
public class FibR extends Fibo {
public void init() {
super.name = "While";
long[] previous = new long[] {0, 1};
System.out.print(previous);
this.init(0, previous);
}
public void init(int count, long[] past) {
if (count < super.size) {
super.setData(past[0]);
past = new long[] {past[1], past[0] + past[1]};
count++;
this.init(count);
}
}
static public void main(String[] args) {
long start = System.nanoTime();
FibR fibR = new FibR();
long end = System.nanoTime();
fibR.print();
System.out.println("Time: " + (end-start) + " ns");
}
}
FibR.main(null);
CollegeBoard Standards
Skill 1.B: Determine code that would be used to complete code segments (ie For, While, Recursion) We used for, while, and recursion in init() of the subclasses to create the Fibonacci sequence.
Skill 4.C: Determine if two or more code segments yield equivalent results (be sure to Discuss how you know results are the same) If both the for and while loop starts at the same number and add 1 until it reaches the same conditional, and the same code block is ran every time, we can determine that the two or more code segments yield equivalent results. In our for loop, we defined i with the same number as count in while, 0. The conditional for both was run when the the index is less than the size. They both also increased by 1 every time the code is ran. The recursive also starts at the same index and increments by 1 every time it is recalled at the end of the code. The overall code in the function also has an if statement that is the same conditional as the for and while loops.
Skill 5.A: Describe the behavior of a given segment of program code (describe the difference in recursion versus for & while loops, perhaps add timing to determine speed) For and while loops repeat the same code block until a condition is evaluated to false. In recursion, the function is recalling itself within its code repeatedly and not just repeating from start to end. For example, in the fist call, the code is ran and when it reaches to the point where it recalls itself, the function calls itself and runs the same code again and calls itself when it reaches the same point, etc.