欧博ABG官网-欧博官方网址-会员登入

Programme Python pour imprimer la séquence de Fibonacci

Les questions sur la série Fibonacci sont parmi les plus fréquemment posées lors des entretiens Python.

Dans cet article, je vais expliquer étape par étape comment imprimer la séquence de Fibonacci en utilisant deux techniques différentes, l'itération et la récursivité.

Avant de commencer, comprenons d’abord quelques termes de base.

Qu'est-ce que la séquence de Fibonacci ?

La séquence de Fibonacci est une séquence de nombres dans laquelle un nombre donné est le résultat de l'addition des 2 nombres qui le précèdent. Et l’addition des 2 nombres précédents un certain nombre de fois forme une série que nous appelons la série de Fibonacci.

La séquence de Fibonacci commence par deux nombres, soit 0 et 1. Ensuite, chaque nombre suivant est constitué de l'addition des deux nombres précédents.

Par exemple, prenons 0 et 1. Ce sont les deux premiers nombres de la séquence. Si vous les additionnez, vous obtenez 1. La séquence commence donc par 0, 1, 1,...

Ensuite, pour trouver le numéro suivant, vous ajoutez le dernier numéro que vous avez et le numéro qui le précède. Donc 1+1=2. Donc la séquence jusqu'à présent est 0, 1, 1, 2, ... Cela a du sens ?

Nous pouvons représenter cela de manière plus mathématique comme 0, 1, (1) - [0 + 1]. De même, le prochain nombre de Fibonacci est - 0, 1, 1, (2) - [1 + 1]. Et ainsi de suite. Voici un diagramme montrant les 10 premiers nombres de Fibonacci :

Ceci est un exemple de série de Fibonacci - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Au sein de cette séquence continue, chaque nombre individuel est un nombre de Fibonacci.

Mathématiquement, la séquence de Fibonacci est représentée par cette formule :

F(n)=F(n-1) + F(n-2), où n > 1.

Nous pouvons utiliser cette séquence pour trouver n’importe quel nième nombre de Fibonacci.

Cette séquence fascinante est largement associée au mathématicien Leonardo Pisano, également connu sous le nom de Fibonacci. Il était originaire de la République de Pise, c'est pourquoi il est également connu sous le nom de Léonard de Pise.

Léonard était connu comme l’un des mathématiciens les plus talentueux du Moyen Âge.

Comment imprimer la séquence de Fibonacci en Python

Vous pouvez écrire un programme informatique pour imprimer la séquence de Fibonacci de 2 manières différentes :

De manière itérative, et

De manière récursive.

L'itération signifie répéter le travail jusqu'à ce que la condition spécifiée soit remplie. La récursivité, quant à elle, signifie effectuer une seule tâche et passer à la suivante pour exécuter la tâche restante.

Voici un algorithme itératif pour imprimer la séquence de Fibonacci :

Créez 2 variables et initialisez-les avec 0 et 1 (première=0, seconde=1)

Créez une autre variable pour garder une trace de la longueur de la séquence de Fibonacci à imprimer (longueur)

Boucle (la longueur est inférieure à la longueur de la série)

Imprimer premier + deuxième

Mettre à jour les variables first et second (la première pointera vers la seconde et la seconde pointera vers la première + la seconde)

Décrémentez la variable de longueur et répétez à partir de l'étape 3

Une fois la boucle terminée, terminez le programme

Comment fonctionne l'algorithme itératif :

Considérons que nous devons imprimer une séquence de Fibonacci de longueur 7. Le déroulement de l'algorithme sera alors le suivant :

Iterations Steps Explained Output
Initial   First = 0, Second = 1   [0, 1]  
1   Print (first + second) = [0+1] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above.   [0, 1, 1]  
2   Print (first + second) = [1+1] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above.   [0, 1, 1, 2]  
3   Print (first + second) = [1+2] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above.   [0, 1, 1, 2, 3]  
4   Print (first + second) = [2+3] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculatod above.   [0, 1, 1, 2, 3, 5]  
5   Print (first + second) = [3+5] Now variable first will point to variable second. And second will point to the next Fibonacci number that we calculated above.   [0, 1, 1, 2, 3, 5, 8]  

