Une séquence de Fibonacci est «une séquence dans laquelle les deux premiers termes sont 0, 1 et chaque terme suivant est la somme des deux termes immédiatement précédents». ([Wikibedia](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3% À partir de 83% 81% E6% 95% B0))
Séquence de Fibonacci
0
1
1 （0 + 1）
2 （1 + 1）
3 （1 + 2）
5 （2 + 3）
8 （3 + 5）
13 （5 + 8）
Lors de la recherche du nième terme de cette séquence de nombres, s'il est implémenté tel quel, il en sera ainsi.
def fib(n):
"""
Trouvez le nième numéro de Fibonacci à partir de 0.
"""
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
print(fib(7)) # -> 13
Lorsque vous l'exécutez, vous pouvez voir qu'il est ** très lent **. Par exemple, même n = 100 prend un temps considérable.
La raison en est que, bien que les détails soient omis, ** le même calcul est effectué plusieurs fois **. Par exemple, fib (8) peut être obtenu en trouvant fib (7) et fib (6), puis en les additionnant.Toutefois, pour trouver fib (7), il est nécessaire de retrouver fib (6). Il y a.
Accélérons avec le mot clé ** "Ne faites pas deux fois le même calcul" **. Je présenterai deux algorithmes, ** mémorandum ** et ** méthode de planification dynamique **.
Enregistrez le résultat du calcul une fois. Si cela fonctionne, utilisez-le, sinon, calculez-le à nouveau et enregistrez le résultat pour une utilisation future.
MAX_N = 100
MEMO = [None] * (MAX_N + 1) #Tableau pour enregistrer le résultat du calcul
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
#Calculé?
if MEMO[n]:
return MEMO[n]
r = fib(n-1) + fib(n-2)
MEMO[n] = r #Enregistrer le résultat du calcul
return r
print(fib(100))
Même lorsque n = 100, le résultat est revenu immédiatement.
Même si vous n'utilisez pas de fonction récursive, vous pouvez trouver le nombre de Fibonacci en calculant à partir de celui avec le plus petit n.
MAX_N = 100
DP = [None] * (MAX_N + 1) #Tableau pour enregistrer le résultat du calcul
DP[0] = 0 #De la définition
DP[1] = 1 #De la définition
def fib(n):
#Trouvez le nombre de Fibonacci dans l'ordre de 2 à n
for i in range(2, n + 1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
print(fib(100))
Voir le matériel de référence pour la planification dynamique.
Recommended Posts