菲波那契数列（Fibonacci sequence）指的是这样一个数列：

        1，1，2，3，5，8，13，21，34，55，……

这个数列从第三项开始，每一项都等于前两项之和。可将其递归定义为：

        F(1) = 1
        F(2) = 1
        F(n) = F(n - 1) + F(n - 2)     n > 2

因此，可用递归的办法编写程序计算该数列第 N 项的值：

        // header inherited from ISO C
        #include <cassert>               // for assert
        // boost header
        #include <boost/bigint.hpp>      // for bigint

        boost::bigint fibonacci(const boost::bigint &n)
        {
            assert(n != 0);

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

            return fibonacci(n - 1) + fibonacci(n - 2);
        }

不过，递归效率实在是太差了，不信你可以试试计算第 50 项的值，看看需要多久。使用迭代可以大大提高运行效率：

        boost::bigint fibonacci(const boost::bigint &n)
        {
            assert(n != 0);

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

            boost::bigint tmp, f1 = 1, f2 = 1;
            for ( boost::bigint i = 2; i != n; ++i )
            {
                tmp = f1 + f2;
                f1.swap(f2);
                f2.swap(tmp);
            }
   
            return f2;
        }

这回计算第 50 项的值一下子就出来了。

    此外，也可以使用公式来计算第 N 项的值：

Boost 库目前似乎还没有针对 bigint 进行开方及求 N 次方的函数（若有请告知），故此，鄙人也就暂不将该公式代码化啦。

    下面这个函数的功能是构建一个 n 项的菲波那契数列

        // ISO C++ header
        #include <vector>
        // header inherited from ISO C
        #include <cassert>               // for assert
        // boost header
        #include <boost/bigint.hpp>      // for bigint

        void form_fib_seq(std::vector<boost::bigint>::size_type n, // 菲波那契数列的项数
                          std::vector<boost::bigint> &vFibSeq)     // 用于保存菲波那契数列
        {
            assert(n != 0);  // 项数不能为 0
   
            if ( n > 2 ) // 如果需要构建的数列的项数大于 2
            {
                // 先将第一、二项的值保存到容器里
                vFibSeq.push_back(1);
                vFibSeq.push_back(1);
                for ( std::vector<boost::bigint>::size_type i = 2;
                      i != n; ++i )
                {
                    // 从第三项开始，每一项都等于前两项之和
                    vFibSeq.push_back(vFibSeq[i - 1] + vFibSeq[i - 2]);
                }
            }
            else  // 如果需要构建的数列的项数小于/等于 2
            {
                while ( n-- != 0 )
                {
                    vFibSeq.push_back(1);
                }
            }
        }

关于斐波那契数列更多内容，可参考：http://bzhang.lamost.org/website/index.php?p=137

本文版权归 蚂蚁的 C/C++ 标准编程 以及 作者 Antigloss 共同所有，转载请注明原作者和出处。谢谢。