Ainsi, la séquence finale de Fibonacci pour la longueur 7 sera [0, 1, 1, 2, 3, 5, 8].

Code Python itératif pour imprimer la séquence de Fibonacci :def PrintFibonacci(length): #Initial variable for the base case. first = 0 second = 1 #Printing the initial Fibonacci number. print(first, second, end=" ") #decreasing the length by two because the first 2 Fibonacci numbers #already printed. length -= 2 #Loop until the length becomes 0. while length > 0: #Printing the next Fibonacci number. print(first + second, end=" ") #Updating the first and second variables for finding the next number. temp = second second = first + second first = temp #Decreasing the length that states the Fibonacci numbers to be #printed more. length -= 1 if __name__ == "__main__": print("Fibonacci Series - ") PrintFibonacci(7) pass

Sortie pour la longueur 7 :

Fibonacci Series - 1 1 2 3 5 8

Explication du Code :

Dans le code ci-dessus, nous avons d'abord défini une fonction qui imprimera la série de Fibonacci. Il accepte un paramètre pour la longueur et la fonction doit imprimer la série de Fibonacci.

Ensuite, nous avons créé 2 variables contenant les 2 valeurs initiales de Fibonacci, soit 0 et 1.

Ensuite, nous avons imprimé les 2 premières valeurs [0, 1] et avons décrémenté la longueur de 2, car 2 valeurs avaient déjà été imprimées.

Nous allons exécuter une boucle pour la durée restante et imprimer à chaque fois la valeur de Fibonacci suivante en ajoutant les 2 termes précédents qui sont stockés dans les première et deuxième variables (que nous avons créées initialement pour garder une trace des 2 valeurs précédentes).

Mettez à jour les première et deuxième valeurs qui pointeront vers les 2 valeurs précédentes [première=seconde et seconde=première précédente + seconde].

La boucle s'exécutera jusqu'à ce que la longueur devienne 0, ce qui indique que la longueur requise de la séquence de Fibonacci est imprimée.

Ensuite, nous appelons la fonction définie pour imprimer Fibonacci à partir de la fonction principale en passant l'argument de la longueur requise à imprimer. Et voila!

Il existe une autre approche pour imprimer la séquence de Fibonacci en utilisant la récursion. Comprenons donc également cette approche.

Algorithme récursif pour imprimer la séquence de Fibonacci :

Acceptez la valeur du premier et du deuxième nombre de Fibonacci précédents comme longueur à imprimer.

Vérifiez si la longueur est 0, puis terminez l'appel de fonction.

Imprimez la valeur de Fibonacci en additionnant les 2 valeurs précédentes reçues dans le paramètre de la fonction (première et seconde).

Appelez récursivement la fonction pour la valeur mise à jour du premier et du deuxième, ainsi que la valeur diminuée de la longueur.

Pour cet appel de fonction récursif, nous devons transmettre la valeur initiale de Fibonacci, soit (0 et 1), dans la première et la deuxième variables.

Pour vous aider à mieux comprendre cet algorithme, voyons l’implémentation Python des algorithmes. Ensuite, nous examinerons un exemple afin que vous puissiez voir comment fonctionne cet algorithme récursif.

Code Python récursif pour imprimer la séquence de Fibonacci :def PrintFibonacci(first, second, length): #Stop the printing and recursive calling if length reaches #the end. if(length == 0): return #Printng the next Fibonacci number. print(first + second, end=" ") #Recursively calling the function by updating the value and #decrementing the length. PrintFibonacci(second, first+second, length-1) if __name__ == "__main__": #Print initial 2 values. print(0,1,end=" ") #Calling the Function to print the remaining length #fibonacci series PrintFibonacci(0,1,7-2)

