首页 > 其他 > 详细

斐波那契数的两种实现方式———1.递归实现,2迭代实现

时间:2016-04-10 01:24:06      阅读:177      评论:0      收藏:0      [点我收藏+]


技术分享

    对于斐波那契数,若是采用递归的算法,每个递归调用都将触发另外两个递归调用,而这两个中调用任意一个还会触发另外两个的调用。递归调用的时间复杂度O(2^N),空间复杂度为O(N),所以在计算略大的数会花费一定的时间和空间。递归程序如下:

#include<iostream>
using namespace std;

unsigned long long Fib(size_t num)
{
    if (num < 2)
    {
        return num;
    }
    else
        return Fib(num - 1) + Fib(num - 2);
}
int main()
{
    unsigned long long ret = Fib(10);
    cout << ret << endl;
    system("pause");
    return 0;
}

技术分享

用迭代方法计算第N 个斐波那契数,时间复杂度O(N),空间复杂度O(1),程序如下:

#include<iostream>
using namespace std;

unsigned long long Fib(size_t num)
{
    unsigned long long first = 0;
    unsigned long long second = 1;
    unsigned long long sum = 0;
    if (num < 2)
        return num;
    else
       for (size_t i = 2; i <= num; i++)
       {
           sum = first + second;
           first = second;
           second = sum;
       }
       return sum;
}

int main()
{
    unsigned long long ret = Fib(10);
    cout <<"Fibonacci(10)="<< ret << endl;
    system("pause");
    return 0;
}

技术分享

本文出自 “朔月云影” 博客,请务必保留此出处http://19940325.blog.51cto.com/10789287/1762158

斐波那契数的两种实现方式———1.递归实现,2迭代实现

原文:http://19940325.blog.51cto.com/10789287/1762158

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!