用c++实现斐波那契数列

参考链接： C++程序显示斐波那契数列

首先，我们要知道斐波那契数列是什么 这个数列从第3项开始，每一项都等于前两项之和。即为这样的一个数列 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368… 

使用递归实现: 

对于这个问题的实现，使用递归无疑是最好的办法。我们可以从数列中看出，从第三项开始，F(n)=F(n-1)+F(n-2);(n>2) 那么我们就可以写出实现这个功能的函数 

int Fibonaccisequence(int n)

{

    if(n == 1 || n == 2)

    {

        return 1;

    }

    else

    {

        return Fibonaccisequence(n-1) + Fibonaccisequence(n-2);

    }

}

完整代码如下: 

#include <iostream>

using namespace std;

int Fibonaccisequence(int n)

{

    if(n == 1 || n == 2)

    {

        return 1;

    }

    else

    {

        return Fibonaccisequence(n-1) + Fibonaccisequence(n-2);

    }

}

int main()

{

    int n;    //n表示为第几个数值

    while(cin >> n)

    {

        int res = Fibonaccisequence(n);

        cout << res <<endl;

    }

    return 0;

}

使用非递归: 

其实对于可以使用递归算法来实现的，大多数可以使用循环代替。 

#include <iostream>

using namespace std;

int main()

{

    int n;

    while (cin >> n)

    {

        int s1 = 1;

        int    s2 = 1 ;

        int sn = 0;

        if (n == 1 || n == 2)

        {

            cout << "第"<<n<<"位的斐波那契数为："<<s1 << endl;

        }

        else

        {

            for (int i = 3; i <= n; i++)

            {

                sn = s1 + s2;

                s1 = s2;

                s2 = sn;

            }

            cout << "第" << n << "位的斐波那契数为："<< sn << endl;

        }

    }

    return 0;

}