Fibnoacci Mini Lab Hacks
Week 5
The Fibonacci algorithm can be coded many ways. This example shows Fibonacci implemented with the Streams interface.
/*
* 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);
Objective of Hacks is to produce the Fibonacci sequence in multiple ways. See this runtime. The method provided is Stream, the objective is to produce more familiar methods like ...
- For Loop
- While Loop
- Recursion
The trick is to produce all these methods without reproducing the same lines of code. Try to store and capture result data from parent class.
- Read the comments of the code in this Blog, as the code instructs you on what to abstract.
Abstraction
- Abstraction is hiding certain info and only show what is necessary to the user
- An
abstractclass can't be used to make object directly, another class needs to inherit the parent class in order to access the abstract class - An
abstractmethod can only be used in an abstract class and the body of the method is given by the child class
abstract class Fruit {
public abstract void fruitColor();
}
// This code will not work since Fruit is an abstract class
Fruit apple = new Fruit();
//Apple class inherits the abstract class Fruit
class Apple extends Fruit {
public void fruitColor() {
System.out.println("I am a red fruit");
}
}
// This code will work
Apple crunchyApple = new Apple();
crunchyApple.fruitColor();
public int add(int myNum) {
if (myNum > 0) {
return myNum + add(myNum - 1);
} else {
return 0;
}
}
int result = add(15);
// 15 > 0 --> return 15 + add(14) --> return 15 + (14 + add(13)) --> and
// so on until return 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
System.out.println(result);
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
// changed to an abstract class Fibo
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("Starting program...");
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) {
ForLoop forLoop = new ForLoop();
forLoop.print();
}
}
public class ForLoop extends Fibo {
protected void init() {
super.name = "For Loop";
System.out.println("for loop");
int fibNum1 = 0;
int fibNum2 = 1;
int fibNum;
for (int i = 0; i <= super.size; i++) {
super.setData(fibNum1);
fibNum = fibNum1 + fibNum2;
fibNum1 = fibNum2;
fibNum2 = fibNum;
}
}
}
Fibo.main(null);
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
// changed to an abstract class Fibo
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("Starting program...");
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) {
WhileLoop WhileLoop = new WhileLoop();
WhileLoop.print();
}
}
public class WhileLoop extends Fibo {
protected void init() {
super.name = "While Loop";
System.out.println("while loop");
int fibNum1 = 0;
int fibNum2 = 1;
int fibNum;
int i = 0;
while (i <= super.size) {
super.setData(fibNum1);
fibNum = fibNum1 + fibNum2;
fibNum1 = fibNum2;
fibNum2 = fibNum;
i++;
}
}
}
Fibo.main(null);
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
// changed to an abstract class Fibo
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("Starting program...");
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) {
Recursion recursion = new Recursion();
recursion.print();
}
}
public class Recursion extends Fibo {
public int fibIt (int i) {
if (i <= 1) {
return i;
}
else {
return fibIt(i-1) + fibIt(i-2);
}
}
protected void init() {
super.name = "Recursion";
//System.out.println("Recursion");
for (int i = 0; i <= super.size; i++) {
super.setData(fibIt(i));
}
}
}
Fibo.main(null);
In Blog or code, comment on how this assignment fulfills the following standards from College Board.
- Skill 1.B:Determine code that would be used to complete code segments (ie For, While, Recursion) - I worked on accomplishing the same goal of creating a fibonacci sequence but through different methods (for, while, recursion)
- Skill 4.C: Determine if two or more code segments yield equivalent results (be sure to Discuss how you know results are the same)
- Again I worked on get the same output but in different ways to output a fibonacci sequence. I can compare the final sequence output for the three programs and see if they are the same.
- 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 loop
- ForLoop child class extends abstract Fibo class
- Loops through the size/how many numbers in the fibonacci sequence (default 20)
- starts with adding 0 and 1 and then add the current and previous term
- While Loop
- WhileLoop child class extends abstract Fibo class
- While the the term is less than the size, start with 0 and 1, and then keep adding the previous term with the current term
- Recursion
- Recursion child class extends abstract Fibo class
- created a fibIt function that calls itself
- For loop