首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数：1300241 时间限制：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)
Java
牛客348570162号头像 牛客348570162号 
public int Fibonacci (int n) {
        if(n == 1 || n == 2) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }


发表于 2024-09-18 15:20:28 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        // 算法核心思想：递归回溯

        return process(n);
    }

    public int process(int n) {
        // 递归出口
        if (n == 1 || n == 2) {
            return 1;
        }
        // 分支搜索
        return process(n - 1) + process(n - 2);
    }
}

发表于 2024-09-17 00:17:01 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int Fibonacci (int n) {
        if(n<=2){
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

发表于 2024-08-04 14:26:37 回复(0)
Java
脑子里有糖头像 脑子里有糖
jian1 代表 n-1; jian2 代表n－2；其实如果忘了解法，就画一个树形图，不用多n=4，求解f(4)的图即可，就用简单的赋值，从下往上算。 


public int Fibonacci (int n) {
        // write code here
        int resuslt = 0;
        int jian1 = 0;//n-1
        int jian2 = 0;//n-2
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                jian1  = 1;
                resuslt = jian1;
            } else if (i == 2) {
                jian2 = 1;
                resuslt = jian2;
            } else if (i > 2) {
                resuslt = jian1 + jian2;
                jian2 = jian1;
                jian1 = resuslt;
            }
        }
        return resuslt;
    }
}


发表于 2024-07-29 21:46:56 回复(0)
Java
天界的指挥官头像 天界的指挥官 
public int Fibonacci (int n) {
        // write code here
        if(n == 1 || n ==2){
            return 1;
        }
        int res = 0;
        int s1 = 1;
        int s2 = 1;
        for(int i=3;i<=n;i++){
            res = s1 + s2;
            s1 = s2;
            s2 = res;
        }
        return res;
    }

编辑于 2024-03-30 21:15:57 回复(0)
Java
热血的发呆爱好者头像 热血的发呆爱好者
 public int Fibonacci (int n) {
        // write code here
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
发表于 2024-03-13 20:20:45 回复(0)
Java
不存在的神秘人头像 不存在的神秘人
最简单方法，直接递归 
public int fib(int n){
        if(n==1||n==2) return 1;
        return fib(n-1)+fib(n-2);
     }
    public int Fibonacci (int n) {
        // write code here
    return fib(n);
    }
编辑于 2024-03-13 15:01:33 回复(0)
Java
-Panda君-头像 -Panda君-
f(n)=f(n-1)+f(n-2)
这就转化为了数学上的二阶常系数差分方程，并且为其次方程。
即转化为了求f(n)的值，f(n)=f(n-1)+f(n-2)且f(0)=0; f(1)=1;
特征方程为：x^2-x-1=0
得 x=(1±√5)/2
因而f(n)的通解为:

代码如下，对结果进行下取整，时间复杂度O(1); 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        double squareRoot = Math.sqrt(5);
        double a = (1 + squareRoot) / 2;
        double b = (1 - squareRoot) / 2;
        double res = (1 / squareRoot) * (Math.pow(a, n) - Math.pow(b, n));
        return (int)Math.floor(res);
    }
}

发表于 2024-02-02 11:39:56 回复(0)
Java
煎饼狗子6999头像 煎饼狗子6999 
  if(n<=2){
            return 1;
        }
        else{
            int arr[]=new int[n];
            arr[0]=1;
            arr[1]=1;
            for(int i=2;i<n;i++){
                arr[i]=arr[i-1]+arr[i-2];
            }
            return arr[n-1];
        }比较适合初学者

编辑于 2023-12-15 21:43:52 回复(1)
Java
Alex_L1u头像 Alex_L1u
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        if(n==1 || n==2){
            return 1;
        }

        return Fibonacci(n-1)+Fibonacci(n-2);
       
    }
}
发表于 2023-10-29 17:29:04 回复(0)
Java
Star201902011032173头像 Star201902011032173
动态规划：
public int Fibonacci (int n) {
int[] vec = new int[n+1];
vec[0] = 0;
vec[1] = 1;
if(n == 1) return 1;
vec[2] = 1;
if(n == 2) return 1;
int ans = 0;
for(int i=3;i<n+1;i++){
vec[i] = vec[i-1] + vec[i-2];
}
return vec[n];
}

发表于 2023-08-03 23:53:31 回复(0)
Java
chenyd头像 chenyd
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        int []f = new int[n+1];
        f[1]=1;
        f[2]=1;
        for(int i=3;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }
}
发表于 2023-07-18 11:14:50 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public int Fibonacci (int n) {
        int[] dp=new int[n];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
}

发表于 2023-07-11 16:59:51 回复(0)
Java
只想搞钱___头像 只想搞钱___


import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        for (int i = 0; i <= x; i++) {
            System.out.println(Fibonacci(i));//搞不懂这里为什么提示语法错误，idea里是可以编译通过的，改成i，虽然题错了但能编译通过，什么离谱BUG
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        if(n<=2){
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
发表于 2023-06-15 19:51:39 回复(0)
Java
Zhima1234头像 Zhima1234 
public class Solution {
    public int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        // dp[i]即fib(i)
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}


发表于 2023-05-31 08:46:00 回复(0)
Java
很苦闷头像 很苦闷 
public class Solution {
    public int Fibonacci(int n) {
        if(n==1 ||n==2){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

发表于 2023-05-18 22:37:23 回复(0)
Java
_ther头像 _ther 
public class Solution {
    public int Fibonacci(int n) {
        /* if (n == 1 || n == 2) {
            return 1;
        } */
        return n == 1 || n == 2 ? 1 : Fibonacci(n-1) + Fibonacci(n-2);
    }
}

发表于 2023-05-11 10:22:52 回复(0)
Java
突突不过头像 突突不过
public class Solution {
    public int Fibonacci(int n) {
        if(n==1||n==2){
           return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

发表于 2023-04-24 11:21:56 回复(0)
Java
觉得你很赞的中国人很爱吃鱼头像 觉得你很赞的中国人很爱吃鱼
//动态规划与递归 
public class Solution {
   public int Fibonacci(int n) {
         if(n<=2)
            return 1;
         int []dp=new int[n+1];
         dp[1]=dp[2]=1;
         for(int i=3;i<=n;i++)
            dp[i]=dp[i-1]+dp[i-2];
         return dp[n];
    }
     /*public int Fibonacci(int n) {
         if(n<=2)
            return 1;
         else
          return  Fibonacci(n-1)+Fibonacci(n-2);
    }*/
}
发表于 2023-03-26 12:02:51 回复(0)
Java
贾天龙头像 贾天龙 
public class Solution {
    public int Fibonacci(int n) {
        // 1.递归
        // 2.记录table
        int[] table = new int[n];
        return fib(n, table);
    }

    private int fib(int n, int[]table) {
        // 递归结束条件
        if (n == 1 || n == 2) {
            return 1;
        }
        // 数组中存在，直接返回，避免重复计算
        if (table[n - 1] != 0) {
            return table[n - 1];
        }

        int res = fib(n - 1, table) + fib(n - 2, table);

        // 结果保存进数组，以免重复计算
        table[n - 1] = res;
        return res;
    }
}

发表于 2023-03-07 13:48:05 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 数组 快速幂 递归
来自：2025年春招-中国电...
难度：
358条回答 214810浏览

热门推荐

通过挑战的用户

查看代码

相关试题

斐波那契数列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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