Python实现斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。

n<=39

        见到题目很自然联想到用递归或是用数组将前面的结果全部存储起来(这个想法其实和递归没区别),写起来最简单。但实际写出来发现不现实,运行效率太低,提交答案的时候果然提示超出要求时间,程序太过复杂。查阅答案的时候才发现一个很巧妙的方法(主要还是自己太笨了脑筋不会拐弯=.=||),其实F(n)=F(n-1)+F(n-2),也就是说整个运算过程其实只用保存两个数值即可计算出所需结果,并不需要保存前面的全部结果。2个数值,就应该联想到通过模2来存取数值(写到这里愈发觉得自己是个猪头),这样大大提高了效率,降低了存储空间。

        其次是在实现过程中要注意一个小问题,最开始本猪写的是for i in range(2,n),后来发现答案全错了,原来是因为n=2时,range(2,2)为0,并不会运算下面的值,所以需要多算一位。

# -*- coding:utf-8 -*-

class Solution:

    def __init__(self):

        self.temp_Array = [0,1]

    def Fibonacci(self, n):

        if type(n) != int or n <= 0:

            return False

        elif n == 1:

            return 1

        else:

            for i in range(2,n+1):

                self.temp_Array[i%2] = self.temp_Array[0]+self.temp_Array[1]

            return self.temp_Array[n%2]

你可能感兴趣的