Fibonacci Algorithms
Returning Fibonacci Sequence in 4 ways.
- Base class for displaying sequence, contains Stream Algorithm
- Class with for loop
- Class with while loop
- Class with recursion
- CB Standards
/*
* 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();
// 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();
// FiboFor fibofor = new FiboFor();
// fibofor.print();
// FiboWhile fibowhile = new FiboWhile();
// fibowhile.print();
// FiboRecur fiborecur = new FiboRecur();
// fiborecur.print();
// }
}
public class FiboFor extends Fibo{
// Overriding the init method so that a different method can be used
// The printing and storing of data is preserved
@Override
public void init() {
this.name = "For Loop";
// Hardcoding first two numbers, and initializing them in the sequence
int first = 1;
int second = 1;
this.setData(0);
this.setData(first);
this.setData(second);
int loopSize = this.size - 2;
// Using a for loop to update the next term to be the sum of the previous two terms.
// Also need to update the second to last term to become what used to be the last term.
for(int i = 0;i<loopSize;i++) {
int temp = second;
second = second + first;
first = temp;
this.setData(second);
}
}
static public void main(String[] args) {
FiboFor fib = new FiboFor();
fib.print();
}
}
FiboFor.main(null);
public class FiboWhile extends Fibo{
// Overriding the init method so that a different method can be used
// The printing and storing of data is preserved
@Override
public void init() {
this.name = "While Loop";
// Hardcoding first two numbers, and initializing them in the sequence
int first = 1;
int second = 1;
this.setData(0);
this.setData(first);
this.setData(second);
int loopSize = this.size - 2;
// Using a while loop to update the next term to be the sum of the previous two terms.
// Also need to update the second to last term to become what used to be the last term.
int i = 0;
while(i < loopSize) {
int temp = second;
second = second + first;
first = temp;
this.setData(second);
i++;
}
}
static public void main(String[] args) {
FiboWhile fib = new FiboWhile();
fib.print();
}
}
FiboWhile.main(null);
public class FiboRecur extends Fibo{
// Overriding the init method so that a different method can be used
// The printing and storing of data is preserved
@Override
public void init() {
this.name = "Recursion";
// Iterating to show the entire sequence
for (int i=0; i<this.size; i++){
this.setData(Recur(i));
}
}
// Recursion method
public int Recur(int size) {
// Each term is the sum of the two terms before it
if (size > 2) {
// Each of these function calls again will start back at the if statement
// It only has actual numbers to return once the else if statements are reached
// EX, when it reaches size = 3, Recur(size-1) + Recur(size-2) = 1+1 = 2
return (Recur(size-1) + Recur(size-2));
}
else if (size == 2) {
return 1;
}
else if (size == 1) {
return 1;
}
else {
return 0;
}
}
static public void main(String[] args) {
FiboRecur fib = new FiboRecur();
fib.print();
}
}
FiboRecur.main(null);
CB Standards
1.B
Determined how to implement a while loop, for loop, and recursive function to accomplish fibonacci.
4.C
Determined if all 3 algorithms returned the same result through the printed output being the same.
5.A
For and while loops run in O(n) time since they run through the input size once and do a constant amount of operations for each loop. The recursive algorithm takes exponential time, however, since for each term of the sequence, the algorithm needs to recalculate all of the other terms as well due to the nature of recursion.