题目描述
斐波那契数列：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。
思路一
利用函数的递归来做。将第0个到第n个裴波那契数列元素都求出来，存在数组中。
代码
class Solution {
public:
int Fibonacci(int n) {
int Fibonacci_array[n];
Fibonacci_array[0] = 0;
Fibonacci_array[1] = 1;
for(int i = 2; i <= n; i++){
Fibonacci_array[i] = Fibonacci_array[i-1] + Fibonacci_array[i-2];
}
return Fibonacci_array[n];
}
}
思路二
用三个变量，第一个变量和第二个变量分别存放0、1两个值，第三个变量用来存放前两项的相加值。
class Solution {
public:
int Fibonacci(int n) {
int first = 0,
second = 1,
result = 1;
if (n < 2) {
return n;
}
for (int i = 2;i < n;i ++){
first = second;
second = result;
result = first + second;
}
return result;
}
}
