1.题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39.
2.算法分析
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。
该算法可以通过两种方式解决，一种是常规的规律法，另一种是递归算法。
3.代码实例
常规算法
public static int Fibo(int n) {
if (n < 1)
return 1;
int n1 = 1;
int n2 = 1;
int result = 0;
for (int i = 2; i <= n; i++){
result = n1 + n2;
n1 = n2;
n2 = result;
}
return result;
}
递归算法
public static int Fibo(int n) {
if (n <= 1) {
return 1;
}else {
return Fibo2(n - 1) + Fibo2(n - 2);
}
}
