当前位置：首页 > news >正文

斐波那契数列------矩阵幂法

news 2025/6/6 5:51:38

斐波那契数列

斐波拉楔数是我们在学递归的使用看到的题目，但递归法是比较慢的，后面我们用循环递进来写的，但今天我有遇到了新的方法—— 矩阵幂法（线性代数的知识点）。

矩阵幂法：

F1=1*F1+0*F2;

F2=0*F1+1*F2;

F3=1*F1+1*F2;

F4=1*F1+2*F2;

………………

根据规律（自己凑出来的）可以发现：

Fn= $\left [ 1,1 \right ]$ * $^{_{\begin{bmatrix} 1 &0 \\ 1 &1 \end{bmatrix}}^{}n-1}$ * $\begin{bmatrix} F1\\ F2 \end{bmatrix}$

所以中间的 $^{_{\begin{bmatrix} 1 &0 \\ 1 &1 \end{bmatrix}}^{}n-1}$ 可以用类似于快速幂的方法计算

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long n;
long long mod = 1e9 + 7;
long long a0[2] = { 1,0 };
long long a[2][2] = { {0,1},{1,1} };
void Multiply(long long b[][2]) {long long c[2][2] = { {b[0][0],b[0][1]},{b[1][0],b[1][1]} };for (long long i = 0; i <2; i++) {for (long long j = 0; j < 2; j++) {long long q = 0;for (long long z = 0; z < 2; z++) {q = (q + c[i][z] * c[z][j] % mod) % mod;}a[i][j] = q;}}
}
void JuZhen (long long p) {while (p > 0) {if (p % 2 == 1) {long long x = a0[0], y = a0[1];a0[0] = (x * a[0][0] % mod + y * a[1][0] % mod) % mod;a0[1] = (x * a[0][1] % mod + y * a[1][1] % mod) % mod;}p /= 2;Multiply(a);}cout << (a0[0] + a0[1]) % mod << endl;
}
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n;JuZhen(n-1);return 0;
}

计算斐波拉楔数的方法：

1. 递归法（Recursive）

特点：直观但效率低，存在大量重复计算
时间复杂度：O(2^n)（指数级）
空间复杂度：O(n)（栈空间）

// 1. 递归法
int fib_recursive(int n) {if (n <= 1) return n;return fib_recursive(n-1) + fib_recursive(n-2);
}

2. 记忆化递归（Memoization）

特点：通过缓存避免重复计算，显著提升递归效率
时间复杂度：O(n)
空间复杂度：O(n)

// 2. 记忆化递归
int fib_memo_helper(int n, unordered_map<int, int>& memo) {if (n <= 1) return n;if (memo.find(n) == memo.end()) {memo[n] = fib_memo_helper(n-1, memo) + fib_memo_helper(n-2, memo);}return memo[n];
}int fib_memo(int n) {unordered_map<int, int> memo;return fib_memo_helper(n, memo);
}

3. 迭代法（动态规划）

特点：高效且节省空间，仅存储前两个值
时间复杂度：O(n)
空间复杂度：O(1)

// 3. 迭代法
int fib_iterative(int n) {if (n <= 1) return n;int a = 0, b = 1;for (int i = 2; i <= n; i++) {int next = a + b;a = b;b = next;}return b;
}

4. 矩阵幂法（Matrix Exponentiation）

特点：利用矩阵乘法快速计算，适合超大 n 值
时间复杂度：O(log n)
空间复杂度：O(1)（忽略矩阵乘法开销）

// 4. 矩阵幂法
struct Matrix {long long a, b, c, d;Matrix(long long a, long long b, long long c, long long d) : a(a), b(b), c(c), d(d) {}
};Matrix matrix_mult(const Matrix& m1, const Matrix& m2) {return Matrix(m1.a * m2.a + m1.b * m2.c,m1.a * m2.b + m1.b * m2.d,m1.c * m2.a + m1.d * m2.c,m1.c * m2.b + m1.d * m2.d);
}Matrix matrix_power(Matrix m, int n) {Matrix result(1, 0, 0, 1); // 单位矩阵while (n) {if (n & 1) {result = matrix_mult(result, m);}m = matrix_mult(m, m);n >>= 1;}return result;
}int fib_matrix(int n) {if (n <= 1) return n;Matrix m(1, 1, 1, 0);Matrix result = matrix_power(m, n - 1);return result.a;
}

5. 通项公式法（Binet's Formula）

特点：数学公式直接计算，但浮点数精度有限
时间复杂度：O(1)（忽略幂运算开销）
空间复杂度：O(1)

// 5. 通项公式法
int fib_binet(int n) {const double sqrt5 = sqrt(5);const double phi = (1 + sqrt5) / 2;return round((pow(phi, n) - pow(-phi, -n)) / sqrt5);
}

6. 生成器法（Generator）

特点：惰性生成无限序列，适合流式处理
时间复杂度：O(n)（单次生成）
空间复杂度：O(1)

// 6. 生成器法
class FibonacciGenerator {
private:long long a = 0, b = 1;
public:long long next() {long long current = a;a = b;b = current + b;return current;}
};

总结对比

方法	时间复杂度	空间复杂度	适用场景
递归法	O(2^n)	O(n)	教学演示（实际避免使用）
记忆化递归	O(n)	O(n)	需要递归且避免重复计算
迭代法	O(n)	O(1)	最常用，平衡效率与简洁
矩阵幂法	O(log n)	O(1)	超大规模 n（如 n > 10^6）
通项公式法	O(1)	O(1)	小规模 n（浮点精度限制）
生成器法	O(n)	O(1)	需要按需生成整个序列