By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,871 Members | 2,304 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,871 IT Pros & Developers. It's quick & easy.

fibonacci series

P: 3
Hi guys,
please tell me how to write the iterative version of fibonacci series using a stack.
Thanks
Sep 20 '06 #1
Share this Question
Share on Google+
4 Replies


100+
P: 293
D_C
Why would you want to use a stack to to do the Fibonacci series? It takes two variables.

The idea is to push 1 and 1 on to the stack to begin. Then, for each iteration, pop A, then B off the stack (B >= A). Push B+A, then B back on to the stack. Repeat that loop N times or so.

The stack is entirely worthless, it could be just done using the two variables...
Sep 20 '06 #2

P: 3
I know the stack is entirely worthless but that's the assignment i have been given by my professor and I don't have a choice..
I wrote this program:
#include <cstdio>
#include<iostream>
using namespace std;
int main(int nNumberofArgs, char*pszArgs[])
{
int n;
cout<<"n";
cin>>n;
int b=1, a=0, c=0;
if (n == 0) cout <<a;
else if (n==1)
cout<<a<<b;
else
{
//cout<<c=0;
for (int i=1; i<=n; i++) {
cout<<c;
c=a+b;
a=b;
b=c;
}
}
system("PAUSE");
return 0;
}


but I don't know how to write it using a stack, I don't even know how to use push or pop functions...
I would really appreciate ur help
Sep 20 '06 #3

100+
P: 144
I'm guessing you are probably supposed to define a stack class. Here is a one possible class definition for a stack (minus the actual member function implementations).

Expand|Select|Wrap|Line Numbers
  1. #define STACK_SIZE 10
  2.  
  3. Class Stack {
  4. public:
    Stack();
  5.  
  6. void push(int value);
  7. int pop();
  8. private:
    int size = STACK_SIZE;
  9. int count = 0;
  10. int stack[STACK_SIZE];
  11. }
  12.  
Sep 21 '06 #4

100+
P: 293
D_C
The stack is first in, last out. Suppose you push X, then Y.
(last to come off stack) X Y (first to come off stack).

Make a stack, say s. Before you start your loop, push 1 then 0, or 0 then 0, depending on how the numbers line up.

For each iteration of your loop,
Y = s.pop();
X = s.pop();
s.push(X+Y);
s.push(X);

When you get to N, you simply print s.pop(), assuming it lines up properly.
Sep 21 '06 #5

Post your reply

Sign in to post your reply or Sign up for a free account.