斐波那契数列--python

什么是斐波那契数列：

斐波那契数列为0,、1、1、2、3、5、8、13、21、34……此数列从第3项（也就是n=2）开始，每一项都等于前两项之和，总结得到以下的递推公式:

  #前两项
  n = 0,num = 0
  n = 1,num = 1
  n > 1,f(n) = f(n-1) + f(n-2)

得到递推公式，接下来就是如何用代码实现了，前两项直接返回结果即可，研究一下递推公式，
1、可使用递归方式，代码部分如下:

class Solution():
    def Fibonacci(self,n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
        #f(n) = f(n-1)+f(n-2)
            num = self.Fibonacci(n-1) + self.Fibonacci(n-2)
            return num
if __name__ == '__main__':
    s = Solution()
    print(s.Fibonacci(4))

2、使用递归方式时耗时较多，考虑优化，经过计算，我们可知本项为前两项之和，以此递进，可使用a,b代替f(n-2),f(n-1),本项f(n) = a + b,求下一项n+1时，则a = f(n-1) = b,b = f(n)
代码实习如下：

def Fibonacci(self,n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a,b = 0,1
        while n > 1:
            num = a + b
            a = b
            b = num
            n -= 1
        return num

对你有帮助的话就点个赞吧！