Mémorandum Python (algorithme)

Un rappel pour réapprendre Python à partir de zéro. Je voudrais obtenir des résultats qui s'attaquent aux problèmes fondamentaux.

Séquence de Fibonacci

Créez un programme d'affichage des résultats pour la séquence de Fibonacci. Au fait, le fonctionnaire est

a_{1} = a_{2} = 1 \\ 
a_{n+2} = a_{n+1} + a_{n}\;\;\;\;\;(n >= 1) 

Est.

Ecrire comme officiel

fibonacci_simple.py

#La formule de la séquence de Fibonacci est la suivante.
#À ce stade, la fonction fibonacci est appelée plusieurs fois pour obtenir la valeur numérique de n.
#Par conséquent, l'algorithme est simple, mais le traitement est lent.
import time 


def fibonacci_simple(n):
    if (n == 1) or (n == 2):
        return 1
    return fibonacci_simple(n - 2) + fibonacci_simple(n - 1)


start = time.time()
print(fibonacci_simple(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Par conséquent

6765
elapsed_time:0.002089977264404297[sec]

Essayez d'en faire un processus à grande vitesse par mémo

fibonacci_memo.py

#Accélérez le traitement en prenant des notes.
#La valeur du tableau conditionnel est placée dans le tableau associatif appelé mémo.
#mémo S'il y en a toujours, ça se termine. Sinon, calculez et insérez dans le mémo
#Le même calcul peut être éliminé.
import time


memo = {1: 1, 2: 1}
def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1)
    return memo[n]


start = time.time()
print(fibonacci_memo(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Par conséquent

6765
elapsed_time:0.0002808570861816406[sec]

Essayez d'utiliser une boucle

fibonacci_loop.py

#Utilisez une boucle pour le trouver.
import time


def fibonacci_loop(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i -2] + fib[i - 1])
        
    return fib[n - 1]


start = time.time()
print(fibonacci_loop(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Par conséquent

6765
elapsed_time:0.00026702880859375[sec]

Si vous comparez

Il est étonnant que le temps de traitement puisse être réduit à 1/10 simplement en réduisant la quantité de calcul en double par rapport au calcul simple.