[剑指Offer]斐波那契数列

斐波那契数列

:$a_0=0$不是斐波那契数列的第一项,而是第零项。

题目描述

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

解题思路

只需注意斐波那契数列的第零项即可。

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
a = [1, 1]
if n < 0:
return
elif n == 0:
return 0
else:
length = 2
while length < n:
a.append(a[-1] + a[-2])
length += 1
return a[n - 1]

运行时间:27ms
占用内存:5756k
:实现斐波那契数列不一定需要使用列表,只是使用列表可以把数列完全存储下来,如果只需要某一项的值,完全可以:

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a