Fibonacci Sequence
/*
* 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 {
public FiboFor() {
this(20); // telescope to avoid code duplication, using default as 20
}
public FiboFor(int nth) {
super(nth);
}
@Override
protected void init() {
this.name = "FOR LOOP";
long f[] = new long[] { 0, 1 };
for (int i = 0; i < size; i++) {
long n = f[0];
this.setData(f[0]);
f[0] = f[1];
f[1] = n + f[1];
}
}
static public void main(String[] args) {
FiboFor fib = new FiboFor();
fib.print();
}
}
FiboFor.main(null);
public class FiboWhile extends Fibo {
public FiboWhile() {
this(20); // telescope to avoid code duplication, using default as 20
}
public FiboWhile(int nth) {
super(nth);
}
@Override
protected void init() {
this.name = "WHILE LOOP";
long f[] = new long[] { 0, 1 };
Integer i = 0;
while (i < size) {
long n = f[0];
this.setData(f[0]);
f[0] = f[1];
f[1] = n + f[1];
i = i+1;
}
}
static public void main(String[] args) {
FiboWhile fib = new FiboWhile();
fib.print();
}
}
FiboWhile.main(null);
public class FiboRec extends Fibo {
public FiboRec() {
this(20); // telescope to avoid code duplication, using default as 20
this.name = "RECURSIVE LOOP";
}
public FiboRec(int nth) {
super(nth);
}
private long my_fib_rec(long n){
if (n<=1){
return n;
}
return my_fib_rec(n-1) + my_fib_rec(n-2);
}
@Override
protected void init() {
this.name = "RECURSIVE LOOP";
for (int i = 0; i < size; i++) {
this.setData(my_fib_rec(i));
}
}
static public void main(String[] args) {
FiboRec fib = new FiboRec();
fib.print();
}
}
FiboRec.main(null);
//for i is less than 9, make it so that the next term is the sum of i and i-1
public static void fib_for(){
ArrayList<Integer> fib = new ArrayList<Integer>(10);
fib.add(0);
System.out.println(fib);
fib.add(1);
System.out.println(fib);
for (int i = 1; i<= 9; i++){
Integer new_elem = fib.get(i) + fib.get(i-1);
fib.add(new_elem);
System.out.println(fib);
}
}
//making it with a while loop is essentially the same thing as making it with a for loop.
//below is a demonstration
public static void fib_while(){
Integer i = 1;
ArrayList<Integer> fib_while = new ArrayList<Integer>(10);
fib_while.add(0);
System.out.println(fib_while);
fib_while.add(1);
System.out.println(fib_while);
while (i<10){
Integer new_elem = fib_while.get(i) + fib_while.get(i-1);
fib_while.add(new_elem);
System.out.println(fib_while);
i = i+1;
}
}
public static long fib_rec(int n){
if (n<=1){
return n;
}
return fib_rec(n-1)+fib_rec(n-2);
}
System.out.println("STARTING THE FIB SEQUENCE WITH FOR LOOP: ");
Fibo.fib_for();
System.out.println("STARTING THE FIB SEQUENCE WITH WHILE LOOP: ");
Fibo.fib_while();
System.out.println("STARTING THE FIB SEQUENCE WITH RECURSION: ");
Fibo.fib_rec(10);
Explanation of Code
The Fibonacci series is a series where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1.
Fibonacci Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
For Loop: Each time, i is increased by one, and is added to the previous 2 terms While loop: the exact same logic as for loop, just executed differently. These two code segements yield the same result.
Recursion: the method fib_rec takes in an integer. Then, when you invoke it, it will find the sum of fib_rec(n-1) and fib_rec(n-2). An important thing here, is that the function is calling itself. That is why is it called recursion.
Basic Logic: we first create an array with just 0 and 1 in it. Then, we set n equal to f[0]. Then, we call setData and input that method with f[0]. In setData, the f[0] term is added to the main fibonacci list, and that list is cloned (as well as associated to a number, creating a hashmap.) Then, the f[0] is set to f[1]. The new f[1] is equal to n (the index of the 0th term) plus the actual 0th term.
long n = f[0]; this.setData(f[0]); f[0] = f[1]; f[1] = n + f[1];