Dans le cours, il était nécessaire d'écrire un algorithme de complexité logarithmique, qui trouvera le Nième nombre de la séquence de Fibonacci.
Algorithme
J'ai trouvé plusieurs articles sur ce sujet, tous traitant de la série classique des nombres de Fibonacci. Pour lui, vous pouvez appliquer cette formule:
Mais dans mon travail, des séries généralisées ont été utilisées, dans lesquelles les deux premiers nombres sont zéro et un paramètre. Après des heures de recherche, je suis tombé sur un commentaire intéressant dans lequel l'auteur donne une formule pour la découverte cyclique de toute séquence linéaire récurrente (y compris une série de nombres de Fibonacci).
Ici Q est une matrice 2x2 dont les éléments peuvent être facilement calculés.
En substituant quelques nombres de Fibonacci, nous découvrons que la matrice Q = [[0,1], [1,1]].
La formule finale de la matrice, qui contient le N-ième nombre de la série généralisée de Fibonacci, peut s'écrire comme suit:
Fn est le nombre de Fibonacci souhaité,
C est la clé,
n est le nombre ordinal du nombre
Évidemment, pour l'efficacité de l'ensemble de l'algorithme, il est nécessaire d'utiliser l'algorithme le plus rapide pour élever la matrice Q à la puissance n.Cet article m'a aidé à faire face à cela. Cela explique que pour élever une matrice à la puissance n, vous pouvez diviser n en puissances de deux, puis élever les matrices uniquement à ces puissances. Cette approche donne la complexité O (log N).
Ensuite, il ne reste plus qu'à multiplier par la matrice [[C, C], [C, 0]] et obtenir l'élément d'indice [0,1].
Implémentation Python
class FiboMatrix:
key = 0
matrix_cur = [[0,0], [0,0]]
matrix_one = [[0,1], [1,1]]
def __init__(self, key):
self.key = key
self.matrix_cur = [[key, key], [key, 0]]
self.PowsBuffer = {}
#
def MultiplyMatrix(self, M1, M2):
"""
2x2 ."""
a11 = M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0]
a12 = M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1]
a21 = M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0]
a22 = M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]
return [[a11, a12], [a21, a22]]
def PowMatrix(self, M: list, p: int):
""" .
2x2 .
"""
if p == 1:
return M
if p in self.PowsBuffer:
return self.PowsBuffer[p]
K = self.PowMatrix(M, int(p / 2))
R = self.MultiplyMatrix(K, K)
self.PowsBuffer[p] = R
return R
def GetNum(self, n):
if n == 0:
return 0
if n == 1:
return 1
# n
powers = []
p = 0
for digit in reversed(bin(n)[2:]):
if digit == '1':
powers.append(int(pow(2, p)))
p += 1
matrices = [self.PowMatrix(FiboMatrix.matrix_one, p)
for p in powers]
#
while len(matrices) > 1:
M1 = matrices.pop()
M2 = matrices.pop()
R = self.MultiplyMatrix(M1, M2)
#
matrices.append(R)
self.matrix_cur = self.MultiplyMatrix(self.matrix_cur, matrices[0])
# F1 F2 ,
return self.matrix_cur[0][1]
Pour comparer l'efficacité, l'analogue le plus simple de cet algorithme a été écrit en utilisant une boucle:
def Fib(num, key):
fib_1 = 0
fib_2 = key
for dec in range(num):
fib_1, fib_2 = fib_2, fib_1+fib_2
return fib_2
Les benchmarks confirment nos attentes: l'algorithme classique prend déjà plusieurs fois plus de temps au 10 000e nombre.
