-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathrec_to_stack.cc
More file actions
63 lines (57 loc) · 1.28 KB
/
rec_to_stack.cc
File metadata and controls
63 lines (57 loc) · 1.28 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cassert>
#include <vector>
#include <iostream>
int fib(int n) {
if (n < 2)
return n;
return fib(n - 1) + fib(n - 2);
}
int fib_loop(int n) {
enum class State {
Init,
Fib1,
Fib2,
};
struct Frame {
int n;
State state;
int fib1;
Frame(int n): n{n}, state{State::Init}, fib1{0} {}
};
std::vector<Frame> frames;
frames.emplace_back(n);
int ret;
while (!frames.empty()) {
auto &f = frames.back();
// std::cerr << static_cast<int>(f.state) << ' ' << f.n << '\n';
switch (f.state) {
case State::Init:
if (f.n < 2) {
ret = f.n;
frames.pop_back();
} else {
f.state = State::Fib1;
frames.emplace_back(f.n - 1);
}
break;
case State::Fib1:
f.fib1 = ret;
f.state = State::Fib2;
frames.emplace_back(f.n - 2);
break;
case State::Fib2:
ret = f.fib1 + ret;
frames.pop_back();
break;
default:
assert(false);
}
}
return ret;
}
int main() {
int n;
while (std::cin >> n) {
std::cout << fib_loop(n) << '\n';
}
}