J’aime enseigner aux autres les concepts de base en informatique.
Parfois même le CPU en a marre !
Dessin de Binkster.
Introduction à la suite de Fibonacci
Dans cet article, je vais discuter de la deuxième méthode de ma série d’algorithmes récursifs. Comme les factorielles, la séquence de Fibonacci est un autre algorithme qui montre une croissance exponentielle au fil du temps. C’est aussi l’une des quatre méthodes utilisées dans l’étude de la récursivité. Donc, cela dit, je voudrais d’abord donner un aperçu de ce qu’est la suite de Fibonacci.
Qui était Leonardo Fibonacci ?
Leonardo Pisano Boglio (alias Leonardo Fibonacci) était un mathématicien italien du Moyen Âge (vers 1170 – 1250). Il est considéré comme l’un des meilleurs mathématiciens de son temps et est crédité de la création du livre Liber Abacique, qui est un livre basé sur des calculs mathématiques. Bien sûr, l’algorithme le plus célèbre du livre est la suite de Fibonacci, qui est basée sur la résolution d’un problème traitant de la croissance de la population de lapins. La séquence réelle n’était cependant pas la sienne. L’algorithme est en fait basé sur les connaissances qu’il a acquises auprès de mathématiciens hindous qui l’ont découvert vers le 6ème siècle. Cependant, c’était la première fois que l’algorithme était introduit en Occident et donnait à Fibonacci la réputation moderne d’être l’une des personnes qui ont contribué à introduire le système de numération hindou/arabe en Europe.
Alors, quelle est exactement la suite de Fibonacci ?
La séquence était une réponse à un problème portant sur la croissance exponentielle d’une population. Dans le cas du livre de Fibonacci, il traite de la croissance démographique des lapins. L’algorithme prend en compte le nombre d’itérations ou d’appels d’une fonction et additionne la somme de l’itération moins un et du nombre précédent moins deux. Cependant, dans le cas d’un nombre d’itérations de 0 ou 1, la somme serait toujours égale à 0 et 1 respectivement. Pourtant, lorsque le nombre d’itérations devient supérieur à un, vous verrez une croissance exponentielle de la somme produite. Voici comment la formule est écrite pour donner une meilleure idée de ce qui se passe :
Fib(n) où n = 0, la somme est toujours 0 [base case]
Fib(n) où n = 1, la somme est toujours 1 [base case]
Cependant, Fib(n) où tous les entiers n > 1 alors Fib(n) est (Fib(n-1) + Fib(n-2)).
Donc, si l’itération est 0 ou 1, alors le nombre sera égal à 0 et 1 respectivement. Cependant, à mesure que les itérations augmentent au-delà de 1, vous commencez à voir une croissance exponentielle de la sortie.
La suite de Fibonacci en rapport avec l’informatique
Dans le milieu universitaire, les cours de programmation informatique aiment utiliser cet algorithme dans leur étude des méthodes récursives. Dans CS, une méthode récursive est une méthode définie dans sa propre définition. Fondamentalement, au lieu que la méthode soit appelée par une autre méthode, elle s’appelle elle-même. Ce qui, à sa manière, en fait une autre façon de programmer une boucle ?
Le raisonnement derrière l’étude est de donner aux étudiants une compréhension sur la façon de résoudre certains problèmes qui nécessitent une solution à partir d’un cas de base. C’est pourquoi la suite de Fibonacci est si populaire car elle donne un cas de base puis permet à un programme de faire des appels répétés à une méthode pour résoudre le problème. Cela dit, vous trouverez ci-dessous un exemple Java de récursions utilisant la formule de Fibonacci.
Exemple de récursivité utilisant la séquence de Fibonacci.
//***************************************************************
//
// Example of recursion using the Fibonacci sequence in Java.
//
// Author: Bink
//
//**************************************************************
package fibonaccirecursion;
import java.math.BigInteger;//For math function
public class FibonacciRecursion {
//Set initial value for BigInterger: return number
private static BigInteger TWO = BigInteger.valueOf(2);
//Do the recursive calculations
public static BigInteger fibonacciCalculations(BigInteger number){
if(number.equals(BigInteger.ZERO)||number.equals(BigInteger.ONE))
return number;
else
return fibonacciCalculations(number.subtract(BigInteger.ONE)).add(
fibonacciCalculations(number.subtract(TWO)));
}//end function
public static void main(String[] args) {
//run through the sequence until counter == 30
for(int counter = 0; counter <= 30; counter++){
System.out.printf("Fibonacci of %d is: %d\n", counter,
fibonacciCalculations(BigInteger.valueOf(counter)));
}//end for
}//end main
}//end class
conclusion:
Cela résume donc ce qu'est la récursivité et à quel point la formule de Fibonacci est importante pour l'étude de la récursivité. Si vous copiez le code ci-dessus, vous verrez qu'après chaque itération, les nombres augmentent de façon exponentielle jusqu'à ce que vous atteigniez l'itération que vous avez définie. Dans le cas du programme ci-dessus, la limite d'itération a été fixée à 30.
Faites défiler pour continuer
Encore une fois, comme indiqué précédemment, la suite de Fibonacci est un bon moyen d'apprendre à programmer une méthode récursive. Il est largement utilisé dans les universités universitaires, de l'informatique aux diplômes de mathématiques, et il donne au programmeur un autre outil dans son arsenal pour résoudre des problèmes.
Cet article est exact et fidèle au meilleur de la connaissance de l'auteur. Le contenu est uniquement à des fins d'information ou de divertissement et ne remplace pas un conseil personnel ou un conseil professionnel en matière commerciale, financière, juridique ou technique.
Binster (auteur) le 07 janvier 2012 :
merci ib,
Je suis nouveau sur le jeu donc merci pour les conseils. Je vais commencer à faire ça.
Bink
brad maîtres de Californie du Sud le 07 janvier 2012 :
Bink
Joli hub et arrière-plan intéressant.
Si je faisais ce programme, mon style est de mettre l'aperçu des calculs dans la zone de commentaire.
Mais c'est mon style personnel.
Merci
