首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1300241 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围：
要求：空间复杂度 ，时间复杂度 ，本题也有时间复杂度 的解法


输入描述:
一个正整数n


输出描述:
输出一个正整数。
示例1

输入

4

输出

3

说明

根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
示例2

输入

1

输出

1
示例3

输入

2

输出

1
算法知识视频讲解
添加回答
推荐
fanhk头像 fanhk
c++动态规划版 
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--) {
            g += f;
            f = g - f;
        }
        return f;
    }
};

编辑于 2015-06-19 17:21:55 回复(110)
Python 3
来个offer叭！头像 来个offer叭！ 
class Solution:
    def Fibonacci(self , n: int) -> int:
        fib = [0,1,1]
        for i in range(3, n+1):
            fib.append(fib[i-1]+fib[i-2])
        return fib[n]

发表于 2022-07-21 16:55:05 回复(0)
Java
PrinceZaZa头像 PrinceZaZa 
public class Solution {
    public int Fibonacci(int n) {
        if (n <= 2)
            return 1;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

发表于 2022-07-07 20:45:03 回复(0)
Python 3
秀中作乐1946头像 秀中作乐1946
递归+记忆化=动态规划
第一步：递归
递归循环 : x3=x1+x2 并且没有其他规律/pattern 则直接return self.Fibonacci(n-1) + self.Fibonacci(n-2)
同时数据起始点在x=1上，所以当x=1 返还1，注意当x=2时候会计算 Fibonacci(2-2)也就是Fibonacci(0)所以必须预设x=0时所返还的数值，则if x =0 :return 0 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n == 0: return 0
        if n == 1:
            return 1
        return self.Fibonacci(n-1)+self.Fibonacci[n-2]

第二步：记忆化
如果不记忆化，当x大于大概30，时间就爆炸了，因为计算Fibonacci(n-1)就已经重复了很多Fibonacci(n-2)
因为Fibonacci(n-1)里面会去计算Fibonacci(n-2)+Fibonacci(n-3)
    
            找到重复的代码部分想办法记录下来就可以完成记忆化

因为Fibonacci(n-2)的计算全部是重复，所以直接记忆化Fibonacci(n-2) 
class Solution:
    def __init__(self):
        self.memo=[0]   
    
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n == 0: return 0
        if n == 1:
            self.memo.append(1)
            return 1
        res =self.Fibonacci(n-1)+self.memo[n-2]
        
        self.memo.append(res)
        return res
发表于 2022-07-07 14:57:56 回复(0)
Java
老菜鸟养乐多头像 老菜鸟养乐多

废话不多说，直接上代码

public class Solution {
    public int Fibonacci(int n) {
        if (n == 1 || n == 2) return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}
发表于 2022-04-12 01:12:44 回复(0)
Typescript
写前端的刻猫猫头像 写前端的刻猫猫 
export function Fibonacci(n: number): number {
    // write code here
    if(n<=1) {
        return n;
    }
    
    const cache:number[] = [];
    cache[0] = 0;
    cache[1] = 1;
    for(let i = 2; i<=n; i++ ) {
        cache[i] = cache[i-1] + cache[i-2];
    }
    return cache[n];
}

发表于 2022-03-26 00:52:29 回复(0)
牛客87268150号头像 牛客87268150号
python方法 空间复杂度O(1) 时间复杂度O(n)
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        a, b = 1, 1
        if n <= 2:
            return 1
        n -= 2
        while n:
            a, b = b, a+b
            n -= 1
        return b

发表于 2022-02-18 22:08:18 回复(0)
Java
Isolated_Island头像 Isolated_Island 
public class Solution {
    public int Fibonacci(int n) {
        int a = 1;
        int b = 1;
        while (n-- > 2) {
            b += a;
            a = b - a;
        }
        return b;
    }
}

发表于 2022-02-18 18:35:15 回复(0)
C/C++
勤能补拙i头像 勤能补拙i
充分利用之前计算过的数避免重复计算。
4ms  526KB 
const int MAXN=100;
class Solution {
public: 
    long long f[MAXN];
    bool visit[MAXN];
    
long long Fibonacci(int n){
    f[0]=0;
    f[1]=1;
    visit[0]=visit[1]=true;
    if(visit[n]){
        return f[n];
    }
    f[n]=Fibonacci(n-2)+Fibonacci(n-1);
    visit[n]=true;
    return f[n];
}
};





编辑于 2022-02-19 20:04:46 回复(0)
Java
牛客782370655号头像 牛客782370655号 
public class Solution {
    public int Fibonacci(int n) {
        if(n == 0) return 0;        
        int a = 1;
        int b = 1;
        for(int i = 2; i < n; i++){
            a = a + b;
            b = a - b;
        }
        return a;
    }
}

发表于 2021-08-25 10:58:50 回复(0)
Python3
牛客468224962号头像 牛客468224962号
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 0:
            return 0
        elif n == 1:
            return 1
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)

#怎么避免递归带来的重复计算呢？？
发表于 2021-07-29 21:33:58 回复(4)
C
CrescentHU头像 CrescentHU
/**
 * 
 * @param n int整型 
 * @return int整型
 */
int Fibonacci(int n ) {
    // write code here
    int f1,f2,f3,i;
    f1=0;
    f2=1;
    if(n==0||n==1)return n;
    for(i=2;i<=n;i++)
    {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }
    return f3;
}
发表于 2021-07-24 16:38:21 回复(0)
jj11头像 jj11 
class Solution:
    def Fibonacci(self,n):
        if n<=1:
            return n
        else:
            a=0
            b=1
            for i in range(n-1):
                a,b=b,a+b
            return b

发表于 2021-05-19 21:50:31 回复(0)
wengJJ头像 wengJJ
Python 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if(n==0):
            return 0
        elif(n==1):
            return 1
        lnum = 0
        rnum = 1
        for _ in range(n-1):
            total = lnum + rnum
            lnum = rnum
            rnum = total
            
        return total
            


发表于 2021-04-14 10:47:35 回复(0)
via223头像 via223
实现斐波拉契数列步骤：
（1）判断n是否为0或者1，如果是这样两个初始值直接返回对应0、1；
（2）从n>=2开始，使用列表添加每一个i下的数列值，一直到n+1（闭区间）
（3）返回列表的最后一个索引值，即为所求； 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n==0:
            return 0;
        if n==1:
            return 1;
        if n>=2:
            f_list = [0,1]
            for i in range(2,n+1,1):
                ai = f_list[i-1] + f_list[i-2]
                f_list.append(ai)
            return f_list[-1]


发表于 2021-04-10 02:01:45 回复(0)
JavaScript
splwany头像 splwany 
function Fibonacci(n)
{
    let [a, b] = [0, 1];
    while (n--) {
        b += a;
        a = b - a;
    }
    return a;
}

编辑于 2021-03-29 14:50:59 回复(0)
distinctive头像 distinctive 
func Fibonacci( n int ) int {
    // write code here
    if(n < 2){
        return n;
    }
    tail := 0
    head := 1
    for i := 2; i <= n; i++ {
        tail, head = head, tail + head
    }
    return head
}

golang dp数组

编辑于 2021-03-28 14:58:06 回复(0)
zzzwzx头像 zzzwzx
跟爬楼梯差不多 
public class Solution {
    public int Fibonacci(int n) {
        if (n == 0) return 0;
        
        int a = 1, b = 1, c = 1;
        for(int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        
        return c;
    }
}


发表于 2021-02-26 22:59:28 回复(0)
_Sakura__头像 _Sakura__ 
public class Solution {
    public int Fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        int r= 0, s = 1, t = 1;
        for(int i = 3; i <= n; i++) {
            int m = t;
            t = s + t;
            r = s;
            s = m;
        }
        return t;
    }
}

发表于 2021-02-22 19:21:12 回复(0)
Python
LHC0512头像 LHC0512
Python 
class Solution:
    def Fibonacci(self, n):
        a, b = 0, 1
        if n == 0:
            return a
        for i in range(2, n+1):
            a, b = b, a + b
        return b


发表于 2021-02-22 17:16:53 回复(0)
C/C++
Joker2720头像 Joker2720 
class Solution {
public:
    int Fibonacci(int n) {    //递归
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};

编辑于 2022-02-11 10:14:10 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 数组 快速幂 递归
来自：2025年春招-中国电...
难度：
2485条回答 214812浏览

热门推荐

通过挑战的用户

查看代码

相关试题

斐波那契数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号