package jianzhiOffer;
/**
* 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
* @author user
*思路：既然n的大小有限制，就用递归来解决
* 0 1 1 2 3 5 8...
*非递归方式也可以实现，采用数组存储的方式
*/
public class ch07 {
//递归实现
public static int Fibonacci(int n) {
if(n < 0) {
return -1;
} else if(n == 0) {
return 0;
} else if(n == 1) {
return 1;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
//非递归实现
public static int Fibonacci2(int n) {
if(n < 0) {
return -1;
} else if(n == 0) {
return 0;
} else if(n <= 2) {
return 1;
} else {
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 3; i <= n; i++) {
arr[i - 1] = arr[i - 2] + arr[i - 3];
}
return arr[n - 1];
}
}
public static void main(String[] args) {
// int result = Fibonacci(5);
int result = Fibonacci2(3);
System.out.println(result);
}
}
剑指offer07
原文：http://blog.51cto.com/12222886/2060632
