[名企面试知识点][Java]斐波那契数列
发布于 2017-03-07 13:39 2440 次浏览 0 赞 来自 笔试面试  

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。

输入描述

一个整数n

输出描述

斐波那契数列的第n项。

题目分析

什么是斐波那契数列?

  

斐波那契数列(Fibonacci sequence),又称黄金分割数列

在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)  

指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、…… 

递归?

  看到这个的第一想法就是用递归,当n<2时返回n,n>=2时返回f(n-1)+f(n-2), 于是就来试一下...   

public class Solution {
   public int Fibonacci(int n) {
       if(n<2){
           return n;
       }

       return Fibonacci(n-1)+Fibonacci(n-2);
   }
}

运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。

为什么呢?

  因为重复计算,比如:

f(4) = f(3) + f(2);
     = f(2) + f(1) + f(1) + f(0);
     = f(1) + f(0) + f(1) + f(1) + f(0);

求f(4)就要计算三次f(1)和两次f(0),显然这是不行的。

解法 (动态规划)

运行时间:27ms 占用内存:629k

public class Solution {
   public int Fibonacci(int n) {
        int i = 0, j = 1;
        for(;n>0;n--){
           j += i;
           i = j-i;
       }
       return i;
   }
}

根据n的大小,从f(0)=i 和 f(1)=j 从头开始遍历整个序列

有f(n)=f(n-1)+f(n-2) (n≥2,n∈N*)

j+=i, 使j成为新的f(n-1) i = j-i ,使i成为f(n-2)

完成后,返回 f(n-2)

注意:java中

while(n--)

会报编译错误:

required: boolean found: int


添加回复
回到顶部