Fibonacci récursif efficace

samedi 10 mars 2018
par  JL
popularité : 4%

La complexité temporelle de tous les algorithmes sauf le dernier est linéaire.

  • Version récursive terminale renvoyant $F_n$ avec seulement deux termes mémorisés :
  1. def fibo_best_term(n, a=0, b=1):
  2.     "Renvoie F_n"""  
  3.     if n == 0 :
  4.         return a
  5.     elif n == 1 :
  6.         return b
  7.     else :
  8.         return fibo_best_term(n - 1, b, a + b)
  9.     # à l'appel de fibo_rec(k, a, b) a contient F_(n-k)
  10.     # et b contient F_(n-k+1).
  • Version tableau :
  1. def fibo_tab(n):
  2.     "Renvoie [F_0,...,F_n]"""
  3.     # La fonction récursive remplit le tableau T des termes.
  4.     def fibo_rec(k, T):
  5.         if k == 0 :
  6.             T[0] = 0 # on remplit avec F_0
  7.         elif k == 1 :
  8.             T[0] = 0 # on remplit avec F_0 et F_1
  9.             T[1] = 1
  10.         else :
  11.             fibo_rec(k - 1, T) # on remplit avec F_0... F_(k - 1)
  12.             T[k] = T[k - 1] + T[k - 2]
  13.            
  14.     T = [1 for i in range(n + 1)]      
  15.     fibo_rec(n, T)
  16.     return T
  • Version liste (à effet de bord) :
  1. def fibo_list(n, L=[]):
  2.     "Renvoie [F_0, ..., F_n]"""
  3.     # La fonction récusrive remplit la liste L des termes.
  4.     def fibo_rec(k, L):
  5.         if k == 0 :
  6.             L.append(0) # on remplit avec F_0
  7.         elif k == 1 :
  8.             L += [0, 1] # on remplit avec F_0 et F_1
  9.         else :
  10.             fibo_rec(k - 1, L) # on remplit avec F_0... F_(k - 1)
  11.             L.append(L[-1] + L[-2])
  12.  
  13.     L = []      
  14.     fibo_rec(n, L)
  15.     return L
  • Version liste (directe) :
  1. def fibo_list_rec(n):
  2.     "Renvoie [F_0, ..., F_n]"""
  3.     if n == 0 :
  4.         return [0]
  5.     elif n == 1 :
  6.         return [0, 1]
  7.     else :
  8.         L = fibo_list_rec(n - 1)
  9.         L.append(L[-1] + L[-2])
  10.         return L
  • Version liste récursive terminale (pas besoin de remonter la pile de récursion, mais pas géré correctement en python) :
  1. def fibo_term(n, L=[0, 1]):
  2.     "Renvoie [F_0, ..., F_n]"""
  3.     if n == 0:
  4.         return [0]
  5.     elif n == 1:
  6.         return L
  7.     else :
  8.         return fibo_term(n - 1, L + [L[-1] + L[-2]])
  9.     # à l'appel de fibo_term(k, L), L contiendra les n + 2 - k premiers
  10.     # termes de la suite
  • Une dernière version par exponentiation rapide matricielle qui donne un coût logarithmique :
  1. def prod(A, B): # produit matriciel naïf en O(n²)
  2.     """produit matriciel"""
  3.     n, m = len(A), len(A[0])
  4.     p, q = len(B), len(B[0])
  5.     assert m == p, "Problème de dimension"
  6.     C = []
  7.     for i in range(n):
  8.         ligne = []
  9.         for j in range(q):
  10.             ligne.append(sum(A[i][k] * B[k][j] for k in range(m)))
  11.         C.append(ligne)
  12.     return C
  13.  
  14. def Id(N):
  15.     "matrice identité de taille N"
  16.     I = [[0] * N for _ in range(N)]
  17.     for i in range(N):
  18.         I[i][i] = 1
  19.     return I
  20.  
  21. def expo_rap_mat(A, n):
  22.     "exponentiaition rapide matricielle"
  23.     N = len(A)
  24.     if n == 0:
  25.         return Id(N)
  26.     A2 = expo_rap_mat(A, n // 2)
  27.     if n % 2 == 0:
  28.         return prod(A2, A2)
  29.     else:
  30.         return prod(A, prod(A2, A2))
  31.  
  32. def fibo_rap(n): # Complexité logarithmique !
  33.     """renvoie F_n"""
  34.     A = [[1, 1], [1, 0]]
  35.     An = expo_rap_mat(A, n - 1)
  36.     return prod(An, [[1], [0]])[0][0]
Script Python - 3.7 ko

Commentaires