Nombres de Fibonacci en langue java
En fait, les deux premiers nombres de Fibonacci sont prédéfinis. Le premier numéro de Fibonacci est 0 et le deuxième numéro de Fibonacci est 1. Avec une indexation basée sur zéro et en supposant que les numéros de Fibonacci sont dans un tableau, alors:
À l'index 0, le nombre de Fibonacci est 0, (prédéfini);À l'indice 1, le nombre de Fibonacci est 1 (prédéfini);
À l'index 2, le nombre de Fibonacci est 1 = 1 + 0, (par définition);
À l'index 3, le nombre de Fibonacci est 2 = 1 + 1, (par définition);
À l'index 4, le nombre de Fibonacci est 3 = 2 + 1, (par définition);
À l'index 5, le nombre de Fibonacci est 5 = 3 + 2, (par définition);
À l'index 6, le nombre de Fibonacci est 8 = 5 + 3, (par définition);
À l'index 7, le nombre de Fibonacci est 13 = 8 + 5, (par définition);
À l'index 8, le nombre de Fibonacci est de 21 = 13 + 8, (par définition);
À l'index 9, le nombre de Fibonacci est de 34 = 21 + 13, (par définition);
et ainsi de suite.
En programmation, la variable n, et non i est utilisée pour les index basés sur zéro pour ces nombres de fibonacci. Et avec cela, les douze premiers numéros de Fibonacci sont:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | dix | 11 |
La deuxième ligne du tableau donne les index à base de zéro, chacun ayant la variable N dans la programmation. La première ligne donne les nombres Fibonacci correspondants. Donc, les chiffres Fibonacci ne sont pas n'importe quel chiffre. La définition de base commence par 0, pour le premier numéro Fibonacci et 1 pour le deuxième numéro Fibonacci. Le reste des chiffres est produit à partir de là.
Les nombres de Fibonacci peuvent être produits en temps d'O (n) et aussi en temps o (1). Pour l'O (n) temps, si n est 12 par exemple, alors les douze premiers numéros de Fibonacci seraient produits. Pour o (1) temps, un seul numéro de Fibonacci est produit. Par exemple, si n est 6, alors le numéro 8 de Fibonacci serait produit.
Cet article explique ces deux façons de produire des chiffres de Fibonacci en Java.
Formule pour un numéro de fibonacci
Il existe une formule mathématique pour un numéro Fibonacci. Cette formule peut être écrite en trois lignes ou une ligne. En trois lignes, il est écrit comme:
où fn Le numéro Fibonacci est-il au N zéroe indice. C'est ainsi que le numéro de Fibonacci est défini.
Produire des nombres de fibonacci en temps o (n)
Si les nombres Fibonacci doivent être produits en O (3) fois, les nombres, 0, 1, 1 seraient produits; Ce sont les trois premiers numéros de Fibonacci. Le dernier n zéro ne Index ici, est 2. Si les nombres Fibonacci doivent être produits en O (7) fois, les nombres, 0, 1, 1, 2, 3, 5, 8 seraient produits; Ce sont les sept premiers chiffres Fibonacci. Le dernier n zéro ne Index ici, est 6. Si les nombres Fibonacci doivent être produits en O (n) fois, les nombres, 0, 1, 1, 2, 3, 5, 8 - - -, seraient produits; Ce sont les nombres n Fibonacci n. Le dernier n zéro ne L'indice ici est n-1.
La méthode Java dans une classe pour produire les premiers nombres N Fibonacci est:
classe fibonaccivoid fibonacci (int [] p)
int n = p.longueur;
if (n> 0)
P [0] = 0;
if (n> 1)
P [1] = 1;
pour (int i = 2; i
P [i] = currno;
La classe, Fibonacci est privée. Le fibonacci () La méthode prend le tableau P et revient vide. 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 numéros de Fibonacci sont déterminés explicitement et mis dans les première et deuxième positions du tableau.
Le reste des nombres de Fibonacci commençant à partir du troisième (index, n = 2) est déterminé en boucle et mis dans leur position dans le tableau. Donc, la fonction doit retourner vide. La déclaration principale dans la boucle for-il ajoute les deux nombres précédents.
La variable d'index, I, a été utilisée à la place de n, à des fins de clarté.
Une classe principale Java appropriée (avec la méthode principale Java) est:
classe publique Mainpublic static void main (String args [])
int m = 12;
int [] arr = new int [m];
Fibonacci obj = new fibonacci ();
obj.Fibonacci (ARR);
pour (int i = 0; i
Système.dehors.println ();
Une fois que les chiffres ont été produits par la méthode Fibonacci (), la méthode principale Java les lit.
Produisant un numéro de fibonacci en temps constant
Il existe une formule mathématique qui peut être utilisée pour produire un numéro Fibonacci, lorsqu'on lui donne l'indice zéro correspondant, n. La formule est:
où n est l'indice et la fib zéron est le numéro Fibonacci correspondant. Notez que sur le côté droit de l'équation, ce n'est pas la racine carrée de 5 qui est élevée au pouvoir n; c'est l'expression entre parenthèses qui est élevée au pouvoir n. Il y a deux de ces expressions.
Si n est 0, Fibn serait 0. Si n est 1, fibn serait 1. Si n est 2, Fibn serait 1. Si n est 3, Fibn serait 2. Si n est 4, Fibn serait 3 - et ainsi de suite. Le lecteur peut vérifier cette formule mathématiquement, en substituant différentes valeurs pour n et en évaluant.
Lorsqu'il est codé, cette formule produirait un seul numéro Fibonacci pour n. Si plusieurs nombres Fibonacci sont nécessaires, le code de la formule doit être appelé une fois pour chacun des différents index correspondants.
En Java, la méthode pour produire un seul numéro Fibonacci est:
Importer Java.égouter.*classe fib
double fibno (int n)
double fibn = (mathématiques.Pow ((1 + mathématiques.sqrt (5)) / 2, n) -math.Pow ((1-Math.sqrt (5)) / 2, n)) / math.SQRT (5);
retour fibn;
Le java.égouter.* Le package devait être importé au début du programme. En effet. La méthode Java personnalisée ici implémente directement la formule mathématique.
La complexité temporelle de cette fonction est O (1), l'apparition constante d'une opération principale. Une classe principale Java appropriée, avec la méthode principale Java pour la méthode ci-dessus est:
classe publique Mainpublic static void main (String args [])
int n = 11;
Fib obj = new fib ();
double ret = obj.fibno (n);
Système.dehors.println (ret);
L'indice n = 11 est envoyé et le numéro 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 numéro actuel, ajoutez les deux nombres correspondants précédents immédiats. Les deux premiers nombres de Fibonacci, 0 suivis de 1, sont pré-déclarés, pour toute la séquence. Les autres numéros de Fibonacci sont produits à partir de là.
Pour produire des nombres Fibonacci de l'index 2, à celui qui correspond à l'index n-1, utilisez une boucle pour l'énoncé principal:
int Currno = p [i - 1] + p [i - 2];où Curno est le numéro Fibonacci actuel et P est le tableau pour stocker les nombres N.
Pour produire un seul numéro Fibonacci à partir de tout index basé sur zéro, utilisez la formule mathématique: