Signification des nombres de Fibonacci
Les nombres de Fibonacci sont une séquence particulière d'entiers positifs, commençant à 0. Les nombres entiers sont des entiers positifs. Ainsi, un nombre de Fibonacci est une séquence particulière de nombres entiers ou de nombres naturels, commençant à 0. Dans cette séquence, les deux premiers nombres sont 0 et 1, dans cet ordre. Le reste des nombres est développé à partir de là en ajoutant les deux nombres précédents. Les douze premiers nombres de Fibonacci sont obtenus comme suit :
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
En d'autres termes, les douze premiers nombres de Fibonacci sont :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Bien sûr, le treizième nombre serait : 144 = 55 + 89. Les nombres de Fibonacci peuvent être imaginés comme étant dans un tableau, comme ceci :
| 0 | 1 | 1 | deux | 3 | 5 | 8 | 13 | vingt-et-un | 3. 4 | 55 | 89 |
Un tableau a des index. Dans le tableau suivant, la deuxième ligne affiche les index de base zéro correspondants pour les nombres de Fibonacci dans un tableau :
| 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 |
Avec les index de base zéro, s'il y a douze éléments, le dernier index est 11.
Les nombres de Fibonacci peuvent être produits en temps O(n) ou en temps O(1). Dans ces expressions de complexité temporelle, n signifie n opérations principales et 1 signifie 1 opération principale. Avec O(n), n nombres de Fibonacci sont produits, à partir de 0. Avec O(1), un nombre de Fibonacci est produit à partir de l'indice correspondant. C'est pourquoi O(1) ne prend qu'une seule opération principale au lieu de n opérations principales.
Le but de cet article est d'expliquer comment produire des nombres de Fibonacci, dans les deux sens, en utilisant JavaScript, qui est en fait ECMAScript aujourd'hui.
Environnement de codage
L'environnement node.js ne sera pas utilisé comme le lecteur aurait pu le prévoir. Au lieu de cela, le navigateur sera utilisé pour l'interprétation du code et l'affichage des résultats. Le script (code) doit être écrit dans un fichier d'éditeur de texte, qui doit être enregistré avec l'extension '.html'. Le script doit avoir comme code minimum :
< ! DOCTYPE HTML >< html >
< tête >
< Titre > Nombres de Fibonacci avec JavaScript Titre >
tête >
< corps >
< type de scénario = 'texte/ecmascript' >
scénario >
corps >
html >
Il s'agit d'un code minimum approximatif dont une page Web a besoin. Tout le codage de cet article se situe entre les balises, .
Pour exécuter le code écrit (ajouté), double-cliquez simplement sur l'icône du nom de fichier et le navigateur de l'ordinateur l'ouvrira.
Définition d'un nombre de Fibonacci
Il existe une définition mathématique pour un nombre de Fibonacci. Il est défini comme suit :
Où Fn est un nombre de Fibonacci correspondant à un indice de base zéro, n.
Les deux premiers chiffres : 0 et 1, sont pré-déclarés, dans cet ordre. La dernière ligne de cette fonction montre comment le reste des nombres provient des deux premiers nombres dans leur ordre.
Cette définition est également l'une des formules du nombre de Fibonacci.
Production de nombres de Fibonacci en temps O(n)
Si n vaut 1, alors seul 0 sera affiché comme nombre de Fibonacci. Si n vaut 2, alors 0 et 1 seraient affichés sous forme de nombres de Fibonacci, dans cet ordre. Si n vaut 3, alors 0, 1 et 1 seraient affichés sous forme de nombres de Fibonacci dans cet ordre. Si n vaut 4, alors 0, 1, 1 et 2 seraient affichés sous forme de nombres de Fibonacci, dans cet ordre. Si n vaut 5, alors 0, 1, 1, 2 et 3 seraient affichés sous forme de nombres de Fibonacci, dans cet ordre. Si n vaut 6, alors 0, 1, 1, 2, 3 et 5 seraient affichés sous forme de nombres de Fibonacci, dans cet ordre - et ainsi de suite.
La fonction ECMAscript pour générer les n premiers entiers (nombres) de Fibonacci est :
< type de scénario = 'texte/ecmascript' >fonction fibonacci ( UN ) {
n = UN. longueur ;
si ( n > 0 )
UN [ 0 ] = 0 ;
si ( n > 1 )
UN [ 1 ] = 1 ;
pour ( je = deux ; je < n ; je ++ ) { //n=0 et n=2 ont été pris en compte
currNo = UN [ je - 1 ] + UN [ je - deux ] ;
UN [ je ] = currNo ;
}
}
La balise de script de fermeture n'a pas été affichée. La fonction reçoit un tableau. Les deux premiers nombres de Fibonacci sont attribués à leur position. La boucle for itère de l'index de base zéro, 2 jusqu'à juste en dessous de n. La déclaration la plus importante dans la boucle for est :
nonactuel = A[i – 1] + A[i – 2] ;
Cela ajoute les deux nombres immédiatement précédents dans le tableau pour obtenir le nombre actuel. Au moment où la fonction fibonacci() termine son exécution, tous les éléments du tableau sont les n premiers nombres de Fibonacci. Un code approprié pour appeler la fonction fibonacci() et afficher les nombres de Fibonacci est :
N = 12 ;arr = Nouveau Déployer ( N ) ;
fibonacci ( arr ) ;
pour ( je = 0 ; je < N ; je ++ )
document. écrivez ( arr [ je ] + ' ' ) ;
document. écrivez ( '
' ) ;
scénario >
Ce code affiche la balise de script de fermeture. Le code est tapé sous le code ci-dessus. La sortie affichée sur la page Web est :
0 1 1 2 3 5 8 13 21 34 55 89
comme prévu.
Production d'un nombre de Fibonacci en temps O(1)
O(1) est un temps constant. Il se réfère à une opération principale. Une autre formule mathématique pour produire un nombre de Fibonacci est :
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 existe deux expressions de ce type.
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 – etc. Le lecteur peut vérifier mathématiquement cette formule en substituant différentes valeurs à n et en évaluant. n est un indice de base zéro dans cette formule. Le résultat est le nombre de Fibonacci correspondant.
Le code ECMAScript (JavaScript) pour cette formule est :
< type de scénario = 'texte/ecmascript' >fonction fibNon ( n ) {
FibN = ( Math . pow ( ( 1 + Math . sqrt ( 5 ) ) / deux , n ) - Math . pow ( ( 1 - Math . sqrt ( 5 ) ) / deux , n ) ) / Math . sqrt ( 5 ) ;
revenir FibN ;
}
La balise de script de fermeture n'a pas été affichée. Notez comment les fonctions prédéfinies de puissance (pow) et de racine carrée (sqrt) ont été utilisées. Dans ECMAScript (JavaScript), le module Math n'a pas besoin d'être importé. La fonction fibNo() implémente directement la formule. Un appel et un affichage appropriés pour la fonction fibNo() sur la page Web sont :
N = Onze ;droit = fibNon ( N ) ;
document. écrivez ( droit ) ;
scénario >
Le code affiche la balise de script de fermeture. La sortie est :
89.00000000000003
Il est possible de supprimer les chiffres décimaux inutiles de la réponse. Cependant, c'est une discussion pour une autre fois.
Si plusieurs nombres de Fibonacci sont requis, le code doit appeler la formule une fois pour chaque indice n correspondant basé sur zéro.
Conclusion
Les nombres de Fibonacci sont une séquence particulière d'entiers positifs, commençant à 0. Les nombres entiers sont des entiers positifs. Ainsi, un nombre de Fibonacci est une séquence particulière de nombres entiers ou de nombres naturels, commençant à 0. Dans cette séquence, les deux premiers nombres sont 0 et 1, dans cet ordre. Ces deux premiers nombres sont simplement définis comme tels. Le reste des nombres est développé à partir de là en ajoutant les deux nombres immédiatement précédents.
Après avoir produit les deux premiers nombres de Fibonacci, afin de produire le reste des nombres de Fibonacci, pour aboutir à un total de n nombres, une boucle for doit être utilisée avec l'instruction :
nonactuel = A[i – 1] + A[i – 2] ;
Cela ajoute les deux derniers nombres de Fibonacci immédiats pour avoir le nombre de Fibonacci actuel.
Lorsqu'on vous donne un indice de base zéro, pour avoir le nombre de Fibonacci correspondant, utilisez la formule :
