Question

C++ Progamming

This lab gives you a little practice with stacks and queues

·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

·In a different file “sched_sim.cpp”, define classes Process and Sched to simulate an operating system alternating among processes, giving each a “time slice”. You will use a queue to manage the processes.

·The Process class should include: (you can add more functions)

(1)   Integer fields for id and time left (number of cycles left to finish execution) – these must be private

(2)   A constructor to initialize the id and time left

(3)   runPeriod() to “run” the process for 5 cycles. We only care about the scheduling, so output the process being run and how many cycles are left after the 5 cycles are over

(4)   done() to return true if the process has nothing left to do (0 time left)

·The Sched class should include:

(1)   A private queue of Process’s – you can make it a queue of pointers to Process if you prefer

(2)   A function addProcess() that takes a Process parameter and adds it to the queue

(3)   A function exec() that:

(a)   If the queue is empty, output a message for that

(b)   Otherwise, take the first process off the queue and

(i)    call runPeriod() for that process

(ii)  if the process is not done, add it back to the queue

·Write a main() to test your code. Sample output for the final program (process 0 needs 14 cycles, process 1 needs 3 cycles, process 2 needs 7 cycles. Processes 0 and 1 are added first, then the Sched exec()’s once before process 2 is added.)

Simulating timesharing among processes

Running process 0

        9 cycles left

Running process 1

        0 cycles left

Running process 0

        4 cycles left

Running process 2

        2 cycles left

Running process 0

        0 cycles left

Running process 2

        0 cycles left

No waiting processes

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;
}

Do like if it helps. Stay safe