Les nombres de Fibonacci sont une séquence particulière où la première valeur est pré-déclarée comme 0 et la deuxième valeur est pré-déclarée comme 1. Le reste des nombres est produit à partir de ces deux en ajoutant les deux nombres précédents. Tous les nombres de Fibonacci sont des nombres entiers positifs, commençant à 0. Les douze premiers nombres de Fibonacci et comment ils sont obtenus sont les suivants :
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
Sans les expressions de somme, ces nombres de Fibonacci peuvent être mis dans un tableau comme suit :
| 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 première ligne contient les nombres de Fibonacci. La deuxième ligne a des index de base zéro, en supposant que les nombres de Fibonacci sont dans un tableau.
Les nombres de Fibonacci peuvent être produits en temps O(n) et 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 d'un indice correspondant. C'est pourquoi il suffit d'une 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 Python.
Formule pour un nombre de Fibonacci
La définition formelle d'un nombre de Fibonacci est :
où F n est le nombre de Fibonacci à l'indice n Si n vaut 1, alors seul 0 serait imprimé comme nombre de Fibonacci. Si n vaut 2, alors 0 et 1 seraient imprimés sous forme de nombres de Fibonacci, dans cet ordre. Si n vaut 3, alors 0, 1 et 1 seraient imprimés sous forme de nombres de Fibonacci dans cet ordre. Si n vaut 4, alors 0, 1, 1 et 2 seraient imprimés sous forme de nombres de Fibonacci dans cet ordre. Si n vaut 5, alors 0, 1, 1, 2 et 3 seraient imprimés sous forme de nombres de Fibonacci, dans cet ordre. Si n vaut 6, alors 0, 1, 1, 2, 3 et 5 seraient imprimés sous forme de nombres de Fibonacci, dans cet ordre - et ainsi de suite. La fonction Python pour produire les n premiers nombres de Fibonacci est : Il commence par créer un tableau de n éléments, tous initialisés à zéros. Ce tableau contiendra les nombres de Fibonacci. Le premier nombre de Fibonacci, 0, est déjà là. Le deuxième nombre de Fibonacci, 1, est attribué par l'instruction suivante (dans la fonction). Ensuite, il y a la boucle for, qui commence de l'index 2 juste avant n. Il a la déclaration: Cela ajoute les deux nombres précédents immédiats. Le code pour appeler la fonction et imprimer les douze premiers nombres de Fibonacci peut être : N = 12 La sortie est : Il existe une formule mathématique qui relie un indice de base zéro à son nombre de Fibonacci correspondant. La formule 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 vaut 0, Fibn vaut 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. n est un indice de base zéro dans cette formule. Le code Python de cette formule est : importer des mathématiques Le module mathématique a été importé. Il a la fonction racine carrée. L'opérateur ** est utilisé pour la puissance. La fonction fibNo() implémente directement la formule. Un appel et une impression appropriés pour la fonction fibNo() sont : N = 11 La sortie est : Il est possible de supprimer les chiffres décimaux inutiles de la réponse. Cependant, c'est une discussion pour une autre fois. Si différents nombres de Fibonacci sont requis pour différents n indices, la fonction fibNo() doit être appelée une fois pour chacun des n indices pour renvoyer les différents nombres de Fibonacci correspondants. Le programme suivant le fait pour les index de base zéro, 7 à 9 (inclus) : importer des mathématiques La sortie est : Notez la façon dont la boucle for a été codée en Python. Le premier index est 7. L'index suivant est 8 et le dernier index est 9. 10 dans l'argument de plage est 9 + 1. La valeur à la position 10 doit être le dernier index de base zéro plus 1. Le premier l'argument, 7, est l'index de départ basé sur zéro. Les nombres de Fibonacci sont une séquence particulière de nombres entiers (entiers positifs). Il commence par 0, suivi de 1 inconditionnellement. Le reste des nombres est développé à partir de là en ajoutant les deux nombres immédiatement précédents. Pour obtenir les n premiers nombres de Fibonacci, acceptez 0 et 1 comme les deux premiers, puis pour le reste, utilisez une boucle for avec une instruction telle que : qui additionne les deux nombres immédiatement précédents. Pour obtenir un seul nombre de Fibonacci à partir d'un indice de base zéro n, utilisez la formule : Production de nombres de Fibonacci en temps O(n)
arr = [ 0 ] * ( n )
arr [ 1 ] = 1
pour je dans intervalle ( deux , n ) :
arr [ je ] = arr [ je - 1 ] + arr [ je - deux ]
revenir arr
A = fibonacci(N)
pour i dans la plage (N):
imprimer (A[i], fin='')
imprimer() Produire un nombre de Fibonacci en temps constant
FibN = ( ( ( 1 +math.sqrt ( 5 ) ) / deux ) ** n- ( ( 1 -math.sqrt ( 5 ) ) / deux ) ** n ) / math.sqrt ( 5 )
revenir FibN
droite = fibNo(N)
imprimer (ret)
FibN = ( ( ( 1 +math.sqrt ( 5 ) ) / deux ) ** n- ( ( 1 -math.sqrt ( 5 ) ) / deux ) ** n ) / math.sqrt ( 5 )
revenir FibN
pour je dans intervalle ( sept , dix ) :
imprimer ( fibNon ( je ) , fin = ' ' )
imprimer ( )
Conclusion
