Trois algorithmes pour la suite de fibonacci

Soyez le premier à donner votre avis sur cette source.

Vue 40 265 fois - Téléchargée 1 100 fois

Description

Bonjour à tous !

Il existe au moins trois manières de programmer le calcul des termes de la suite de Fibonacci. La première, très coûteuse en temps, consiste à traduire la définition mathématique de la suite (qui est une relation de récurrence telle que : F(0) = F(1) = 1 et F(n) = F(n - 1) + F(n - 2)) sous forme d'algorithme. Une autre version, plus judicieuse, consiste à calculer une seule fois les petites valeurs (alors que la somme F(n - 1) et F(n - 2) oblige à les calculer deux fois) grâce à une fonction auxiliaire. Une troisième méthode, mathématiquement plus riche, exploite une relation matricielle (vous la trouverez dans le zip plus ou moins mal représentée, ou dans d'autres pages où LaTeX permet de faire des merveilles ;-))

Le but de cette source est avant tout de montrer que la notion de complexité compte beaucoup dans les algorithmes, et que son calcul constitue un excellent indicateur de l'efficacité des algorithmes. J'ai aussi inclu l'API QueryPerformanceCounter pour vous permettre de réaliser des mesures plus "concrètes" du temps d'exécution (mais, pour le coup, il faut réitérer plusieurs fois la manoeuvre avant d'obtenir une moyenne exploitable).

Je n'ai rien prévu concernant les grands entiers car mon but n'était pas de réaliser un programme capable de calculer effectivement le cinq millième terme de la suite de Fibonacci. De plus, il existe déjà d'excellentes sources sur le sujet (travailler avec de grands entiers) sur VBFrance. Bis repetita placent jusqu'à un certain point quand même...

La catégorie est 2 "Initié" en raison du recours aux matrices, de la récursivité et de l'API. Bon, rien de bien méchant malgré tout. Disons que c'est un niveau 1 légèrement plus proche de 2 que de 1 :D

Voilà, tout est dit. J'espère que ça vous plaira. Bonne lecture !

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
69
Pour les questions vague, tu es doué...
Messages postés
1
Date d'inscription
jeudi 15 mars 2012
Statut
Membre
Dernière intervention
15 mars 2012

salut à tous je suis un nouveau qui veut réellement apprendre donc j'aurai bésoin de vs aides, soutients, conseils,astuces,...
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
69
j'ai du ecrire un algo pour fibonacci, hier soir, lors d'un test technique, et j'ai écrit :

Private Function ReyFibonacci(ByVal n As Long) As Long
Dim n1 As Long
Dim n2 As Long
Dim i As Long
If n > 0 Then
If n <= 2 Then
ReyFibonacci = 1
Else
n1 = 1
n2 = 1
For i = 3 To n - 1
If i And 1 Then
n1 = n1 + n2
Else
n2 = n1 + n2
End If
Next i
ReyFibonacci = n1 + n2
End If
End If
End Function

Je voulais savoir ce que cet algorithme vallait, et je m'apercoit qu'il est plutôt rapide ^^
Messages postés
251
Date d'inscription
lundi 29 mars 2004
Statut
Membre
Dernière intervention
4 mars 2008
1
Salut !

Un problème de matériel... ce n'est pas drôle ça ! Au pire, il est toujours possible de se rabattre sur GetTickCount. On obtiendra des mesures moins précises, mais faute de mieux c'est encore raisonnable.

Cordialement,
Cacophrène
Messages postés
170
Date d'inscription
jeudi 11 décembre 2003
Statut
Membre
Dernière intervention
24 janvier 2009

Si vous lisez le lien que j'ai mis précédemment, vous verrez qu'il semble y avoir une solution, indiquée ici:

"Problem's been solved. I found a hot-fix for Xp that fixes the QueryPerformanceCounter, so things have returned to normal once more. http://support.microsoft.com/?id=896256 for more info on that if you're interested."

Cela résoud il aussi votre problème?
Afficher les 43 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.