题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。

n<=39

 

这个题目大家在学编程的时候都应该遇到过,但是不能够使用递归解法,因为如果使用递归,就会超出时间,算法的复杂度是2^n。因此这里采用迭代的解法。

代码如下所示:

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n==1:
        
            return 1
        if n==0:
            return 0

        a=1
        b=0
        ret=0
        for i in range(0,n-1):
            ret=a+b
            b=a
            a=ret
        return ret

 

内容来源于网络如有侵权请私信删除