teaching:progappchim:suite_de_fibonacci-4

Ceci est une ancienne révision du document !


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 !

Ce site web utilise des cookies. En utilisant le site Web, vous acceptez le stockage de cookies sur votre ordinateur. Vous reconnaissez également que vous avez lu et compris notre politique de confidentialité. Si vous n'êtes pas d'accord, quittez le site.En savoir plus
  • teaching/progappchim/suite_de_fibonacci-4.1383895689.txt.gz
  • Dernière modification : 2013/11/08 08:28
  • de villersd