Suite de Fibonacci : encore un algorithme

Voici le programme complété pour la technique récursive : <sxh python; title : fibonacci07_fonction_recursive.py> #! /usr/bin/env python # -*- coding: utf-8 -*- “”“ Calculs des premiers éléments de la suite de Fibonacci. Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci Application de la définition par récursivité. ”“” def fibonacci_item_recursive(n):

  """
  Renvoie l'élément d'indice n de la suite de Fibonacci
  """
  if n==0:
      return 0
  elif n==1:
      return 1
  return fibonacci_item_recursive(n-1)+fibonacci_item_recursive(n-2)

if name == 'main':

  i=input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ")
  print ("Élément de la suite : "),
  print fibonacci_item_recursive(i)
  print ('Premiers éléments de la suite : ')
  for j in range(10):
      print j,fibonacci_item_recursive(j)

</sxh>

La page Wikipedia sur la suite de Fibonacci introduit aussi un algorithme logarithmique. Même s'il est très intéressant à décortiquer, on peut se contenter de simplement l'appliquer :

<sxh python; title : fibonacci08_fonction_algo_log.py> #! /usr/bin/env python # -*- coding: utf-8 -*- “”“ Calculs des premiers éléments de la suite de Fibonacci. Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci Application de l'algorithme logarithmique http://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique ”“” def fibo2(n):

  """Renvoie F_{n-1}, F_n"""
  if (n == 0):  # cas de base
      return 1, 0  # F_{-1}, F_0
  else:         # récurrence
      f_k_1, f_k = fibo2(n//2)        # F_{k-1}, F_k   avec k = n/2
      f2_k = f_k**2                   # F_k^2
      if n%2 == 0:  # n pair
          return f2_k + f_k_1**2,    f_k*f_k_1*2 + f2_k       # F_{2k-1}, F_{2k}
      else:         # n impair
          return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k  # F_{2k},   F_{2k+1}

def fibonacci_item_logarithmic(n):

  """Renvoie F_n"""
  return fibo2(n)[1]

if name == 'main':

  i=input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ")
  print ("Élément de la suite : "),
  print fibonacci_item_logarithmic(i)
  print ('Premiers éléments de la suite : ')
  for j in range(10):
      print j,fibonacci_item_logarithmic(j)

</sxh>

Nous disposons à présent de 4 méthodes/fonctions pour calculer les éléments de la suite de Fibonacci.

Pour rechercher quel est le meilleur algorithme, cliquez ici !