1. 说明
Fibonacci 为1200年代的欧洲数学家，在他的著作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是 Fibonacci 数列，一般习惯称之为费氏数列，例如以下：1、1、2、3、5、8、13、21、34、55、89......
2. 解法
依上图所示，我们可以将费氏数列定义为以下：
Fib[0] = 1;Fib[1] = 1;Fib[2] = Fib[1] + Fib[0];Fib[3] = Fib[2] + Fib[1];...
基于如上的推论，当 N<=1 时，Fib[N] = 1，当N >= 2 时，Fib[N] = Fib[N-1] + Fib[N-2]。
2.1 C 语言实现
在 C 语言中，常用的 Fibonacci 数列计算方法有几种，最基本的是递归法、动态规划法（或迭代法）。为了提高性能，通常采用迭代法。
2.1.1 递归方法
#include <stdio.h>// 递归函数计算第 n 项 Fibonacci 数
int fibonacci(int n) {if (n <= 1) {return 1; // F(0) = 1 和 F(1) = 1}return fibonacci(n - 1) + fibonacci(n - 2); // F(n) = F(n-1) + F(n-2)
}int main() {int n;printf("Enter the number of months: ");scanf("%d", &n);printf("The number of rabbits in month %d is %d\n", n, fibonacci(n));return 0;
}2.1.2 迭代方法（优化）
迭代方法是更高效的 Fibonacci 数列计算方式，它避免了递归的重复计算。
#include <stdio.h>// 迭代法计算第 n 项 Fibonacci 数列
int fibonacci(int n) {if (n <= 1) {return 1; // F(0) = 1 和 F(1) = 1}int a = 1, b = 1, temp;for (int i = 2; i <= n; i++) {temp = a + b; // 当前项是前两项之和a = b; // 更新 a 为 bb = temp; // 更新 b 为新计算的值}return b; // 返回第 n 项
}int main() {int n;printf("Enter the number of months: ");scanf("%d", &n);printf("The number of rabbits in month %d is %d\n", n, fibonacci(n));return 0;
}2.2 递归和迭代方法对比
- 递归方法：
- 时间复杂度：O(2^n)，由于有重复的计算，效率较低。
- 空间复杂度：O(n)，递归调用栈需要存储函数调用。
- 迭代方法：
- 时间复杂度：O(n)，每个 Fibonacci 数只需要计算一次。
- 空间复杂度：O(1)，只需要常量空间来保存前两个数。