Trois algorithmes pour la suite de fibonacci
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 !
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
- Trois algorithmes pour la suite de fibonacci
- Architecture trois tiers ✓ - Forum ASP / ASP3
- Fibonacci java ✓ - Forum Java
- Algorithme pour gagner au keno - Forum Visual Basic
- Algorithme de prim - Forum C / C++ / C++.NET
- Algorithme de horner - Forum C / C++ / C++.NET
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.