Fibonacci数列代码实现
斐波那契数列
http://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3
public class Solution {
//解法一 递归(不考虑效率与内存)
public int FibonacciA(int n) {
if(n == 0 || n == 1){
return n;
}
if(n <= 39){
return Fibonacci(n-1) + Fibonacci(n-2);
}
return -1;
}
//解法二 效率提高了，内存占用还是大
public int FibonacciB(int n) {
if( n > 39 || n < 0){
return -1;
}
int answer[] = new int[n];
answer[0] = 0;
answer[1] = 1;
for(int i = 2;i <= n;i++){
answer[i] = answer[i-1] + answer[i-2];
}
return answer[n];
}
//解法三 内存占用还是大
public int FibonacciC(int n) {
if( n > 39 || n < 0){
return -1;
}
if(n == 0 || n == 1){
return n;
}
int result = 0;
int temp1 = 0;
int temp2 = 1;
for(int i = 2;i <= n; i++){
result = temp1 + temp2;
temp1 = temp2;
temp2 = result;
}
return result;
}
//解法四，与三类似，只是少了一个变量
public int FibonacciD(int n) {
if( n > 39 || n < 0){
return -1;
}
if(n == 0 || n == 1){
return n;
}
int result = 1;
int temp1 = 0;
for(int i = 2;i <= n; i++){
result = result + temp1;
temp1 = result - temp1;
}
return result;
}
//解法五 直接使用高中学过的Fibonacci数列的通项公式，或者利用学过的知识推导一下下，反正我不会。
public int FibonacciE(int n) {
double a = Math.sqrt(5.0);
double temp1 = (1.0 + a)/2.0;
double temp2 = (1.0 - a)/2.0;
return (int)(1.0/a*(Math.pow(temp1, n) - Math.pow(temp2, n)));
}
}
推导过程如下(百度的)：
