Name it \"Assignment_4_1\". Write the Java source code necessary to build a solu
ID: 3795703 • Letter: N
Question
Name it "Assignment_4_1".
Write the Java source code necessary to build a solution for the problem below:
The Fibonacci numbers form a sequence where each number is the sum of the previous two numbers. Starting from 0 and 1, the first eight Fibonacci numbers are built in the following list using the equation F n = F n-1 + F n-2:
0, 0
0, 1
1, 1
1, 2
2, 3
3, 5
5, 8
8, 13
The sequence would be the numbers in red (0, 1, 1, 2, 3, 5, 8, 13).
Using the linked list (MyLinkedList) created in Assignment 3.1, create a stack class and a test program to display the first 50 Fibonacci numbers in descending order. Use a stack to store these numbers. Once 50 numbers have been computed, print the numbers in a descending order. You will note that this process is naturally recursive. Therefore, use recursion to find this series of Fibonacci numbers.
Here is the MyLinkedList class:
public class MyLinkedList<T> {
class Node<T> {
T data;
Node<T> next;
Node<T> prev;
Node () {
data = null;
next = null;
prev = null;
}
}
private Node<T> head;
private Node<T> tail;
private int size;
public MyLinkedList () {
head = null;
tail = null;
size = 0;
}
public void addHead (T data) {
if (head == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = head;
head = new Node<T>();
head.data = data;
head.next = tmp;
tmp.prev = head;
head.prev = null;
}
size++;
}
public void addTail (T data) {
if (tail == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = tail;
tail = new Node<T>();
tail.data = data;
tmp.next = tail;
tail.prev = tmp;
tail.next = null;
}
size++;
}
public void addMiddle (T data) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
Node<T> n = new Node<T>();
n.data = data;
prev.next = n;
n.prev = prev;
n.next = cur;
cur.prev = n;
size++;
}
public void removeHead () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
head = head.next;
head.prev = null;
size--;
}
}
public void removeMiddle () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size == 2) {
head = tail; // head removed and updated accordingly
head.prev = null;
size--;
} else if (size > 2) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
prev.next = cur.next;
cur.next.prev = prev;
cur.next = null;
cur.prev = null;
size--;
}
}
public void removeTail () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
tail = tail.prev;
tail.next = null;
size--;
}
}
public boolean search (T data) {
Node<T> n = head;
while (n != null) {
if (n.data.equals(data))
return true;
n = n.next;
}
return false;
}
public int getSize () {
return size;
}
@Override
public String toString () {
String str = "";
Node<T> s = head;
while (s != null) {
str += s.data + " ";
s = s.next;
}
return str;
}
}
Step 1 Create a new project.
Name it "Assignment_4_1".
Step 2 Build a solution.
Write the Java source code necessary to build a solution for the problem below:
The Fibonacci numbers form a sequence where each number is the sum of the previous two numbers. Starting from 0 and 1, the first eight Fibonacci numbers are built in the following list using the equation F n = F n-1 + F n-2:
0, 0
0, 1
1, 1
1, 2
2, 3
3, 5
5, 8
8, 13
The sequence would be the numbers in red (0, 1, 1, 2, 3, 5, 8, 13).
Using the linked list (MyLinkedList) created in Assignment 3.1, create a stack class and a test program to display the first 50 Fibonacci numbers in descending order. Use a stack to store these numbers. Once 50 numbers have been computed, print the numbers in a descending order. You will note that this process is naturally recursive. Therefore, use recursion to find this series of Fibonacci numbers.
Here is the MyLinkedList class:
public class MyLinkedList<T> {
class Node<T> {
T data;
Node<T> next;
Node<T> prev;
Node () {
data = null;
next = null;
prev = null;
}
}
private Node<T> head;
private Node<T> tail;
private int size;
public MyLinkedList () {
head = null;
tail = null;
size = 0;
}
public void addHead (T data) {
if (head == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = head;
head = new Node<T>();
head.data = data;
head.next = tmp;
tmp.prev = head;
head.prev = null;
}
size++;
}
public void addTail (T data) {
if (tail == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = tail;
tail = new Node<T>();
tail.data = data;
tmp.next = tail;
tail.prev = tmp;
tail.next = null;
}
size++;
}
public void addMiddle (T data) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
Node<T> n = new Node<T>();
n.data = data;
prev.next = n;
n.prev = prev;
n.next = cur;
cur.prev = n;
size++;
}
public void removeHead () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
head = head.next;
head.prev = null;
size--;
}
}
public void removeMiddle () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size == 2) {
head = tail; // head removed and updated accordingly
head.prev = null;
size--;
} else if (size > 2) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
prev.next = cur.next;
cur.next.prev = prev;
cur.next = null;
cur.prev = null;
size--;
}
}
public void removeTail () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
tail = tail.prev;
tail.next = null;
size--;
}
}
public boolean search (T data) {
Node<T> n = head;
while (n != null) {
if (n.data.equals(data))
return true;
n = n.next;
}
return false;
}
public int getSize () {
return size;
}
@Override
public String toString () {
String str = "";
Node<T> s = head;
while (s != null) {
str += s.data + " ";
s = s.next;
}
return str;
}
}
Explanation / Answer
class Test{
public static void main(String[] args){
Fibonacci fib = new Fibonacci();
fib.generate(50);
System.out.println(fib);
}
}
class Fibonacci{
MyStack stack = null;
public Fibonacci(){
stack = new MyStack();
}
public void generate(long n0,long n1, int limit){ //limit >=2
if(stack.size()<2){
stack.push(n0);
stack.push(n1);
}
if(stack.size()<limit){
long next_n = n0+n1;
stack.push(next_n);
n0=n1;
n1=next_n;
generate(n0,n1,limit);
}
}
public String toString(){
return stack.toString();
}
}
class MyStack{
MyLinkedList<Long> stack;
public MyStack(){
stack = new MyLinkedList<Long>();
}
public void push(Long data){
stack.addHead(data);
}
public Long pop(){
Long item=null;
if(stack.getSize()>0){
item = (long)stack.getHead();
stack.removeHead();
}
return item;
}
public Long peek(){
Long item=null;
if(stack.getSize()>0){
item = (long)stack.getHead();
}
return item;
}
public int size(){
return stack.getSize();
}
@Override
public String toString(){
return stack.toString();
}
}
class MyLinkedList<T> {
class Node<T> {
T data;
Node<T> next;
Node<T> prev;
Node () {
data = null;
next = null;
prev = null;
}
}
private Node<T> head;
private Node<T> tail;
private int size;
public MyLinkedList () {
head = null;
tail = null;
size = 0;
}
public void addHead (T data) {
if (head == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = head;
head = new Node<T>();
head.data = data;
head.next = tmp;
tmp.prev = head;
head.prev = null;
}
size++;
}
public void addTail (T data) {
if (tail == null) {
head = new Node<T>();
head.data = data;
head.prev = null;
head.next = null;
tail = head;
} else {
Node<T> tmp = tail;
tail = new Node<T>();
tail.data = data;
tmp.next = tail;
tail.prev = tmp;
tail.next = null;
}
size++;
}
public void addMiddle (T data) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
Node<T> n = new Node<T>();
n.data = data;
prev.next = n;
n.prev = prev;
n.next = cur;
cur.prev = n;
size++;
}
public void removeHead () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
head = head.next;
head.prev = null;
size--;
}
}
public T getHead () {
return head.data;
}
public void removeMiddle () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size == 2) {
head = tail; // head removed and updated accordingly
head.prev = null;
size--;
} else if (size > 2) {
Node<T> cur = head;
Node<T> prev = null;
for (int i = 0; i < size / 2; i++) {
prev = cur;
cur = cur.next;
}
prev.next = cur.next;
cur.next.prev = prev;
cur.next = null;
cur.prev = null;
size--;
}
}
public void removeTail () {
if (size == 1) {
head = null;
tail = null;
size--;
} else if (size > 1) {
tail = tail.prev;
tail.next = null;
size--;
}
}
public boolean search (T data) {
Node<T> n = head;
while (n != null) {
if (n.data.equals(data))
return true;
n = n.next;
}
return false;
}
public int getSize () {
return size;
}
@Override
public String toString () {
String str = "";
Node<T> s = head;
while (s != null) {
str += s.data + " ";
s = s.next;
}
return str;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.