题目描述
大家都知道斐波那契数列,现在要求输入一个整数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
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!