C++程序 求解斐波那契数列

斐波那契数列是指每个数都是前两个数的和，即0,1,1,2,3,5,8,13,21,34,\cdots。

在C++中，我们可以通过递归和循环两种方法实现斐波那契数列的求解。

递归实现

递归实现的代码较为简单，使用函数自身调用即可求解。

#include<iostream>
using namespace std;

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

int main()
{
    int n;
    cout<<"请输入要求解的斐波那契数列的项数：";
    cin>>n;
    cout<<"斐波那契数列的前"<<n<<"项为：\n";
    for(int i=0;i<n;i++)
    {
        cout<<fib(i)<<" ";
    }
    return 0;
}

输出结果如下：

请输入要求解的斐波那契数列的项数：10
斐波那契数列的前10项为：
0 1 1 2 3 5 8 13 21 34

但是递归实现的效率一般较低，因为每次调用函数时都要重新压栈和出栈，所以当n较大时，程序的效率会降低。

循环实现

循环实现的思路是用两个变量来存储之前的两个数，然后不断更新这两个变量的值，直到求解出所需项数的斐波那契数列。

#include<iostream>
using namespace std;

int main()
{
    int n;
    cout<<"请输入要求解的斐波那契数列的项数：";
    cin>>n;
    cout<<"斐波那契数列的前"<<n<<"项为：\n";
    int fib1=0,fib2=1;//初始值
    cout<<fib1<<" "<<fib2<<" ";
    for(int i=2;i<n;i++)
    {
        int fib=fib1+fib2;
        cout<<fib<<" ";
        fib1=fib2;
        fib2=fib;
    }
    return 0;
}

输出结果如下：

请输入要求解的斐波那契数列的项数：10
斐波那契数列的前10项为：
0 1 1 2 3 5 8 13 21 34

可以看出，循环实现的效率要高于递归实现，因此在实际应用中，我们一般采用循环实现。

结论

通过以上两种方法，我们可以方便地求出所需项数的斐波那契数列。如果我们要在实际应用中实现高效的求解，建议使用循环实现。