用栈非递归实现fib数列

2019-10-10
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5     int val;
 6     int tag;
 7     node(int a = 0, int b = 0) : val(a), tag(b){}
 8 };
 9 long long fib(int x)
10 {
11     stack<node> s;
12     long long sum = 0;
13     do
14     {
15         while (x > 2)
16         {
17             s.push(node(x, 1));
18             x--;
19         }
20         sum++;
21         while (!s.empty())
22         {
23             node temp = s.top(); s.pop();
24             if (temp.tag == 1)
25             {
26                 temp.tag = 2;
27                 s.push(temp);
28                 x = temp.val - 2;
29                 break;
30             }
31         }
32     } while (!s.empty());
33     return sum;
34 }
35 
36 int main()
37 {
38     int v[100];
39     v[1] = v[2] = 1;
40     for (int i = 3; i <= 20; i++)
41         v[i] = fib(i);
42     for (int i = 1; i <= 20; i++)
43         cout << v[i] << endl;
44 }