生成斐波那契数列前20项的C++方法

斐波那契数列是一个经典的数学序列，前两项为0和1，后续每一项都是前两项之和。

生成方法

1. 使用循环的简单方法

#include <iostream>

int main() {
    int n = 20;
    long long fib[20];
    
    fib[0] = 0;
    fib[1] = 1;
    
    for (int i = 2; i < n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    for (int i = 0; i < n; i++) {
        std::cout << fib[i] << " ";
    }
    
    return 0;
}

2. 使用递归方法（效率较低）

#include <iostream>

long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    for (int i = 0; i < 20; i++) {
        std::cout << fibonacci(i) << " ";
    }
    return 0;
}

3. 使用递归+记忆化（提高效率）

#include <iostream>
#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo.find(n) != memo.end()) return memo[n];
    
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

int main() {
    for (int i = 0; i < 20; i++) {
        std::cout << fibonacci(i) << " ";
    }
    return 0;
}

4. 使用动态规划（空间优化）

#include <iostream>

int main() {
    int n = 20;
    long long a = 0, b = 1, c;
    
    std::cout << a << " " << b << " ";
    
    for (int i = 2; i < n; i++) {
        c = a + b;
        std::cout << c << " ";
        a = b;
        b = c;
    }
    
    return 0;
}

5. 使用模板元编程（编译时计算）

#include <iostream>

template<int N>
struct Fibonacci {
    static const long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;
};

template<>
struct Fibonacci<0> {
    static const long long value = 0;
};

template<>
struct Fibonacci<1> {
    static const long long value = 1;
};

int main() {
    std::cout << Fibonacci<0>::value << " ";
    std::cout << Fibonacci<1>::value << " ";
    // 继续输出直到Fibonacci<19>::value
    // 这种方法需要在编译时知道所有值
    return 0;
}

6. 使用STL的generate算法

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<long long> fib(20);
    
    fib[0] = 0;
    fib[1] = 1;
    
    std::generate(fib.begin()+2, fib.end(), [&fib]() {
        static int i = 2;
        return fib[i-1] + fib[i-2];
    });
    
    for (auto num : fib) {
        std::cout << num << " ";
    }
    
    return 0;
}

每种方法都有其优缺点，对于生成前20项这样的小规模数列，所有方法都适用。但对于更大的数列，递归方法效率会明显下降，而循环和动态规划方法更为高效。