斐波纳契数列 fibonacci

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指:

前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

样例
给定 1,返回 0

给定 2,返回 1

给定 10,返回 34

使用递归的话时间运行时间太高

solution

1
2
3
4
5
6
7
8
9
10
11
12
class :
"""
@param: n: an integer
@return: an ineger f(n)
"""
def fibonacci(self, n):
a = 0
b = 1
for i in range(n-1):
a ,b = b ,a+b
return a