Sortir :

For Length 7 1 1 2 3 5 8 For Length 10 1 1 2 3 5 8 13 21 34

Explication du code :

Tout d’abord, nous avons créé une fonction et effectué une récursion dessus. Dans cette fonction, nous avons accepté la valeur des 2 nombres de Fibonacci précédents pour calculer le nombre de Fibonacci actuel. Et nous avons une longueur qui permet de suivre le cas de base.

Pour le cas de base de récursion, nous vérifions si la longueur atteint 0. Si c'est le cas, nous mettrons fin à l'appel récursif.

Dans d'autres cas, nous imprimons le nombre de Fibonacci en ajoutant les 2 nombres de Fibonacci précédents.

Et puis nous appelons récursivement la fonction pour imprimer la prochaine valeur de Fibonacci en mettant à jour les 2 valeurs précédentes et en décrémentant la longueur.

Visualisons maintenant les appels récursifs de cette fonction à l'aide d'un arbre de récursivité. La longueur que nous voulons imprimer est de 7.

Avant que l'appel récursif ne soit effectué, la fonction principale imprime les 2 valeurs initiales, 0 et 1. Et puis elle transmet ces valeurs à la fonction récursive.

La fonction récursive imprime la valeur (0 + 1) et appelle de manière récursive avec la prochaine valeur mise à jour.

Ensuite, la fonction récursive imprime la valeur (1 + 1) et appelle de manière récursive avec la prochaine valeur mise à jour.

Maintenant, la fonction récursive imprime la valeur (1 + 2) et appelle de manière récursive avec la prochaine valeur mise à jour.

Et puis la fonction récursive imprime la valeur (2 + 3) et appelle récursivement avec la prochaine valeur mise à jour.

Maintenant, la fonction récursive imprime la valeur (3 + 5) et appelle récursivement avec la prochaine valeur mise à jour.

Enfin, le dernier appel est passé. Et la longueur est 0, donc cela mettra à nouveau fin à l'appel récursif et la série sera imprimée sur la console.

Analyse de la complexité temporellePour l'approche itérative

Dans l'algorithme itératif, nous effectuons une boucle jusqu'à ce que la longueur devienne 0. Dans la boucle, nous effectuons une opération à temps constant consistant à imprimer la valeur et à mettre à jour les variables.

Si nous considérons que cette longueur est n, alors la complexité temporelle sera O(n).

Pour l'approche récursive

Dans l’approche récursive, nous appelons des fonctions récursives jusqu’au nombre de fois donné. Nous effectuons également une opération simple et constante d'impression.

Donc, là aussi, si nous considérons que la longueur est de n nombres, alors la complexité temporelle sera O(n).

Analyse de la complexité spatialePour une approche itérative

Dans l'approche itérative, nous n'avons pas utilisé la mémoire supplémentaire pour accepter les deux variables qui gardent la trace des deux nombres de Fibonacci précédents et la constante de n'importe quel nombre de la longueur de la série. La complexité spatiale sera donc constante O(1).

Pour l'approche récursive

Dans l’approche récursive, nous appelons les fonctions de longueur un certain nombre de fois. Nous savons que la récursivité utilise en interne une pile d'appels.

Donc, si nous considérons qu'il s'agit de mémoire occupée par le programme, alors l'appel récursif est effectué le nombre de fois suivant. Alors la complexité spatiale sera O(n).

Conclusion

La suite de Fibonacci est la série de nombres dans laquelle chaque nombre est la somme de ses deux nombres précédents.

Les séquences de Fibonacci se retrouvent non seulement en mathématiques, mais partout dans le monde naturel - comme dans les pétales de fleurs, les feuilles ou les épines d’un cactus, etc.

C'est aussi une question fréquemment posée en entretien - il est donc bon de savoir comment cela fonctionne.

Je me suis inspiré de cet article d'InterviewBit.