The Fibonacci sequence is generated using the following recursion: F(n) = F(n-2)

Question

The Fibonacci sequence is generated using the following recursion: F(n) = F(n-2) + F(n-1), for n > 1. F(0) = 0 and F(1) = 1. In this question, you will generate the Fibonacci sequence as a "Singly Linked List" of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., N where N is the largest integer in the sequence that is less than the integer J, comprising the last three digits of your J#. For example, if your J# is J00543244, then J is 244. In that case, the Fibonacci sequence that is generated should be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233. If the last three digits of your J# form an integer that is less than 100, add 100 to the last three digits of your J# and use the resulting value as J. For example, if your J# is J00543034, then J is 34 + 100 = 134 and the Fibonacci sequence generated would be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. You are given the code for the Singly Linked List-based implementation of the List ADT. Add a member function constructSequence(int) to the List class that takes an integer argument (upperBound: J for the Fibonacci sequence) The main function given to you already inserts the first two nodes (with data 0 and 1 respectively) to a List called FibonacciList. Your task will be to implement the constructSequence function that will insert a sequence of nodes (one node per iteration) to the FibonacciList whose last element will be the largest element in the sequence that is less than the upperBound.

#include <iostream>

using namespace std;

// implementing the dynamic List ADT using Linked List

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class List{

private:

Node *headPtr;

public:

List(){

headPtr = new Node();

headPtr->setNextNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void insert(int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

while (currentNodePtr != 0){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

prevNodePtr->setNextNodePtr(newNodePtr);

}

void insertAtIndex(int insertIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

prevNodePtr->setNextNodePtr(newNodePtr);

}

int read(int readIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == readIndex)

return currentNodePtr->getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

void modifyElement(int modifyIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == modifyIndex){

currentNodePtr->setData(data);

return;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

}

void deleteElementAtIndex(int deleteIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == deleteIndex){

nextNodePtr = currentNodePtr->getNextNodePtr();

break;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

prevNodePtr->setNextNodePtr(nextNodePtr);

}

void deleteElement(int deleteData){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

while (currentNodePtr != 0){

if (currentNodePtr->getData() == deleteData){

nextNodePtr = currentNodePtr->getNextNodePtr();

break;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

prevNodePtr->setNextNodePtr(nextNodePtr);

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout << currentNodePtr->getData() << " ";

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout << endl;

}

void constructSequence(int upperBound){

Node* firstNodePtr = headPtr->getNextNodePtr();

Node* secondNodePtr = firstNodePtr->getNextNodePtr();

// complete the code to construct a singly linked list that has the elements of the

// Fibonacci sequence less than or equal to the upperBound

}

};

int main(){

List FibonacciList;

FibonacciList.insert(0);

FibonacciList.insert(1);

int upperBoundFibonacciValue;

cout << "Enter the upper bound for the sequence: ";

cin >> upperBoundFibonacciValue;

FibonacciList.constructSequence(upperBoundFibonacciValue);

FibonacciList.IterativePrint();

return 0;

}

Explanation / Answer

In the Fibonacci sequence, the first two numbers are 0 and 1 and each number after that is the sum of the previous two numbers in the sequence. So, the sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21… and so on. The “0” in the sequence is considered to be the 0th element, the first “1” is considered to be the 1st element, the 2 is the 3rd element, etc. And the problem specifically states that the function or method needs to return the nth element in the Fibonacci sequence, where the input to that function or method is n.

It should be very clear that if the input to our method is a 0, then we will return a 0 because the 0th element in the sequence is a 0. Likewise, if n is 1, then we will have to return a 1. These 2 scenarios are the base cases for our recursive method. So far, our incomplete method looks like this in Java:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.