Fibonacci
Fibonacci
For loop
I first created an array that contained two elements. Within the for loop, the first element of the array is added to the list of numbers through the setData method. Next, I changed the first element of the array into the second element, and the second into the sum of the first and second element, and allowed the for lop to repeat.
/*
* 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));
}
}
/*
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
*/
}
public class FiboExtended extends Fibo {
public FiboExtended() {
super();
}
protected void init(){
super.name = "for loop";
long[] nums = new long[]{0, 1};
for (int i = 0; i < super.size; i++) {
super.setData(nums[0]);
long index1 = nums[0];
long index2 = nums[1];
nums[0] = index2;
nums[1] = index1 + index2;
}
}
static public void main(String[] args) {
long startTime = System.nanoTime();
FiboExtended fib = new FiboExtended();
fib.print();
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Time to run code: " + duration/1000000 + " milliseconds");
}
}
FiboExtended.main(null);
public class FiboExtended extends Fibo {
public FiboExtended() {
super();
}
protected void init(){
super.name = "while loop";
long[] nums = new long[]{0, 1};
int i = 0;
while (i < super.size) {
super.setData(nums[0]);
long index1 = nums[0];
long index2 = nums[1];
nums[0] = index2;
nums[1] = index1 + index2;
i++;
}
}
static public void main(String[] args) {
long startTime = System.nanoTime();
FiboExtended fib = new FiboExtended();
fib.print();
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Time to run code: " + duration/1000000 + " milliseconds");
}
}
FiboExtended.main(null);
public class FiboExtended extends Fibo {
public FiboExtended() {
super();
}
protected void init() {
super.name = "recursion";
long[] nums = new long[]{0, 1};
test(0, nums);
}
public void test(int i, long[] array) {
long[] nums = array.clone();
if (i < super.size) {
super.setData(nums[0]);
long index1 = nums[0];
long index2 = nums[1];
nums[0] = index2;
nums[1] = index1 + index2;
i++;
test(i, nums);
}
}
static public void main(String[] args) {
long startTime = System.nanoTime();
FiboExtended fib = new FiboExtended();
fib.print();
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Time to run code: " + duration/1000000 + " milliseconds");
}
}
FiboExtended.main(null);
Skills
-
Skill 1.B: Determine code that would be used to complete code segments: (Explained in each type of code above)
-
Skill 4.C: Determine if two or more code segments yield equivalent results
It's pretty simple to see how the for loop and while loop achieve the same results. In the for loop, each line of code is implemented, and after the program reaches the end of the loop, the loop is repeated (with
iincrementing by 1), until i = 20 (the value ofsize).The recursion is a little bit more complicated. First, the recursive loop is called within the
initmethod, and then proceeds to run through the code. At the end of the code,iis incremented by 1, and the last line of code,recursiveLoop(i)tells the program to run the recursive loop again, repeating until i = 20.tldr; As a result, all three methods achieve the same result in that the code within the loop is ran,
iincreases by 1, which causes the loop to run again until i = 20. -
Skill 5.A: Describe the behavior of a given segment of program code: (Explained in each type of code above)
Timing: Using
system.nanoTime(), it seems as if the for loop runs the fastest, followed by recursion, and lastly the while loop.
From the example of Fibo using stream.
this(): Calls constructor with the same name in the current class
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]}):
-
new long[]{0, 1}: Creates an array, becomes the seed for theStream.iteratemethod -
f -> new long[]{f[1], f[0] + f[1]}: Lambda expression, passing in the parameter offinto the functionnew long[]{f[1], f[0] + f[1]}
.limit(this.size): Set a limit (in this case, 20), to the number of times the stream iterates
.forEach(f -> this.setData(f[0]));: For each item, run the setData() method
Hashmap: Unlike an array that is accessed through an index, a hashmap uses key/value pairs. As a result, the index of a hashmap can be an string, whereas the index of an array is an integer.
An explanation of the Fibo code using streams.
Looking at the code was pretty challenging, but after searching up each unfamiliar piece of code, I had a general idea of what the program does.
I will explain below what the code does so that it can further my understanding of Java.
By creating the fib object, the Fibo() constructor is ran. this(20); points to the Fibo(int nth) constructor. The code within the constructor is ran, mainly use to assign variables to various values. Next, the init() method is ran. An array is created within the stream. The stream will iterate 20 times, as determined with .limit(this.size). Next, for each item (the element in the array), the setData method will run with f[0] as an argument. When the stream iterates again, the array will change it's first element to the second element, and its second element to the sum of the first and second element. Now onto running the setData(long num) method. First, the element of f[0] will be added to the already created list. Next, a hashmap will be created, with a key with the index number, and a value with a duplicate of the list (list.clone();). Going back to the main method, fib.print(); runs the print() method. I'll skip the basic calling the variable stuff and proceed to the second System.out.println, in which the getNth() method is ran. Here, the last element of the list (and you have to access the last element with this.size - 1 because there are 20 elements in the array, so the 20th element is accessed using the 19th index since indexes start at 0) is obtained to print the 20th Fibonacci number. Next, the entire Fibonacci array and hashmap is printed. Finally, the for loop outputs each of the values for the specified key. The Fibonacci sequence for each number is printed successfully because each key is associated with a list, which contains the Fibonacci sequence for the sequence number.