Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
18 décembre 2010 6 18 /12 /décembre /2010 14:43

La suite de Fibonacci est définie par 2 valeurs de départ :

fibo init

et une relation de récurence pour tout entier n supérieur ou égal à 2  

fibo n

Nous avons vu dans Suite de Fibonacci et tableur que bien qu'il soit facile de calculer les termes de la suite de Fibonacci avec un tableur, ce n'était pas satisfaisant car des erreurs de calculs arrivaient rapidement.

 

On peut écrire un algorithme puis le trauire en lagage machine. Ici, l'algorithme est traduit langage Python (logiciel avec lequel je viens juste de faire connaissance).

 


Algorithme

Fonction en Python

%commentaire% variable : n  (entrée)

 

On assigne à a la valeur 1

On assigne à b la valeur 1

On assigne à c la valeur 1

Si n=1 alors afficher la valeur de a

Sinon et si n=2 alors afficher la valuer de b

Sinon Tant que c<n-2 Faire

           on assigne à a la valeur b

           on assigne à b la valeur a+b

           on assigne à c la valeur c+1

afficher la valeur de a+b

 

def Fibo(n) :
    a,b,c=1,1,1
    if (n==1) :
        print(a)
    elif (n==2) :
        print(b)
    else :
        while (c<n-2) :
            a,b,c=b,a+b,c+1
        print(a+b)

 

Alors que le tableur nous donnait le faux résultat

1 304 969 544 928 660

pour le calcul du 74 ème terme de la suite de Fibonacci, 

on obtient ici en executant Fibo(74) :

1 304 969 544 928 657

Fibo(100) donne par exemple 

35 422 848 179 261 915 075

On peut aussi calculer le 1 000è terme de la suite de Fibonacci en moins d'une seconde grace à ce programme. (Essayez !) 

 

Complexité

 

Notre algotrithme n'utilise que 3 variables en mémoire a,b, et c. Mais comme avec le tableur, il y a 998 calculs si l'on veut le 1 000è terme.

Par définition la suite de Fibonacci est récursive donc on ne pourra pas créer de programme sauf si nous disposions d'une formule permettant de calculer directement le 1 000è terme sans avoir besoin des 999 précédents ! 

C'est que nous verrons avec la formule de Binet.

Partager cet article

Repost 0
Published by Maths_Buchwald - dans Nombre d'or
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories