首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列

热度指数：1283761 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 $fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.$ 的数列

数据范围： $1\leq n\leq 40$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ ，本题也有时间复杂度 $O(logn)$ 的解法

输入描述:

一个正整数n

输出描述:

输出一个正整数。

示例1

输入

输出

说明

根据斐波那契数列的定义可知，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

输入

输出

示例3

输入

输出

算法知识视频讲解

推荐

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

响亮的闵玆

class Solution:

def Fibonacci(self , n: int) :

# write code here

d=[0]*n

d[0],d[1]=1,1

if n==1 or n==2:

return 1

else:

for i in range(2,n):

d[i]=d[i-1]+d[i-2]

return d[n-1]

发表于 2024-02-20 22:53:01 回复(0)

Python 3

talv

# 搞事情

class Solution:

def Fibonacci(self , n: int) -> int:

import math

a = 0.5*(1+math.sqrt(5))

b = 0.5*(1-math.sqrt(5))

c = (1-1/math.sqrt(5))/2

d = c*math.pow(a,n+1)+(1-c)*math.pow(b,n+1)

print(d)

return(round(d))

# write code here

发表于 2023-03-15 21:33:54 回复(0)

Python 3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n == 1&nbs***bsp;n ==2:
            return 1
        one, two = 1, 1
        while n > 2:
            tmp = one
            one = two
            two = two + tmp
            n = n - 1
        return two

发表于 2022-09-14 11:46:30 回复(0)

Python 3

牛客659106785号

class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        li = [0, 1, 1]
        if n>2:
            for i in range(n-2):
                num = li[-1] + li[-2]
                li.append(num)
        return li[-1]

发表于 2022-09-01 17:06:15 回复(0)

Python 3

牛客32833635号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    fb = {1:1,2:1,3:2}
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n==1&nbs***bsp;n==2:
            return self.fb[n]
        else:
            if n-1 not in self.fb:self.fb[n-1] = self.Fibonacci(n-1)
            if n-2 not in self.fb:self.fb[n-2] = self.Fibonacci(n-2)
            return self.fb[n-1]+self.fb[n-2]

发表于 2022-08-23 08:02:19 回复(0)

Python 3

东方佑

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<=2:
            return 1
        else:
#           递归
#             return self.Fibonacci(n-1)+self.Fibonacci(n-2)
            start=[1,1]
            for _ in range(n-2):
                start.append(start[0]+start[1])
                start.pop(0)
            return start[-1]

发表于 2022-07-26 15:45:07 回复(0)

Python 3

来个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)

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#

class Solution:
    def Fibonacci(self , n: int) -> int:
        ## 通过递归来实现 
        # write code here
        if n == 0: 
            return 0 
        if n == 1: 
            return 1
        if n == 2: 
            return 1 
        return self.Fibonacci(n-1) + self.Fibonacci(n-2)


class Solution:
    def Fibonacci(self, n: int) -> int:
        ## 通过动态规划来实现 
        dp = [0] * (n+1) 
        dp[0] = 0
        dp[1] = 1
        dp[2] = 1
        for i in range(2, n+1):
            dp[i] = dp[i - 1] + dp[i - 2]
#         print(dp) 
        return dp[n]

发表于 2022-07-16 09:55:16 回复(0)

Python 3

秀中作乐1946

https://www.youtube.com/watch?v=oBt53YbR9Kk

递归+记忆化=动态规划

第一步：递归

递归循环 : 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)

Python 3

Vivimore

class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n==2:
            return 1
        a = 1
        b = 1
        for i in range(3, n + 1):
            res = a + b
            a = b
            b = res 
        return res

发表于 2022-05-21 10:05:36 回复(0)

Python 3

燕北茶

不用递归，试试用列表直接算

class Solution:
    def __init__(self):
        self.L=[1,1]

    def Fibonacci(self , n: int) -> int:
        # write code here
        if n <=2:
            return 1
        for i in range(n-2):
            self.L.append(self.L[-1]+self.L[-2])   
        return self.L[n-1]

如果可以调矩阵，感觉用矩阵也可以

import numpy as np

class Solution:
    def __init__(self):
        self.m=np.mat('1 1;1 0')

    def Fibonacci(self , n: int) -> int:
        # write code here
        res = self.m**n
        return res[-1,0]

发表于 2022-05-06 12:12:48 回复(0)

Python 3

danspace

class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        f = [0,1,1]
        if n >= 3:
            for i in range(3, n+1):
                f.append(f[i-1]+f[i-2])
        return f[n]

发表于 2022-04-19 10:06:49 回复(0)

Python 3

ygl45

num=int(input())
num1=num2=num3=1
while num-2 > 0:
    num3=num1+num2
    num1=num2
    num2=num3
    num-=1

print(num3)
    
#孱弱的成长之路

发表于 2022-04-15 10:36:00 回复(0)

Python 3

尹煜

class Solution:
def Fibonacci(self , n: int) -> int:
# write code here
fiblist = [1,1]
i = 0
while i <= n-2:
a = fiblist[i]+fiblist[i+1]
fiblist.append(a)
i += 1

return fiblist[n-1]

可能不符合复杂度的要求

发表于 2022-04-13 10:08:56 回复(0)

Python 3

牛客991913212号

#暴力递归（会超时）
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n ==2:
            return 1
        else:
            return self.Fibonacci(n -1) + self.Fibonacci(n - 2)

# 采用dP动态规划
class Solution:
    def Fibonacci(self , n: int) -> int:
        res = [0] * n
        res[0] = 1
        res[1] = 1
        for i in range(2,n):
            res[i] = res[i -1] +res[i-2]
        return res[n-1]

# 优化动态规划的空间复杂度
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n ==1 or n ==2:
            return 1
        prev,curr = 1,1
        for i in range(3,n+1):
            sum = prev + curr
            prev = curr
            curr = sum
        return curr

发表于 2022-04-10 22:15:19 回复(0)

Python 3

dubim

class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n<=2:
            return 1
        x,y,z=1,1,2
        while n > 3:
            x,y = y,z
            z = x+y
            n -= 1
        return z

发表于 2022-03-23 13:33:51 回复(0)

提交观点

问题信息

动态规划记忆化搜索数组快速幂递归

来自：寻找时间黑客在线编程大...

难度：

40条回答 1816收藏 208338浏览

通过挑战的用户

查看代码

QLLQL

2023-02-25 11:52:25
牛客79085...

2023-02-19 08:04:38
牛客73350...

2023-02-01 14:40:35
小米内推员

2023-01-19 23:39:10
CUC曾江林

2023-01-13 13:47:09

斐波那契数列

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题