斐波那契数列的传统递归方法这里就不讲了。
以下是殷人昆版数据结构中给出的计算斐波那契数的非递归算法。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
using namespace std;
long (long n){
long twoback = 0, oneback=1, current = 0;
for(int i = 1;i < n;i++){
current = oneback + twoback;
twoback = oneback;
oneback = current;
}
return current;
}
int main(){
long n;
cin >> n;
cout << Fibnacci(n) << endl;
return 0;
}
|
$$F(i-2) + F(i-1) = F(i)$$
这里的 twoback 表示$F(i-2)$，oneback 表示$F(i-1)$。
一开始分别赋值0和1，表示$F(0)$和$F(1)$，要计算$F(n)$只需迭代$n-1$次。
计算斐波那契数列的最高效算法是利用递推方程得到的公式直接求解
$$F(n) = frac{1}{sqrt{5}}[(frac{1+sqrt 5}{2})^n - (frac{1-sqrt5}{2})^n]$$
近期评论