首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1271301 时间限制：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
牛客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)
Python3
linqi4rea头像 linqi4rea
DP，但是直接的DP的空间复杂度是0(n)，题目要求：要求：空间复杂度 O(1)，时间复杂度 O(n) ，所以使用中间变量，不生成dp list？
直接： 
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        dp = [1]*n
        for i in range(n):
            if i <= 1:
                dp[i] = 1
            else:
                dp[i] = dp[i-1] + dp[i-2]
        return dp[n-1]
改进？： 
        a, b = 1, 1
        if n <= 1:
            return 1
        else:
            for i in range(2, n):
                    tmp = a + b
                    a = b
                    b = tmp
            return b



发表于 2021-12-03 23:39:12 回复(0)
Python3
年少策马且长歌头像 年少策马且长歌
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #斐波那契数的边界条件为：F(0) = 0, F(1) = 1
        if n < 2:
            return n
        else:
            a, b, sum = 0, 0, 1
            for i in range(0, n-1):
                a = b
                b = sum 
                sum = a + b  #状态转移方程，每次滚动更新数组
            return sum 
发表于 2021-09-01 10:55:39 回复(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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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