C++实现斐波那契数列高效
时间: 2024-02-20 11:54:42 浏览: 20
以下是C++中实现斐波那契数列的高效方法:
1. 使用循环:
```cpp
#include <iostream>
using namespace std;
int fibonacci(int n) {
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
int n;
cout << "请输入要计算的斐波那契数列的项数:";
cin >> n;
cout << "第 " << n << " 项的斐波那契数为:" << fibonacci(n) << endl;
return 0;
}
```
2. 使用矩阵:
```cpp
#include <iostream>
using namespace std;
void multiply(int F[2][2], int M[2][2]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n) {
int M[2][2] = {{1, 1}, {1, 0}};
for (int i = 2; i <= n; i++)
multiply(F, M);
}
int fibonacci(int n) {
int F[2][2] = {{1, 1}, {1, 0}};
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
int main() {
int n;
cout << "请输入要计算的斐波那契数列的项数:";
cin >> n;
cout << "第 " << n << " 项的斐波那契数为:" << fibonacci(n) << endl;
return 0;
}
```