斐波那契数列

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

分析

斐波那契数列公式：F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2),(n>=3,n∈N*);

递归法

递归是最简单的实现方式，但是递归的缺点是不考虑时间复杂度和内存问题。

代码

public int Fibonacci1(int n){ if(n <= 1){ return n; } return Fibonacci1(n-1) + Fibonacci1(n-2); }

优化递归

递归会重复计算大量的数据，既占用大量内存又耗费时间，优化递归的第一种方式是以内存换取时间，用数组将数列存起来，时间更快，但是内存会变大。

优化代码一

public int Fibonacci2(int n){ int[] ans = new int[40];//n<=39,一共40个数； ans[0] = 0; ans[1] = 1; for(int i = 2; i <= n; i++){ ans[i] = ans[i-1] + ans[i-2]; } return ans[n]; }

优化存储

将数列存储到数组后，虽然减少了递归耗费的大量时间，但却耗费了大量的内存，现将数组去掉继续对代码进行优化，减少占用的内存。

优化代码二

public int Fibonacci3(int n){ if(n <= 1){ return n; } int sum = 1; int one = 0; for(int i = 2; i <= n; i++){ sum = sum + one; one = sum - one;//很巧妙； } return sum; }

优化二的代码很巧妙，个人最喜欢！