首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数:1268449 时间限制: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
推荐
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)
class Solution {
public:
    int Fibonacci(int n) {
        // 时间复杂度O(N),空间复杂度O(1)
        int dp1 = 1, dp2 = 1, dp3 = 1;
        for (int i = 3; i <= n; ++i) {
            dp3 = dp1 + dp2;
            dp1 = dp2;
            dp2 = dp3;
        }
        return dp3;
    }
};

发表于 2022-08-10 23:27:27 回复(0)
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)
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)
递归+记忆化=动态规划
第一步:递归
递归循环 : 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)

废话不多说,直接上代码

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)
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)
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)
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)
充分利用之前计算过的数避免重复计算。
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)
int Fibonacci(int n ) {
    // write code here
    int i=3,y,y1=1,y2=1;
    if(n==1 || n==2){return 1;}
    else {
        while(i<=n){y=y1+y2;y1=y2;y2=y;i++;}
        return y;}
}
发表于 2021-11-14 16:37:52 回复(0)
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)
# -*- 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)
/**
 * 
 * @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)
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)
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)
实现斐波拉契数列步骤:
(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)
function Fibonacci(n)
{
    let [a, b] = [0, 1];
    while (n--) {
        b += a;
        a = b - a;
    }
    return a;
}

编辑于 2021-03-29 14:50:59 回复(0)
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)
跟爬楼梯差不多
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)
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)