[Python] Trouver le nombre de Fibonacci à grande vitesse (mémorisation, méthode de planification dynamique)

introduction

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 **.

Note

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éthode de planification dynamique (DP)

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.

Matériel de référence

Recommended Posts

[Python] Trouver le nombre de Fibonacci à grande vitesse (mémorisation, méthode de planification dynamique)
Récurrence de mémorisation et méthode de planification dynamique connue de la séquence Python Fibonacci
[Python] Comment obtenir la fraction d'un nombre naturel à grande vitesse
Effectuez une conversion demi-largeur / pleine largeur à grande vitesse avec Python
[Python] Article qui permet le calcul rapide de matrices éparses
Projet Euler # 2 "Even Fibonacci Number" en Python