面试题10-斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。（n<=39）
斐波那契数列公式为：

我们以求解f(10)为例类分析递归的求解过程。想求f(10)，需要先求得f(9)和f(8)。同样，想求得f(9)，需要先求的f(8)和f(7)…我们可以用树形结构来表示这种依赖关系，如下图所示：

我们不难发现在这棵树中有很多节点是重复的，而且重复的结点数会随着n的增加而急剧增加，这意味计算量会随着n的增加而急剧增大。事实上，递归方法计算的时间复杂度是以n的指数的方式递增的。

#include
using namespace std;
//递归
long long Fibonacci(unsigned int n)
{
	if (n <= 0)
		return 0;
	if (n == 1)
		return 1;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}
//循环
long long Fibonacci1(unsigned n)
{
	int result[2] = { 0,1 };
	if (n < 2)
		return result[n];
	long long fibNMinusOne = 1;
	long long fibNMinusTwo = 0;
	long long fibN = 0;
	for (unsigned int i = 2; i <= n; ++i)
	{
		fibN = fibNMinusOne + fibNMinusTwo;
		fibNMinusTwo = fibNMinusOne;
		fibNMinusOne = fibN;
	}
	return fibN;
}
int main() {
	cout << "3的斐波那契数列是：" << Fibonacci(3) << endl;
	cout << "10的斐波那契数列是：" << Fibonacci(10) << endl;
	cout << "0的斐波那契数列是：" << Fibonacci(0) << endl;
	cout << "1的斐波那契数列是：" << Fibonacci(1) << endl;
	cout << "2的斐波那契数列是："< 
Python实现 
class Solution:
    def Fibonacci(self,n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            fibNMinusOne, fibNMinusTwo, fibN = 1, 0, 0
            for i in range(2,n+1):
                fibN = fibNMinusOne + fibNMinusTwo
                fibNMinusTwo = fibNMinusOne
                fibNMinusOne = fibN
            return fibN

# 测试
if __name__ == "__main__":
    s = Solution()
    res=s.Fibonacci(3)
    print(res)
 
测试用例 
功能测试（如输入3/5、10等）
边界值测试（如输入0,、1、2）
性能测试（输入较大的数字，如40、50、100等）