二级网站模板/打广告

题目描述

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

题解

首先是斐波那契数列，除了第一项和第二项，所有的数列的值都是前一项和前一项的前一项的加和，转换成函数也就是f(n) = f(n-1) + f(n-2)：

第0项：0
第1项：1
第2项：1
第3项：2
…
…
第n项：f(n) = f(n-1) + f(n-2)

看到这里首先想到的就是递归算法：

# -*- coding:utf-8 -*-
class Solution:def Fibonacci(self, n):# write code hereif n == 0:return 0elif n == 1:return 1else:sum = self.Fibonacci(n - 1) + self.Fibonacci(n - 2)return sum

但是提交代码后发现超时了，下面是非递归写法，循环过程中，将 (n-1)和(n-2)的值加到 sum 中，并刷新 (n-1)和(n-2)的值：

# -*- coding:utf-8 -*-
class Solution:def Fibonacci(self, n):# write code hereif n == 0:return 0elif n == 1:return 1else:sum = 0n0 = 0n1 = 1for i in range(2,n+1):sum = n0 + n1n0 = n1n1 = sumreturn sum