En fait, les deux premiers nombres de Fibonacci sont prédéfinis. Le premier nombre de Fibonacci est 0 et le deuxième nombre de Fibonacci est 1. Avec une indexation à base zéro et en supposant que les nombres de Fibonacci sont dans un tableau, alors :
à l'indice 0 , le nombre de Fibonacci est 0 , ( prédéfini ) ;à l'indice 1 , le nombre de Fibonacci est 1 , ( prédéfini ) ;
à l'indice deux , le nombre de Fibonacci est 1 = 1 + 0 , ( par définition ) ;
à l'indice 3 , le nombre de Fibonacci est deux = 1 + 1 , ( par définition ) ;
à l'indice 4 , le nombre de Fibonacci est 3 = deux + 1 , ( par définition ) ;
à l'indice 5 , le nombre de Fibonacci est 5 = 3 + deux , ( par définition ) ;
à l'indice 6 , le nombre de Fibonacci est 8 = 5 + 3 , ( par définition ) ;
à l'indice sept , le nombre de Fibonacci est 13 = 8 + 5 , ( par définition ) ;
à l'indice 8 , le nombre de Fibonacci est vingt-et-un = 13 + 8 , ( par définition ) ;
à l'indice 9 , le nombre de Fibonacci est 3. 4 = vingt-et-un + 13 , ( par définition ) ;
etc.
En programmation, la variable n, et non i est utilisée pour les indices de base zéro de ces nombres de Fibonacci. Et avec cela, les douze premiers nombres de Fibonacci sont :
| 0 | 1 | 1 | deux | 3 | 5 | 8 | 13 | vingt-et-un | 3. 4 | 55 | 89 |
| 0 | 1 | deux | 3 | 4 | 5 | 6 | sept | 8 | 9 | dix | Onze |
La deuxième ligne du tableau donne les index de base zéro, dont chacun aurait la variable n en programmation. La première ligne donne les nombres de Fibonacci correspondants. Ainsi, les nombres de Fibonacci ne sont pas n'importe quels nombres. La définition de base commence par 0, pour le premier nombre de Fibonacci et 1 pour le deuxième nombre de Fibonacci. Le reste des numéros sont produits à partir de là.
Les nombres de Fibonacci peuvent être produits en temps O(n) et aussi en temps O(1). Pour le temps O(n), si n vaut 12 par exemple, alors les douze premiers nombres de Fibonacci seraient produits. Pour un temps O(1), un seul nombre de Fibonacci est produit. Par exemple, si n vaut 6, alors le nombre de Fibonacci 8 serait produit.
Cet article explique ces deux manières de produire des nombres de Fibonacci en Java.
Formule pour un nombre de Fibonacci
Il existe une formule mathématique pour un nombre de Fibonacci. Cette formule peut être écrite sur trois lignes ou sur une ligne. En trois lignes, il s'écrit :
où F n est le nombre de Fibonacci au n de base zéro e indice. C'est ainsi que le nombre de Fibonacci est défini.
Production de nombres de Fibonacci en temps O(n)
Si les nombres de Fibonacci doivent être produits en O(3) fois, les nombres 0, 1, 1 seraient produits ; ce sont les trois premiers nombres de Fibonacci. Le dernier n de base zéro e l'indice ici est 2. Si les nombres de Fibonacci doivent être produits en O(7) fois, les nombres 0, 1, 1, 2, 3, 5, 8 seraient produits ; ce sont les sept premiers nombres de Fibonacci. Le dernier n de base zéro e l'indice ici est 6. Si les nombres de Fibonacci devaient être produits en O(n) fois, les nombres 0, 1, 1, 2, 3, 5, 8 – – - seraient produits ; ce sont les n premiers nombres de Fibonacci. Le dernier n de base zéro e l'indice ici est n-1.
La méthode Java dans une classe pour produire les n premiers nombres de Fibonacci est :
classer Fibonacci {annuler fibonacci ( entier [ ] P ) {
entier n = P longueur ;
si ( n > 0 )
P [ 0 ] = 0 ;
si ( n > 1 )
P [ 1 ] = 1 ;
pour ( entier je = deux ; je < n ; je ++ ) { //n=0 et n=2 ont été pris en compte
entier currNo = P [ je - 1 ] + P [ je - deux ] ;
P [ je ] = currNo ;
}
}
}
La classe, Fibonacci est privée. La fibonacci() La méthode prend le tableau P et renvoie void. La méthode commence par déterminer la longueur du tableau. Cette longueur de n est le nombre de nombres de Fibonacci requis. Les premier et deuxième nombres de Fibonacci sont déterminés explicitement et placés dans les première et deuxième positions du tableau.
Le reste des nombres de Fibonacci à partir du troisième (index, n = 2) sont déterminés dans une boucle for et mis à leur place dans le tableau. La fonction doit donc renvoyer void. L'instruction principale dans la boucle for ajoute les deux nombres précédents.
La variable d'indice, i, a été utilisée à la place de n, par souci de clarté.
Une classe Java Main appropriée (avec la méthode Java main) est :
Publique classer Principal {Publique statique annuler principale ( Chaîne de caractères arguments [ ] ) {
entier m = 12 ;
entier [ ] arr = Nouveau entier [ m ] ;
obj de Fibonacci = Nouveau Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
pour ( entier je = 0 ; je < m ; je ++ )
Système . dehors . imprimer ( arr [ je ] + ' ' ) ;
Système . dehors . println ( ) ;
}
}
Une fois les nombres produits par la méthode fibonacci(), la méthode principale de Java les lit.
Produire un nombre de Fibonacci en temps constant
Il existe une formule mathématique qui peut être utilisée pour produire un nombre de Fibonacci, lorsqu'on lui donne l'indice de base zéro correspondant, n. La formule est :
où n est l'indice de base zéro et Fib n est le nombre de Fibonacci correspondant. A noter que du côté droit de l'équation, ce n'est pas la racine carrée de 5 qui est élevée à la puissance n ; c'est l'expression entre parenthèses qui est élevée à la puissance n. Il y a deux de ces expressions.
Si n vaut 0, Fib n serait 0. Si n vaut 1, Fib n serait 1. Si n vaut 2, Fib n serait 1. Si n vaut 3, Fib n serait 2. Si n vaut 4, Fib n serait 3 - et ainsi de suite. Le lecteur peut vérifier mathématiquement cette formule en substituant différentes valeurs à n et en évaluant.
Une fois codée, cette formule produirait un seul nombre de Fibonacci pour n. Si plusieurs nombres de Fibonacci sont requis, le code de la formule doit être appelé une fois pour chacun des différents indices correspondants.
En Java, la méthode pour produire un seul nombre de Fibonacci est :
importer java.lang.* ;classer Mensonge {
double fibNon ( entier n ) {
double FibN = ( Math . pow ( ( 1 + Math . sqrt ( 5 ) ) / deux , n ) – Math . pow ( ( 1 - Math . sqrt ( 5 ) ) / deux , n ) ) / Math . sqrt ( 5 ) ;
revenir FibN ;
}
}
Le package java.lang.* devait être importé au début du programme. En effet, le package contient la classe Math, qui possède les méthodes puissance (pow) et racine carrée (sqrt). La méthode Java personnalisée implémente ici directement la formule mathématique.
La complexité temporelle de cette fonction est O(1), constante apprivoisée d'une opération principale. Une classe Java Main appropriée, avec la méthode principale Java pour la méthode ci-dessus est :
Publique classer Principal {Publique statique annuler principale ( Chaîne de caractères arguments [ ] ) {
entier N = Onze ;
Fib obj = Nouveau Mensonge ( ) ;
double droit = obj. fibNon ( N ) ;
Système . dehors . println ( droit ) ;
}
}
L'indice n = 11 est envoyé et le nombre de Fibonacci, 89 est renvoyé. La sortie est :
89.00000000000003Les chiffres décimaux inutiles peuvent être supprimés, mais c'est une discussion pour une autre fois.
Conclusion
Les nombres de Fibonacci sont une séquence particulière de nombres entiers. Pour obtenir le nombre actuel, additionnez les deux nombres correspondants immédiatement précédents. Les deux premiers nombres de Fibonacci, 0 suivi de 1, sont pré-déclarés, pour toute la suite. Le reste des nombres de Fibonacci sont produits à partir de là.
Pour produire des nombres de Fibonacci à partir de l'indice 2, jusqu'à celui qui correspond à l'indice n-1, utilisez une boucle for avec l'instruction principale :
entier currNo = P [ je - 1 ] + P [ je - deux ] ;où currNo est le nombre de Fibonacci actuel et P est le tableau pour stocker les n nombres.
Pour produire un seul nombre de Fibonacci à partir de n'importe quel indice de base zéro n, utilisez la formule mathématique :
