首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1286504 时间限制：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)
Python3
刘隐月头像 刘隐月 
牛客网会把 or 转换成 &nbs***bsp; 不知道为什么

'''递归法 (超时)'''
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 1
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)

'''逐一记录法'''
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n <= 0:
            return 0
        result = [1]*n
        if n > 2:
            for i in range(2,n):
                result[i] = result[i-1] + result[i-2]
        return result[n-1]

'''三数循环法'''
class Solution:
    def Fibonacci(self , n: int) -> int:
        a,b = 1,1
        if n <= 0:
            return 0
        if n == 1&nbs***bsp;n == 2:
            return 1
        if n > 2:
            for i in range(2,n):
                res = a+b
                a,b = b,res
        return res

'''二数循环法'''
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n <= 0:
            return 0
        if n == 1&nbs***bsp;n == 2:
            return 1
        a,b = 1,1
        if n > 2:
            for i in range(2,n+1):
                a,b = b,a+b
        return a

发表于 2024-12-12 12:40:49 回复(0)
Python3
iwaku头像 iwaku
时间复杂度O(1) 通项公式 
import math
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        return int((((1+math.sqrt(5))/2)**n-((1-math.sqrt(5))/2)**n)/math.sqrt(5))

发表于 2024-12-07 21:29:20 回复(0)
Python3
牛客368871463号头像 牛客368871463号
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        f = [0] *(n + 2)
        f[0] = 0
        f[1] = 1
        for i in range(2,n + 1):
            f[i] = f[i - 1] + f[i - 2]
        return f[n]
发表于 2024-08-21 18:17:36 回复(0)
Python3
牛客619898895号头像 牛客619898895号
class Solution:
    def Fibonacci(self, n: int) -> int:
        if n <= 2:
            return 1
        else:
            tmp1 = 1
            tmp2 = 1
            rlt = 0
            for i in range(2, n):
                cur = tmp1 + tmp2
                tmp2 = tmp1
                tmp1 = cur
                rlt = cur
            return rlt
发表于 2023-04-13 21:14:14 回复(0)
Python3
Namely头像 Namely 
class Solution:
    def Fibonacci(self , n: int) -> int:
        f1 = f2 = 1
        if n <= 2:
            return f1

        for i in range(3,n+1):
            f2, f1 = f1, f2+f1
        return f1

发表于 2023-03-02 14:13:45 回复(0)
Python3
努力搞钱头像 努力搞钱 
class Solution:
    def Fibonacci(self, n: int) -> int:
        list1 = [1, 1]
        if n <= 2:
            return 1
        else:
            for i in range(1, n-1):
                    list1.append(list1[-1]+list1[-2])
            return list1[-1]
发表于 2022-11-01 00:33:09 回复(0)
Python3
牛客720958981号头像 牛客720958981号
class Solution:
    def Fibonacci(self, n: int) -> int:
        z=[0,1]
        while len(z)<=n :
            z.append((z[-2]+z[-1]))
        return z[-1]
发表于 2022-10-20 09:41:10 回复(0)
Python3
momo本mo头像 momo本mo
# 只用递归会运行超时
class Solution:
    def __init__(self) -> None:
        # 用一个字典记录F(n)有没有计算过
        self.f = dict()
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<=2: return 1
        else: 
            if self.f.get(n-1,-1) == -1:
                a = self.Fibonacci(n-1)
                # 在递归的基础上避免重复计算
                self.f[n-1] = a
            else:
                a = self.f[n-1]
            if self.f.get(n-2,-1) == -1:
                b = self.Fibonacci(n-2)
                self.f[n-2] = b
            else:
                b = self.f[n-2]
            return a + b
发表于 2022-09-20 13:45:21 回复(0)
Python3
牛客703888323号头像 牛客703888323号
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n == 1 or n==2:
            return 1
        if n <0:
            return None
        else:
            return self.Fibonacci(n-1) + self.Fibonacci(n-2)
发表于 2022-03-19 15:34:03 回复(0)
Python3
Joy_9头像 Joy_9 
import functools
class Solution:
    @functools.lru_cache()
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n==1&nbs***bsp;n==2:
            return 1
        else:
            return self.Fibonacci(n-1)+self.Fibonacci(n-2)

发表于 2021-12-28 10:31:54 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 数组 快速幂 递归
来自：寻找时间黑客在线编程大...
难度：
23条回答 209424浏览

热门推荐

通过挑战的用户

查看代码

相关试题

斐波那契数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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