首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列
  • 热度指数:1268550 时间限制: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)
 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)
最简单方法,直接递归 
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)
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)
  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)
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)
动态规划:
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)
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)
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)


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)
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)
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)
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)
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)
//动态规划与递归
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)
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)
public class Solution {
    public int Fibonacci(int n) {
        if(0==n){
            return n;
        }
       
        int first = 1;
        int second = 1;
        int third = 1;
        while(n>2){
            third = first + second;
            first = second;
            second = third;
            n--;
        }
        return third;
    }
}

发表于 2023-02-04 22:54:22 回复(0)
我的解法是  初始化前两个数,从第3个数开始向n个位置移动 相加
具体解法如下
public class Solution {
    public int Fibonacci(int n) {
        if(n <= 2){
            return 1;
        }

        // 初始化前两个数
        int pre = 1, last = 1;
        // temp用于存储每次相加后的新数
        int temp;
        for(int i = 2; i < n; i++){
            // 得到下一个数
            temp = pre + last;

            // 下面两步即为向后移动

            // pre等于last 
            pre = last;
            // last等于当前计算好的下一个数
            last = temp;
        }

        // 最终返回last
        return last;

    }
}


发表于 2022-10-25 01:32:34 回复(0)
public class Solution {
    public int Fibonacci(int n) {
        int first = 1;
        int second = 1;
        int third = 2;
        for (int i = 3; i < n; i++) {
            first = second;
            second = third;
            third = first + second;
        }
        return n == 1 ? 1 : n == 2 ? 1 : third;
    }
}

发表于 2022-10-14 14:51:17 回复(0)
public class Solution {
    public int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
发表于 2022-09-08 16:42:56 回复(0)