版权声明：本文为博主原创文章，未经博主允许不得转载。
难度：容易
要求：
查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
思路：
题目较简单，需要注意的是 输入参数N是1~N，比较常用思路是递归
方法一：无脑循环法
class Solution {
/**
* @param n: an integer
* @return an integer f(n)
*/
public int fibonacci(int n) {
if(n == 1){
return 0;
}
if(n == 2){
return 1;
}
int f1 = 0;
int f2 = 1;
int tmp = 0;
for(int i = 0; i < n - 2; i++){
tmp = f1 + f2;
f1 = f2;
f2 = tmp;
}
return f2;
}
}
方法二：递归 比较遗憾的是递归耗时比无脑循环多
class Solution{
/**
* @param n: an integer
* @return an integer f(n)
*/
public int fibonacci(int n) {
if ( n == 1 ) {
return 0;
} else if ( n == 2 || n == 3 ) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
