首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1271067 时间限制：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
轩201905211935559头像 轩201905211935559 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        res = 0 
        n1 = 1
        n2 = 1
        if n < 3:
            return 1
        else :
            count = 2
            res = 1
            while count < n :
                  res = n1+n2
                  n1 = n2
                  n2 = res
                  count += 1
        return res
#         return self.Fibonacci(n-1) + self.Fibonacci(n-2)

发表于 2021-11-26 17:07:31 回复(0)
Python
牛客427383779号头像 牛客427383779号
        if n <= 1:
            return n
        else:
            List = [0, 1]
            i = 2
            while i <= n:
                List[0] = List[0] + List[1] # 更新第一项（奇数项）
                List[1] = List[0] + List[1] # 更新第二项（偶数项）
                i += 2 # 一次性更新了两个数
            if n % 2 == 0: # 0(0 1)  2(1 2) 4(3 5) 6(8 13)
                return List[0]
            else:
                return List[1]
发表于 2021-07-13 22:43:14 回复(0)
Python
Keosu头像 Keosu 
class Solution:
    def Fibonacci(self, n):
        a, b = 0, 1
        for _ in range(n):
          a, b = b, a+b
        return a

发表于 2021-07-05 16:49:06 回复(0)
Python
BG4PFQ/QRP头像 BG4PFQ/QRP

我们都知道，斐波那契数列的运行需要用到排序。以下是我的观点（Python 3，使用的是冒泡排序）:

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        s = []
        a = 1
        b = 1
        for x in range(39):
            s.append(a)
            a,b = b,a+b
        if n == 0:
            return 0
        else:
            return s[n-1]

其中，因为 n<=39,所以我们只需要这个数列的前39项。核心代码是在第9行交换数据的部分。
在输入这里因为下标是从0开始，所以需要在返回值这里进行减1处理。
但是，如果输入0那么它的返回值就会成为-1(即，列表的最后一个元素(显示为63245986))，所以当输入值为0时返回值也必须是0才能保证代码的正确实现。
以上就是我的思路，如有疑问或错误，欢迎指正。

发表于 2021-06-19 16:06:56 回复(0)
Python
牛客804608857号头像 牛客804608857号
class Solution:
    def Fibonacci(self, n):
        self.n = n
        return n-1
发表于 2021-06-09 22:43:31 回复(0)
Python
不会说话的412.头像 不会说话的412.
for i in range(n):
            a,b = b,(a+b)
        return a
发表于 2021-05-29 15:32:43 回复(1)
Python
土娃头像 土娃
class Solution:
    def Fibonacci(self,n):
        l=[0]
        self.c, self.a, self.b = 0, 0, 1
        self.n=n
        while self.c < n:
            l.append(self.b)
            #print(b)
            self.a, self.b =self.b, self.a + self.b
            self.c += 1
        return l[-1]
发表于 2021-05-13 17:45:12 回复(0)
Python
本尊不二青年头像 本尊不二青年 
class Solution:
    def Fibonacci(self, n):
        num = []
        for i in range(n+1):
            if i == 0:
                num.append(0)
            elif i == 1:
                num.append(1)
            else:
                num.append(num[-1]+num[-2])
        return num[-1]
1、递归方法，python调试过程中速度太慢没有通过
2、利用for循环语句与数列的方法进行运算，将数列加入列表中，并对最后一个元素进行返回。

发表于 2021-04-19 13:38:06 回复(0)
Python
牛客314674748号头像 牛客314674748号
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 1:
            return n
        lst = [0, 1]
        while n > 1:
            a = lst[0] + lst[1]
            lst[0], lst[1] = lst[1], a
            n -= 1
        return a
发表于 2021-04-16 10:56:32 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        result=[0,1]
        if n<0&nbs***bsp;n>39:
            return False
        else:
            if n<=1:
                return result[n]
            else:
                for i in range(2,n+1):
                    result.append(result[i-1]+result[i-2])
                return result[n]

发表于 2021-04-11 19:50:52 回复(0)
Python
牛客313692148号头像 牛客313692148号
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n<=1:
            return n
        lst = []
        
        lst.append(0)
        lst.append(1)
        for i in range(2,n+1):
            lst.append(lst[i-2]+lst[i-1])
        return lst.pop()
发表于 2021-03-29 17:57:32 回复(0)
Python
牛客622181604号头像 牛客622181604号
class Solution:
    def Fibonacci(self, n):
        # write code here
        f = [0, 1]
        i = 2
        while i < n+2:
            f.append(f[i-1]+f[i-2])
            i += 1
        return f[n]
发表于 2021-03-28 22:55:16 回复(0)
Python
Jiemmy头像 Jiemmy 
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        preNum = 1
        prePreNum = 0
        count = 2
        result = 0
        if n == 0 :
            return 0
        if n == 1 :
            return 1
        while count <= n :
            result = preNum + prePreNum
            prePreNum = preNum
            preNum = result
            count += 1
        return result

发表于 2021-03-27 21:19:29 回复(0)
Python
陌上谁家少年足风流头像 陌上谁家少年足风流
解题思路
首先，斐波那契数列的公式其实就是f(n)=f(n-1)+f(n-2)  (n>=2),这是一个典型的递归，尝试用递归写一下,当n<=1时,直接return n，当其他情况就是直接return f(n-1)+f(n-2),如下 : 
class Solution:
    def Fibonacci(self,n):
        if n<=1:
            return n
        else:
            return self.Fibonacci(n-1)+self.Fibonacci(n-2)
尝试提交，提示代码执行超时，毕竟递归调用复杂，那么不用递归要怎么写，我可不可以定义一个列表，让每次执行完之后，把执行得到的值append进列表里，这样下一次用的时候就不用去计算，可以直接拿来用,这样永远计算的就是LIST[n-1]+LIST[n-2]，如下： 
class Solution:
    def Fibonacci(self,n):
        if n<=1:
            return n
        else:
            lis=[0,1]
            i=2
            while i<=n:
                lis.append(lis[i-1]+lis[i-2])
                i+=1
            return lis[n]


发表于 2021-03-23 14:42:45 回复(0)
Python
牛客729953733号头像 牛客729953733号
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        res = [0,1,1,2]
        if n>len(res)-1:
            for i in range(3,n):
                res.append(res[i]+res[i-1])
        return res[n]
发表于 2021-03-19 16:13:44 回复(0)
Python
西南交大巨可爱头像 西南交大巨可爱 
# python 迭代法
class Solution:
    def Fibonacci(self, n):
        a, b, c= 1, 0, 0
        if not n: return 0
        for i in range(n - 1):
            a, b = a + b , a
        return a

编辑于 2021-03-09 22:57:29 回复(0)
Python
猫牛头像 猫牛 
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n <= 1:
            return n
            
        fn = [0, 1]
        for i in range(2, n+1):
            fn.append(fn[0] + fn[1])
            fn = fn[1:]
        return fn[-1]


发表于 2021-03-08 23:33:13 回复(0)
Python
牛客454249073号头像 牛客454249073号 
方法一：

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0: return 0
        if n == 1: return 1
        else:
            a_n_1, a_n_2 = 1, 0
            for i in range(1, n):
                a_n = a_n_1 + a_n_2
                a_n_1, a_n_2 = a_n, a_n_1
            return a_n


方法二：
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        num_list = [0,1]
        if n<2: return num_list[n]
        for i in range(2, n+1):
            num_list.append(num_list[-1]+num_list[-2])
        return num_list[n] 

编辑于 2021-05-27 11:45:20 回复(4)
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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