CODEWITHSUNDEEP
c++stackfibonacci
user593301
user593301

Reputation: 913

C++ Stack Fibinacci Hw Problem Clarification

Hey Guys. I need help understanding my hw assignment. I am starting out in C++ and don't know that much. I do know the basics of a stack and fibonacci sequence. However I do not exactly understand the problem given to me and need not the code to solving the problem but help clarifying some steps. Here's the hw:

"By completing this project you will become familiar with using recursion and creating ADTs in C++.

Create an integer stack ADT (you may Modify the IntStack ADT given to you in the lecture notes) such that it has a maximum capacity of at least 256 elements. Also add whatever is needed such that it will print out its contents (left-to-right, with the top of the stack on the right) if it is printed to a C++ ostream - such as cout). This stack should be designed such that it will only hold meaningful values greater than zero. Values less than or equal to zero should be printed out as a '?'.

Write a recursive implementation of the Fibonacci sequence discussed in class. Also - create an instance of your stack ADT that persists between calls (it can't be a local variable), and at each step, push a non-meaningful value into it until the value at that stage is determined, then pop it off, and push in the determined value and print the entire stack before returning.

Your program should ask for the position N in the Fibonacci sequence to be determined and then it should output the result of the function call. Example output (including the output from your recursive function) follows:

Enter the position in the Fibonacci sequence to determine: 5

?-?-?-1
?-?-?-1
?-?-2
?-?-1
?-3
?-?-1
?-?-1
?-2
5

Fibonacci(5) = 5

What exactly is the output here? Is it printing out the stack as it calculates the 5th position? also Any ideas on how to implement the Fibonacci into a stack in C++? Should these values be stored in array, list or it doesn't matter? I'm a noob so any help would be much appreciated. Thanks

Upvotes: 0

Views: 363

Answers (3)

Hai Vu
Hai Vu

Reputation: 40733

I leave printing the stack to you and address the confusing part of using the stack to store marker ("the non meaningful" number) and result. Here is the partial pseudo code:

procedure fib(n)
    push a marker (say a zero) to a global stack
    if n is 1 or 2 then
        result = you_know_what
    else
        calculate fib(n-1)
        pop the stack ==> fib_n_minus_1
        calculate fib(n-2)
        pop the stack ==> fib_n_minus_2
        result = fib_n_minus_1 + fib_n_minus_2
    endif

    pop the marker off the stack and discard
    push the result into the stack
    print the stack
end fib

The key to note here is fib() does not return a value. Instead, it pushes the return value into a global stack.

Upvotes: 0

uesp
uesp

Reputation: 6204

Beak your entire problem into smaller parts which can be solved/implemented by themselves. In this case there are two main parts:

  1. Stack -- Implement a standard stack class according to the details given in the question. It may help to list them all in point form.
  2. Fibonacci -- Use the stack class to generate the Fibonacci series recursively. The stack is your storage mechanism for this exercise.

The example output ?-?-?-1 can be understood as the following stack operations:

push 0
push 0
push 0
push 1
print

Upvotes: 0

Migi
Migi

Reputation: 1142

Yes, it's calculating 5th fibonacci number (which happens to be 5, that's a bit confusing), but look at what you calculate when you call fibonacci(5), assuming the following code for fibonacci:

int fibonacci(int n) {
    if (n <= 1) return n;
    else if (n == 2) return 1;
    else return fibonacci(n-1) + fibonacci(n-2);
}

here are the function calls to calculate fibonacci(5):

f(5)
 -> f(4)
     -> f(3)
         -> f(2)
         -> f(1)
     -> f(2)
 ->f(3)
    -> f(2)
    -> f(1)

If you look at this as a binary tree, the output they gave you was a post-order tree traversal, with the amount of ? being the depth of that stack, and the number being the value of that node.

So just do what the function does and every time you see return, write what you return (with the ?'s before it):

  • The first function that returns is the first f(2), at depth 4: print ?-?-?-1
  • The second return is the f(1) below it: print ?-?-?-1
  • The third return is the parent of f(2) and f(1), which has depth 3 and value f(2)+f(1)=2: print ?-?-2
  • And so on until you return f(5) at depth 0 and value 5

Upvotes: 1

Related Questions