《程序猿笔试题系列》之斐波那契数列

JAVA的学习之路 2021-03-21

479

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n\leq 39 n<=39.

示例

输入
   4
输出
   3

思路分析

对于这个题目来说，首先是大家是先要搞清楚，斐波那契数列是啥，可能一开始做这个题的时候，一下子有点懵，忘记了什么是斐波那契数列了。下面给大家回顾一下：

指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

根据这个定义可以很容易的使用递归做出来了。

 public int Fibonacci(int n) {
        if(n==0||n==1){
            return n;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }

发现这种的话，算法复杂度都比较高，如果大家了解动态规划的话，可以直接使用动态规划来做这个题目。使用3个变量来保存值。

   /**
     * 
     * 时间复杂度：O（n）
     * 空间复杂度：O（1）
     */
    public static int Fibonacci2(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = a+b;
            a=b;
            b=c;
        }
        return c;
    }