int fib(int n) {
if(n == 1 || n == 2) { return n; }
return fib(n-1) + fib(n-2)
1
v2mm 2021-10-06 22:38:34 +08:00
stack.push(n);
sum = 0; while (!stack.empty()) { i = stack.pop() if(i == 1 || i == 2) sum += i; else { stack.push(i-1); stack.push(i-2); } } |
2
metitation OP @v2mm if(i == 1 || i == 2)
sum += 1; |
3
AoEiuV020 2021-10-06 22:59:13 +08:00 via Android
啊这,是来出考题的吗,斐波那契搞递归本来就是底效的了,强行模拟递归就更难看了,
而且模拟递归是固定套路和具体题目没啥关系吧, 另外斐波那契前两项是 1 不是 n,1 楼都被楼主带偏了, |
4
metitation OP 是我搞错了,标准的是 0 、1 、1 、2 、3 、5 、8 、13 、21 、34 、……
但是一般说是 1 、1 、2 、3 、5 、8 、13 、21 、34 、…… F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)( n ≥ 2,n ∈ N*) |
5
namelosw 2021-10-06 23:23:16 +08:00
一楼写的就挺好的。
调用栈可以看成树,求值本质上就是多叉树遍历,比如从 fib(5) 一路遍历下来 fib(0) 和 fib(1) 就可以在纸上画成一颗树,所以抄一个迭代版 DFS 改一改其实就出来一楼的结果了。 |
6
akira 2021-10-06 23:56:44 +08:00
递归的时候做了啥事情,保留现场 ,压入参数,执行一遍代码,恢复现场 ,重新模拟一遍就是好了啦
|
7
vance123 2021-10-07 02:26:56 +08:00
如果是```fib(n - 1) + fib(n - 2) * 2```呢?
|
8
jinliming2 2021-10-07 12:10:51 +08:00
斐波那契数列本身就不需要递归、栈啊,只需要两个变量保存前两项的值就行啊?
|
9
lonewolfakela 2021-10-07 12:27:34 +08:00
struct fib_state
{ void* ret_addr; int n; int n_minus_1; int n_minus_2; int ret_val; }; std::stack<fib_state> stack; void* call(void* func_addr, int n, void* ret_addr) { stack.push(fib_state{ ret_addr, n }); return func_addr; } void* ret(int ret_val) { void* p = stack.top().ret_addr; stack.pop(); stack.top().ret_val = ret_val; return p; } int fib(int n) { stack.push(fib_state{}); goto* call(&& fib_func, n, && ret); ret: return stack.top().ret_val; fib_func: if (stack.top().n <= 2) { goto* ret(1); } { goto* call(&& fib_func, stack.top().n - 1, && lbl_1); lbl_1: stack.top().n_minus_1 = stack.top().ret_val; } { goto* call(&& fib_func, stack.top().n - 2, && lbl_2); lbl_2: stack.top().n_minus_2 = stack.top().ret_val; } goto* ret(stack.top().n_minus_1 + stack.top().n_minus_2); } 简单、粗暴、有效、好使。 再复杂的递归函数都能 goto 出来…… |