来源：蚂蚁的 C/C++ 标准编程 作者：Antigloss 等级：一般 发布于2007-06-16 11:46 被读1063次 【字体：大 中 小】     菲波那契数列（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

评论