1、题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
2、思路
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。
原文：https://blog.csdn.net/l18637220680/article/details/80382301
递归方法时间复杂度比循环要高
3、C++实现
class Solution { public: int Fibonacci(int n) { //int result = {0,1}; long f0=0, f1=1; long fn; if(n<1){ return 0; }else if(n<2) { return 1; }else{ for(int i=2;i<=n;i++) { fn=f1+f0; f0 = f1; f1 = fn; } return fn; } } }; |
4、写的有点冗余了，参考下牛客的代码
class Solution { public: int Fibonacci(int n) { int first = 0; int second = 1;
int result = n; for(int i = 2; i<=n; i++){ result = first + second; first = second; second = result; } return result; } }; |