fibonacci using loops
/*
* Creator: Nighthawk Coding Society
* Mini Lab Name: fibonaccinacci 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 fibonacci {
String name; // name or title of method , no name is set
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
ArrayList<Long> list; // captures current fibonaccinacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
int first = 1;
int second = 1;
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public fibonacci() {
this(20); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonaccinacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public fibonacci(int nth) {
this.size = nth;
this.list = new ArrayList<>();
this.hashID = 0;
this.hash = new HashMap<>();
//initialize fibonaccinacci and time mvc
this.init();
}
/*
This Method should be "abstract"
*/
protected abstract void init();
/*
Number is added to fibonaccinacci sequence, current state of "list" is added to hash for hashID "num"
*/
public void setData(long num) { // the number in setdata is added here
list.add(num); // the number is added to the list
hash.put(this.hashID++, list.clone()); // the hash id is incremented and added as a key and list is added as a value in the hashmap
}
/*
Custom Getter to return last element in fibonaccinacci sequence
*/
public long getNth() {
return list.get(this.size - 1);
}
/*
Custom Getter to return last fibonaccinacci 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("fibonaccinacci Number " + this.size + " = " + this.getNth());
System.out.println("fibonaccinacci List = " + this.list);
System.out.println("fibonaccinacci Hashmap = " + this.hash);
for (int i=0 ; i<this.size; i++ ) {
System.out.println("fibonaccinacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
}
}
}
public class fibonacciFor extends fibonacci{
@Override
public void init() {
this.name = "For Loop"; // setting name
this.setData(0); // first item in the list
this.setData(first);
this.setData(second);
int loopSize = this.size - 3;
for(int i = 0;i<loopSize;i++) {
int next = second;
second = second + first;
first = next;
this.setData(second);
}
}
static public void main(String[] args) {
fibonacciFor fib = new fibonacciFor();
fib.print();
}
}
fibonacciFor.main(null);
public class whileloop extends fibonacci{
@Override
public void init() {
this.name = "While Loop";
this.setData(0);
this.setData(first);
this.setData(second);
int loopSize = this.size - 3;
int i = 0;
while(i < loopSize) {
int temp = second;
second = second + first;
first = temp;
this.setData(second);
i++;
}
}
static public void main(String[] args) {
whileloop fib = new whileloop();
fib.print();
}
}
whileloop.main(null);
public class fibonacciRecur extends fibonacci{
@Override
public void init() {
this.name = "Recursion";
for (int i=0; i<this.size; i++){
this.setData(recursiveFib(i));
}
}
// Recursion method
public int recursiveFib(int n) {
if (n == 0) {
return 0;
} else
if (n == 1) {
return this.first;
} else if (n == 2) {
return this.second;
}
return recursiveFib(n-2) + recursiveFib(n-1);
}
static public void main(String[] args) {
fibonacciRecur fib = new fibonacciRecur();
fib.print();
}
}
fibonacciRecur.main(null);
Collegeboard Standards
1.B
Implementing a while loop, for loop, and recursive function to accomplish fibonacci.
4.C
All 3 algorithms returned the same result through the printed output being the same.
5.A
For and while loops run in linear 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.