C16.3 : Suite de Fibonacci

Rappel sur la suite de Fibonacci

La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Le terme d'indice 0 est 0 et le terme d'indice 1 et 1.

Ainsi, les premiers termes de la suite sont : 0, 1, 1, 2, 3, 5, 8, 13, 21...

Programmation de la suite de Fibonacci

Programmation récursive

1) Écrire une fonction fibo_rec(n) qui prend un nombre entier n en paramètre et renvoie la valeur du n^ième terme de la suite de Fibonacci.

2) Construire, sous la forme d'un arbre, la pile des appels successifs à la fonction.

3) Pourquoi peut-on affirmer que cet algorithme n'est pas optimal ?

def fibo_rec(n:int)-> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibo_rec(n-1) + fibo_rec(n-2)

print(fibo_rec(30))

Programmation récursive dynamique, méthode descendante (top-down)

Ici, on s'appuiera sur le raisonnement récursif précédent, tout en utilisant un dictionnaire dont les clés sont les indices des termes de la suite et les valeurs, les valeurs des termes de la suite.

La fonction fibo_dyn_desc(n, dico) aura donc deux paramètres, l'indice du terme recherché et le dictionnaire des termes déjà calculés.

1) Écrire le code de la fonction.

2) Quel est le coût de cet algorithme ?

def fibo_dyn_desc(n:int, dico:dict) -> int:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        if n-1 not in dico:
            dico[n-1] = fibo_dyn_desc(n-1, dico)
        if n-2 not in dico:
            dico[n-2] = fibo_dyn_desc(n-2, dico)
        return dico[n-1] + dico[n-2]

# Autre version
def fibo_dyn_desc_v2(n, dico):
    if n == 0 or n == 1:
        return n
    else:
        if n not in dico:
            dico[n] = fibo_dyn_desc_v2(n-1, dico) + fibo_dyn_desc_v2(n-2, dico)
        return dico[n]
# ===== Programme principal =====
for n in range(20):
    print(n, ':', fibo_dyn_desc(n,{}))

Programmation dynamique itérative, méthode ascendante (bottom-up)

Ici, on calcul les termes de la suite itérativement de 0 à n en stockant les valeurs dans une liste.

1) Écrire la fonction fibo_dyn_asc(n) qui prend un nombre entier n en paramètre et renvoie la valeur du n^ième terme de la suite.

2) Quel est le coût de cet algorithme ?

def fibo_dyn_asc(n:int) -> int:
    li_fibo = [0, 1]
    i = 2
    while i <= n:
        li_fibo.append(li_fibo[i-1] + li_fibo[i-2])
        i = i + 1
    return li_fibo[n]

# Autre version
def fibo_dyn_asc(n):
    li_fibo = [0, 1]
    for n in range(2, n+1):
        li_fibo.append(li_fibo[n-1] + li_fibo[n-2])
    return li_fibo[n]


# ===== Programme principal =====
for n in range(21):
    print(n, ':', fibo_dyn_asc(n))