斐波那契数列的计算

发表于 | 阅读次数:
字数统计: 331 | 阅读时长 ≈ 1

python 使用numpy的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import numpy as np

"""
    使用numpy的做法
    
"""


def fib_matrix(n):
    res = pow((np.matrix([[1, 1], [1, 0]])), n) * np.matrix([[1], [0]])
    return res[0][0]


for i in range(10):
    print(int(fib_matrix(i)), end=' ')

### 2
# 使用矩阵计算斐波那契数列
def Fibonacci_Matrix_tool(n):
    Matrix = np.matrix("1 1;1 0")
    # 返回是matrix类型
    return pow(Matrix, n)  # pow函数速度快于 使用双星好 **

def Fibonacci_Matrix(n):
    result_list = []
    for i in range(0, n):
        result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
    return result_list
# 调用
# Fibonacci_Matrix(10)

标准库的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# encoding=utf-8

from functools import reduce


"""
   标准库的做法
"""


class Solution(object):
    # 矩阵相乘
    def mul(self, a, b):
        r = [[0, 0], [0, 0]]
        r[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0]
        r[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1]
        r[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0]
        r[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1]
        return r

    # 递归加速计算斐波那契数列 O(n^2) -> O(logn)
    def helper(self, n):
        if n == 0:
            return [[1, 0], [0, 1]]
        if n == 1:
            return [[1, 1], [1, 0]]
        if n&1 == 0 :
            return self.mul(self.helper(n/2), self.helper(n/2))
        else:
            return reduce(self.mul,[self.helper((n-1)/ 2),self.helper((n-1)/ 2),[[1, 1], [1, 0]]])
        
    def fib(self, N):
        return self.helper(N-1)[0][0]


if __name__ == "__main__":
    for i in range(1, 11):
        print(i-1, Solution().fib(i))