斐波那契数列第n项公式推导#c++#函数

斐波那契数列是一个经典的数列，每个数字是前两个数字之和。其第一项通常设为0，第二项为1。对于第n项F(n)，可以使用递归公式推导，但这种方法效率较低，因为会有很多重复计算。更高效的做法是使用动态规划，特别是通过“记忆化”来存储已经计算过的值。

在C++中，我们可以使用一个数组或map来存储中间结果，避免重复计算。这里提供一个简单的非递归版C++函数：

#include <iostream>
#include <unordered_map>

int fibonacci(int n) {
    std::unordered_map<int, int> memo; // 记忆表

    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;

    if (memo.find(n) != memo.end()) // 如果之前已计算过
        return memo[n];

    int result = fibonacci(n - 1) + fibonacci(n - 2); // 根据定义计算当前项
    memo[n] = result; // 存储到记忆表中
    return result;
}

int main() {
    int n;
    std::cout << "请输入一个正整数: ";
    std::cin >> n;
    std::cout << "斐波那契数列的第" << n << "项是: " << fibonacci(n) << std::endl;
    return 0;
}