C语言深入探究斐波那契数列

#include<stdio.h>
int fib(int n)
{
    return n > 2 ? n : fib(n - 1) + fib(n - 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
long long fib(int n)
{
    long long* p = (long long*)malloc(sizeof(long long) * (n+1));
    p[0] = 0;
    p[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        p[i] = p[i - 1] + p[i - 2];
    }
    long long temp = p[n];
    free(p);
    p = NULL;
    return temp;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", fib(n));
    return 0;
}

#include<stdio.h>
long long fib(int n)
{
    if (n < 2)
    {
        return n;
    }
    long long left = 0, right = 1, ret = 1;
    for (int i = 2; i < n; ++i)
    {
        left = right;
        right = ret;
        ret = left + right;
    }
    return ret;
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", fib(n));
    return 0;
}

#include<stdio.h>
#include<math.h>
int fib(int n)
{
    double sqrt5 = sqrt(5);
    double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
    return round(fibN / sqrt5);
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}

#include<stdio.h>
struct Matrix
{
    int mat[2][2];
};
struct Matrix matrixMultiply(struct Matrix* a, struct Matrix* b)
{
    struct Matrix c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.mat[i][j] = (*a).mat[i][0] * (*b).mat[0][j] + (*a).mat[i][1] * (*b).mat[1][j];
        }
    }
    return c;
}
struct Matrix matrixPow(struct Matrix a, int n)
{
    struct Matrix ret;
    ret.mat[0][0] = ret.mat[1][1] = 1;
    ret.mat[0][1] = ret.mat[1][0] = 0;
    while (n > 0) {
        if (n & 1) {
            ret = matrixMultiply(&ret, &a);
        }
        n >>= 1;
        a = matrixMultiply(&a, &a);
    }
    return ret;
}
int fib(int n)
{
    if (n < 2)
    {
        return n;
    }
    struct Matrix q;
    q.mat[0][0] = q.mat[0][1] = q.mat[1][0] = 1;
    q.mat[1][1] = 0;
    struct Matrix res = matrixPow(q, n - 1);
    return res.mat[0][0];
}
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", fib(n));
    return 0;
}