IESN - Fibonacci

fibonacci.py

# L'approche la plus simple pour ce problème serait la suivante, mais elle est inefficace.
# En effet, cette fonction va devoir recalculer toute la séquence pour chaque terme.
def fibonacci_inefficient(n):
    if n == 0: 
        return 0
    elif n == 1: 
        return 1
    else: 
        return fibonacci_inefficient(n-1) + fibonacci_inefficient(n-2)
    
 
# Cette approche est une version revisitée de la première, 
# l'idée est de garder quelque part les termes qui ont déjà été calculés.
def fibonacci_efficient(n, generated_numbers={}):
    if n in generated_numbers:
        return generated_numbers[n]
    elif n > 1:
        return generated_numbers.setdefault(n, fibonacci_efficient(n-1) + fibonacci_efficient(n-2))
    return n

# En comparant ces solutions, vous verrez que la première approche 
# commence déjà à faiblir en performance après seulement quelques dizaine de termes.


# A titre informatif, cette approche est considérée comme la plus "pyhtonique".
# On utilise ici ce qu'on apelle un objet générateur (cfr: https://docs.python.org/fr/3.7/c-api/gen.html )
def fibonacci_yield():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
        
# Pour utiliser cette approche le plus simple est d'utiliser zip(),
# qui va grouper ensemble les éléments ayant la meme position dans chaque objet itérable.
#
# for index, fibonacci_number in zip(range(nb_terms), fibonacci_yield()):
#     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))


valid_input = False
nb_terms = 0
while not valid_input:
    try:
        nb_terms = int(input("Nombre de termes à calculer: "))
    except ValueError:
        print("Vous n'avez pas entré un nombre !")
        continue
    if nb_terms < 0:
        print("Vous devez entrer un nombre positif")
    else:
        valid_input = True

# A titre démonstratif, vous trouverez ci-dessous quelques exemples de formattage de chaine de caractères.
header = "Voici les " + str(nb_terms) + " premiers termes de la suite de fibonacci :"
print('\n' + header)
print("=" * len(header))
for index in range(nb_terms):
    print('{i:3}: {f:5}'.format(i=index, f=fibonacci_efficient(index)))