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

 斐波那契数列 

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

矩阵幂法：

F1=1*F1+0*F2;

F2=0*F1+1*F2;

F3=1*F1+1*F2;

F4=1*F1+2*F2;

………………

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

Fn=**

所以中间的可以用类似于快速幂的方法计算

代码：

#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;
    }
};

总结对比