美文网首页工作生活
10.斐波那契数列

10.斐波那契数列

作者: HamletSunS | 来源:发表于2019-06-30 18:07 被阅读0次

思路:

  • 公式 f(n)=f(n-1)+f(n-2),f(0)=0,f(1)=1
  • 递归去写,代码很简洁,时间复杂度很高,为指数级,涉及到了大量的重复计算,不建议
  • 用循环去写,定义3个遍历,分别代表f(n),f(n-1),f(n-2),循环中的操作借鉴swap操作
class Solution {
public:
    int Fibonacci(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        int first=1,second=0,ret=0;
        for(int i=2;i<=n;i++){
            ret=first+second;
            second=first;
            first=ret;
        }
        return ret;
    }
};

相关文章

网友评论

    本文标题:10.斐波那契数列

    本文链接:https://www.haomeiwen.com/subject/rbibcctx.html