斐波那契数列快速幂c语言

斐波那契数列可以用快速幂算法来进行优化，可以将时间复杂度从线性递归的 O(2^n) 降为 O(log n)。

下面是用 C 语言实现斐波那契数列快速幂的代码：

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1)
        return n;

    int a = 0, b = 1, c, i;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int fibonacci_fast(int n) {
    if (n <= 1)
        return n;

    int F[2][2] = {{1, 1}, {1, 0}};
    int M[2][2] = {{1, 0}, {0, 1}};

    while (n > 0) {
        if (n % 2 == 1) {
            int tmp[2][2] = {{0, 0}, {0, 0}};
            int i, j, k;
            for (i = 0; i < 2; i++) {
                for (j = 0; j < 2; j++) {
                    for (k = 0; k < 2; k++) {
                        tmp[i][j] += M[i][k] * F[k][j];
                    }
                }
            }
            M[0][0] = tmp[0][0];
            M[0][1] = tmp[0][1];
            M[1][0] = tmp[1][0];
            M[1][1] = tmp[1][1];
        }

        int tmp[2][2] = {{0, 0}, {0, 0}};
        int i, j, k;
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                for (k = 0; k < 2; k++) {
                    tmp[i][j] += F[i][k] * F[k][j];
                }
            }
        }
        F[0][0] = tmp[0][0];
        F[0][1] = tmp[0][1];
        F[1][0] = tmp[1][0];
        F[1][1] = tmp[1][1];

        n /= 2;
    }

    return M[1][0];
}

int main() {
    int n = 10;
    printf("fibonacci(%d) = %d\n", n, fibonacci(n));
    printf("fibonacci_fast(%d) = %d\n", n, fibonacci_fast(n));

    return 0;
}

其中 `fibonacci` 函数是用线性递归的方式计算斐波那契数列的值，而 `fibonacci_fast` 函数则是用快速幂算法来计算斐波那契数列的值。