Question

(C++ Programming)

Practice with Stacks and Queues (PLEASE FOLLOW ALL DIRECTIONS)

·In “stackfib.cpp”, write a non-recursive function fib() which:

·Takes a single int parameter n

·Returns the nth Fibonacci number. We will start with fib(0) == fib(1) == 1, then fib(n) = fib(n-1) + fib(n-2)

·To compute this without using recursion, we use a stack to store the numbers we need to compute

(1)   Initialize your result to be 0

(2)   Push the parameter n onto the stack

(3)   While the stack is not empty,

(a)   Get the top value on the stack (use top()) and pop it off

(b)   If this value is less than 2, add 1 to the result. Do not push anything onto the stack

(c)   Otherwise, push the top value - 1 and the top value – 2. Do not modify the result

(4)   When the stack is finally empty, return the result

·Write main() to test this function – output the values of fib(0) through fib(9)

·Here is some sample final output:

Computing Fibonacci numbers without recursion

fib(0) = 1

fib(1) = 1

fib(2) = 2

fib(3) = 3

fib(4) = 5

fib(5) = 8

fib(6) = 13

fib(7) = 21

fib(8) = 34

fib(9) = 55

Answer 1

1. I have implemented only the stack Fibonacci portion. Hope it will help.

#include <bits/stdc++.h>
using namespace std;


class FibStack
{
public:
    stack <int> fibStack; // stack intialization

    void getFib(int n)    {
        int res = 0; // store result
        int topElement;
        fibStack.push(n); 
        while(!fibStack.empty()) // looping while stack is not Empty
        {
            topElement = fibStack.top(); // get top element
            fibStack.pop(); // remove top element from the stack
            if(topElement<2)
                res += 1;
            else
            {
                fibStack.push(topElement-1);
                fibStack.push(topElement-2);
            }
        }
        cout<<"fib("<<n<<") = "<<res<<endl; // print output (return res will also work, if output should be printed in main function)
    }
};


int main ()
{
    FibStack fs;
    for(int i=0; i<10; i++) // to get 0-9 fibonacci series
        fs.getFib(i);
    return 0;
}

i hope it helps..

If you have any doubts please comment and please don't dislike.

PLEASE GIVE ME A LIKE. ITS VERY IMPORTANT FOR ME