pythonフィボナッチ数列の計算方法
タイトル:
フィボナッチの数列を計算します。具体的にはフィボナッチの数列は0、1、1、2、3、5、8、13、21、34、55、89、144、233です。
要求:
時間の複雑さはできるだけ少ないです。
分析:
三つの方法を示した。
方法1:再帰的な方法は、ここでは空間の複雑さが非常に大きい。再帰層数が非常に多い場合、pythonでは、解釈器のデフォルトの再帰的深さを調整する必要がある。デフォルトの再帰的深さは1000です。私は長い間コードを調整しましたが、1000に再帰したので、もう私のパソコンのメモリが足りなくなりました。
方法2:再帰を反復に変えて、時間の複雑さもコードに表記されています。
方法3:この方法はべき乗の簡便性を利用してビット演算を採用した。しかし、対価はマトリックスを作成し、マトリックス演算を行う必要があります。したがって、当所が求めている数列の数は時間よりも少なく、この方法はまだ第二の簡単さを持っていません。しかし、インデックス値nがスーパー大きい場合、この方法は非常に便利です。時間の複雑さがコードに表記されています。
コード:
フィボナッチの数列を計算します。具体的にはフィボナッチの数列は0、1、1、2、3、5、8、13、21、34、55、89、144、233です。
要求:
時間の複雑さはできるだけ少ないです。
分析:
三つの方法を示した。
方法1:再帰的な方法は、ここでは空間の複雑さが非常に大きい。再帰層数が非常に多い場合、pythonでは、解釈器のデフォルトの再帰的深さを調整する必要がある。デフォルトの再帰的深さは1000です。私は長い間コードを調整しましたが、1000に再帰したので、もう私のパソコンのメモリが足りなくなりました。
方法2:再帰を反復に変えて、時間の複雑さもコードに表記されています。
方法3:この方法はべき乗の簡便性を利用してビット演算を採用した。しかし、対価はマトリックスを作成し、マトリックス演算を行う必要があります。したがって、当所が求めている数列の数は時間よりも少なく、この方法はまだ第二の簡単さを持っていません。しかし、インデックス値nがスーパー大きい場合、この方法は非常に便利です。時間の複雑さがコードに表記されています。
コード:
#!usr/bin/python2.7
# -*- coding=utf8 -*-
# @Time : 18-1-3 2:53
# @Author : Cecil Charlie
import sys
import copy
sys.setrecursionlimit(1000) #
class Fibonacci(object):
def __init__(self):
pass
def fibonacci1(self, n):
'''
, o(2**n),
:param n: n
:return: n
'''
if n < 1:
return 0
if n == 1 or n == 2:
return 1
return self.fibonacci1(n-1) + self.fibonacci1(n-2)
@staticmethod
def fibonacci2(n):
"""
, , o(n)
"""
if n < 1:
return 0
if n == 1 or n == 2:
return 1
res = 1
tmp1 = 0
tmp2 = 1
for _ in xrange(1, n):
res = tmp1 + tmp2
tmp1 = tmp2
tmp2 = res
return res
def fibonacci3(self, n):
"""
, , o(log n), , , . 。
"""
base = [[1, 1], [1, 0]]
if n < 1:
return 0
if n == 1 or n == 2:
return 1
res = self.__matrix_power(base, n-2)
return res[0][0] + res[1][0]
def __matrix_power(self, mat, n):
"""
"""
if len(mat) != len(mat[0]):
raise ValueError("The length of m and n is different.")
if n < 0 or str(type(n)) != "<type 'int'>":
raise ValueError("The power is unsuitable.")
product, tmp = [], []
for _ in xrange(len(mat)):
tmp.append(0)
for _ in xrange(len(mat)):
product.append(copy.deepcopy(tmp))
for _ in xrange(len(mat)):
product[_][_] = 1
tmp = mat
while n > 0:
if (n & 1) != 0: # , 1 , ,
product = self.__multiply_matrix(product, tmp)
tmp = self.__multiply_matrix(tmp, tmp)
n >>= 1
return product
@staticmethod
def __multiply_matrix(mat1, mat2):
"""
:param m: 1,
:param n: 2
:return:
"""
if len(mat1[0]) != len(mat2):
raise ValueError("Can not compute the product of mat1 and mat2.")
product, tmp = [], []
for _ in xrange(len(mat2[0])):
tmp.append(0)
for _ in xrange(len(mat1)):
product.append(copy.deepcopy(tmp))
for i in xrange(0, len(mat1)):
for j in xrange(0, len(mat2[0])):
for k in xrange(0, len(mat1[0])):
if mat1[i][k] != 0 and mat2[k][j] != 0:
product[i][j] += mat1[i][k] * mat2[k][j]
return product
f = Fibonacci()
print f.fibonacci1(23)
print f.fibonacci2(23)
mat1 = [[2,4,5],[1,0,2],[4,6,9]]
mat2 = [[2,9],[1,0],[5,7]]
print f.fibonacci3(23)
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。