算法题解：斐波那契数列（C语言）
斐波那契数列
斐波那契数列是一个经典的数学序列，其中每一项的值是前两项的和。数列的前两项通常定义为0和1，即：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)
输入一个正整数n，求斐波那契数列的第n项。
样例
假设输入 n = 5，则其输出为：5，即斐波那契数列的第五项。
F(5) = F(4) + F(3)
= (F(3) + F(2)) + (F(2) + F(1))
= ((F(2) + F(1)) + (F(1) + F(0))) + (F(1) + F(0))
= ((1 + 1) + (1 + 0)) + (1 + 0) = 5
下面我们将通过两种不同的算法来解决这个问题。
算法1
(递归)
递归算法是计算斐波那契数列的一种直观方法，基于定义中的递推公式，递归函数将从 n 向下递归到基准条件（n == 0 或 n == 1）。
递归实现思路：
- 基本情况：当
n等于0或1时，直接返回n； - 递归情况：对于其他
n，返回F(n-1) + F(n-2)。
C语言代码：
int Fibonacci(int n){
if(n == 0 || n == 1){
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
时间复杂度：
递归算法的时间复杂度是 O(2^n)，因为对于每个非基本情况的 n，我们都会调用两次递归函数，这会导致指数级的增长。
空间复杂度：
递归调用使用了栈空间，空间复杂度为 O(n)，因为递归的深度最深为 n。
优缺点：
- 优点：实现简单，直观地基于斐波那契定义公式。
- 缺点：效率较低，存在大量重复计算，如
F(4)会多次被计算。
算法2
(动态规划)
为了避免递归中的重复计算，我们可以使用动态规划的思想。通过保存中间计算结果来提高效率。通过自底向上的方法，从 F(0) 和 F(1) 开始，逐步计算到 F(n)。
动态规划实现思路：
- 初始化两个变量
a = 0，b = 1，分别表示F(0)和F(1)； - 迭代更新
a和b，每次计算F(i)时，a存储F(i-2)的值，b存储F(i-1)的值； - 最后返回
b，即为F(n)的值。
C语言代码：
int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int a = 0, b = 1, c;
for(int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
时间复杂度：
动态规划的时间复杂度是 O(n)，因为我们只需要从 F(0) 计算到 F(n)，每个数字仅计算一次。
空间复杂度：
空间复杂度为 O(1)，因为只用了固定的几个变量来存储中间结果，不需要额外的数组。
优缺点：
- 优点：效率高，没有重复计算，时间复杂度从递归的
O(2^n)降到了O(n)。 - 缺点：相比递归实现稍微复杂一些。
参考文献
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
通过对比递归算法和动态规划算法，显然动态规划具有更优的性能。在实际编程中，推荐使用动态规划来解决斐波那契数列问题。