斐波那契数列用c++打出来

下面是用C++语言打印斐波那契数列的代码，其中包括了三种不同的解法：

解法1：使用数组存储每个数值，时间复杂度为O(n)

#include <bits/stdc++.h>
using namespace std;

const int maxn = 41;
int num[maxn];

int main() {
    num[1] = 1;
    num[2] = 1;
    for(int i = 3; i <= 40; i++) {
        num[i] = num[i-1] + num[i-2];
    }
    printf("%d", num[40]);
    return 0;
}

解法2：使用递归，时间复杂度为O(2^n)

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

int main() {
    printf("%d", fib(40));
    return 0;
}

解法3：使用递归，但不使用数组，时间复杂度为O(n)

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    printf("%d", fib(40));
    return 0;
}