c++斐波那契数列递归算法

C++实现斐波那契数列递归算法如下：

#include <iostream>
using namespace std;

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

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

在该程序中，`fibonacci` 函数是递归实现斐波那契数列的主体部分。如果 `n` 小于等于 1，则直接返回 `n`；否则，返回斐波那契数列的前两项之和。

在 `main` 函数中，首先要求用户输入一个正整数 `n`，然后输出斐波那契数列的第 `n` 项的值。

相关问题

使用C++编写斐波那契数列的算法

在C++中，可以使用递归、循环或者动态规划的方式来编写斐波那契数列的算法。以下是三种常见的实现方法：

1. **递归**:

#include <iostream>
int fibonacci_recursive(int n) {
    if(n <= 0) return 0;
    else if(n == 1) return 1;
    else return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

递归方式简洁直观，但对于大的n值会非常慢，因为存在大量重复计算。

2. **循环**:

#include <iostream>
int fibonacci_iterative(int n) {
    if(n <= 0) return 0;
    if(n == 1) return 1;
    int a = 0, b = 1, c;
    for(int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

循环版本避免了递归带来的重复计算，效率更高。

3. **动态规划**:

#include <vector>
int fibonacci_dp(int n) {
    std::vector<int> fib(n+1, 0);
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i <= n; ++i) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

动态规划存储并利用之前的结果，是最常用的高效方法。

斐波那契数列递归除以10007

根据提供的引用内容，斐波那契数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。为了避免使用递归算法，我们可以使用循环来实现。以下是C++代码实现：

#include <iostream>
using namespace std;

int main() {
    int i = 1, j = 1, n;
    cin >> n;
    if (n == 1 || n == 2) {
        cout << "1";
        return 0;
    }
    int sum = 0;
    for (int t = 3; t <= n; ++t) {
        sum = (i + j) % 10007;
        i = j % 10007;
        j = sum % 10007;
    }
    cout << sum;
    return 0;
}

在上述代码中，我们使用了循环来计算斐波那契数列的值，并在每次计算后对10007取余，以避免计算结果过大。如果n等于1或2，则直接输出1。否则，我们使用循环计算斐波那契数列的值，并在每次计算后对10007取余，最终输出结果。