首页 > 代码库 > IT公司100题-19-求Fibonacci数列

IT公司100题-19-求Fibonacci数列

2024-07-16 23:00:00   219人阅读

问题描述：
定义Fibonacci数列的定义如下：
         /    0                           n=0
f(n)=      1                           n=1
\    f(n-1)+f(n-2)          n=2
给定n，求Fibonacci数列的第n项。
 
分析：

1 递归法

 1 // 19_1.cc 2 #include <iostream> 3 using namespace std; 4  5 size_t fibo(size_t n) { 6     if (n < 2) 7         return n; 8     else 9         return fibo(n - 1) + fibo(n - 2);10 }11 12 int main() {13     size_t n;14     cout << "please input n:" << endl;15     cin >> n;16     cout << "The Fibonacci is: " << fibo(n) << endl;17     return 0;18 }

使用递归，会有大量的重复计算，以计算fibo(8)为例：

2 避免重复计算法

从下往上递推，避免重复计算。

 1 // 19_2.cc 2 #include <iostream> 3 using namespace std; 4  5 size_t fibo(size_t n) { 6     if (n < 2) 7         return n; 8  9     size_t f1 = 0;10     size_t f2 = 1;11     size_t res;12     for (size_t i = 2; i <= n; i++) {13         res = f1 + f2;14         f1 = f2;15         f2 = res;16     }17     return res;18 }19 20 int main() {21     size_t n;22     cout << "please input n:" << endl;23     cin >> n;24     cout << "The Fibonacci is: " << fibo(n) << endl;25     return 0;26 }

 


联系
我们