首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列

热度指数：1305350 时间限制：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

输入

输出

算法知识视频讲解

查看答案及解析

JacobGo！

package go.jacob.day1201;

/**
 * 斐波那契数列
 * 
 * @author Administrator 记住两个方法：1.O(n)时间复杂度用循环; 2.O(logn)用矩阵相乘 切记不要用递归
 */
public class Demo2 {
    /*
     * 方法一：循环 时间复杂度O(n)
     */
    public int Fibonacci_1(int n) {
        if (n < 1)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        int res = 1;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }

    /*
     * 结论：F(n)=F(n-1)+F(n-2),是一个二阶递推数列，
     * 一定可以用矩阵乘法的形式表示 
     * 这道题的递推矩阵为[1,1;1,0]
     */
    public int Fibonacci_2(int n) {
        if (n < 1)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        int[][] base = { { 1, 1 }, { 1, 0 } };
        int[][] res = maxtrixPower(base, n - 2);

        return res[0][0] + res[0][1];

    }

    /*
     * 求矩阵m的p次方
     */
    private int[][] maxtrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m.length];
        for (int i = 0; i < m.length; i++) {
            res[i][i] = 1;
        }
        int[][] tmp = m;

        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                res = multiMatrix(res, tmp);
            }
            tmp = multiMatrix(tmp, tmp);
        }

        return res;
    }

    /*
     * 求两个矩阵相乘
     */
    public int[][] multiMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m1[0].length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;

    }

}

发表于 2017-12-01 21:54:34 回复(2)

更多回答

推荐

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)

Java

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

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)

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号

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

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

充分利用之前计算过的数避免重复计算。

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号

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号

# -*- 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)

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

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

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

实现斐波拉契数列步骤：

（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

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

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

跟爬楼梯差不多

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__

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

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

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)

楚地夏忙

class Solution {
    public:
    int Fibonacci(int n) {
        /*if(n<=1) return n;
        return Fibonacci(n-1)+Fibonacci(n-2);*/
        if(n<=1) return n;
        int a[n+1];
        a[0]=0;
        a[1]=1;
        for(int i=2;i<=n;i++)
            a[i]=a[i-1]+a[i-2];
        return a[n];
    }
};

发表于 2020-12-17 20:31:00 回复(0)

提交观点

问题信息

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

来自：2025年春招-中国电...

难度：

2488条回答 1883收藏 223116浏览

通过挑战的用户

查看代码

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

斐波那契数列

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

golang dp数组

问题信息

热门推荐

通过挑战的用户

相关试题