斐波那契数列是一个非常经典的数学序列，其定义为：第一项F0=0，第二项F1=1，之后的每一项Fn都是前两项Fn-1和Fn-2的和，即Fn=Fn-1+Fn-2。这个序列在计算机科学中有着广泛的应用，尤其是在算法竞赛和数据结构的学习中。
### 1. 递归实现
递归是最直观的解决斐波那契数列的方法。然而，这种方法效率极低，因为它会产生大量的重复计算。在C语言中的实现如下：
```c
int fib1(int index) {
if (index < 1) return -1;
if (index == 1 || index == 2) return 1;
return fib1(index - 1) + fib1(index - 2);
}
```
### 2. 数组实现
通过预先存储已计算的项，避免重复计算，可以显著提高效率。数组实现如下：
```c
int fib2(int index) {
if (index < 1) return -1;
if (index < 3) return 1;
int *a = new int[index];
a[0] = a[1] = 1;
for (int i = 2; i < index; i++) a[i] = a[i - 1] + a[i - 2];
int m = a[index - 1];
delete[] a; // 释放内存空间
return m;
}
```
### 3. `vector<int>` 实现
`vector<int>` 的实现与数组类似，但它提供了动态增长的能力，但可能因为额外的内存管理而带来一定开销。
```c
int fib3(int index) {
if (index < 1) return -1;
vector<int> a(2, 1); // 创建一个含有2个元素都为1的向量
a.reserve(3);
for (int i = 2; i < index; i++) {
a.insert(a.begin(), a.at(0) + a.at(1));
a.pop_back();
}
return a.at(0);
}
```
### 4. `queue<int>` 实现
利用队列的特性，只保留最近的两个元素，可以有效地解决问题。
```c
int fib4(int index) {
if (index < 1) return -1;
queue<int> q;
q.push(1);
q.push(1);
for (int i = 2; i < index; i++) {
q.push(q.front() + q.back());
q.pop();
}
return q.back();
}
```
### 5. 迭代实现
迭代方法是最高效的方式，只需要常数级别的空间复杂度和线性的计算时间。
```c
int fib5(int n) {
int i, a = 1, b = 1, c = 1;
if (n < 1) return -1;
for (i = 2; i < n; i++) {
c = a + b; // 辗转相加法
a = b;
b = c;
}
return c;
}
```
### 6. 公式实现
斐波那契数列有一个闭合形式的公式，但是由于浮点数精度限制，可能会有误差。公式如下：
```c
int fib6(int n) {
double gh5 = sqrt((double)5);
return (pow((1 + gh5), n) - pow((1 - gh5), n)) / (pow((double)2, n) * gh5);
}
```
### 7. 二分矩阵方法
通过矩阵快速幂可以将斐波那契数列的计算时间降低到对数级别，但这涉及到更复杂的矩阵运算和位运算。
在实际编程中，通常推荐使用迭代或数组实现，因为它们具有较高的效率和较低的内存消耗。对于大型输入，公式实现或二分矩阵方法可能更优，但需要对数值计算和矩阵操作有深入理解。在不同的场景下，选择合适的实现方式至关重要，以平衡性能和代码的简洁性。
- 1
- 2
前往页