题目：https://www.nowcoder.com/ta/coding-interviews

现在要求输入一个整数n；

输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

斐波那契数列 ：

因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

方法1：直接利用递归的方法

这样的方法效率低，存在大量重复计算:

例如，想过要求得f(10)需要先求得f(9)、f(8)；要求得f(9)要先求得f(8)、f(7)…如此等等。在剑指offer中给出了直观的依赖关系树形结构

1
2
3
4
5
6
7
8
class Solution:
    def Fibonacci(self, n):
        if n<=0:
            return 0
        elif n == 1:
            return 1
        else:
            return self.Fibonacci(n-1)+ self.Fibonacci(n-2)#递归调用的写法！！！self.function
1
2
3
method = Solution()
answer = method.Fibonacci(8)
answer
21

解法2：

为了避免重复计算，可以选择从下往上计算，f(0)–>f(1)–>f(2)–>…–>f(10)…以此类推得到第n项。时间复杂度为O(n)。
可以用数组存储，空间复杂度 O(n)；也可以用变量存储，空间复杂度 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution1:
    def Fibonacci(self, n):
        if n<=0:
            return 0
        elif n == 1:
            return 1
        else:
            a = 0
            b = 1
            for i in range(2,n+1):#从第2到n
                b = a + b#更新b（当前非波拉契数列的值）
                a = b - a#a（保留前一个非波拉契数列的值）
            return b
1
2
3
method = Solution1()
answer = method.Fibonacci(8)
answer
21

方法3：利用python的相关特性

1
2
3
4
5
6
7
8
9
10
11
class Solution2:
    def Fibonacci(self, n):
        if n<=0:
            return 0
        if n==1:
            return 1
        else:
            a,b=0,1 
            for i in range(n-1):#循环n-1次
                a,b=b,a+b#a的变化？先计算右边的值再同时赋值给左边
            return b

先将b赋予a；再更新b，跟Solution1中的方法相似

1
2
3
method = Solution2()
answer = method.Fibonacci(3)
answer
2

利用列表来实现是我感觉很赞的方法,最直观明了

1
2
3
4
5
6
7
8
9
10
11
class Solution3():
    def Fibonacci(self, n):
        a = [0, 1]
        if n<=0:
            return a[0]
        if n==1:
            return a[n]
        else:
            for i in range(2, n+1):
                a.append(a[i-1] + a[i-2])
        return a[n]
1
2
3
method = Solution3()
answer = method.Fibonacci(8)
answer
21

参考：

https://blog.csdn.net/fuxuemingzhu/article/details/79501434

https://blog.csdn.net/Datawhale/article/details/82152447

https://doocs.gitee.io/coding-interview/#/docs/coding-interview

1
2